Entropy of a state subject to the action of a set of random unitaries Suppose that we have a known set of unitaries $U_1,...,U_n$ randomly selected from the Haar measure and suppose that each unitary is applied with probability $\frac{1}{n}$ to some input state $\rho$ which is pure and lives in a $d$-dimensional Hilbert space. 
For $n\rightarrow\infty$ it is clear that:
\begin{equation}
\lim_{n\rightarrow\infty}H(\frac{1}{n}\sum_{i=1}^nU_i\rho U_i^+)=\log d
\end{equation}
where $H$ is the von Neumann entropy.
However, for small $n$ how would you explicitly compute the entropy of the state? I'll plug some numbers to show an example: if we let $n=2$, $d=2$, this would be equivalent to computing the following average:
\begin{equation}
E_U\left[H\left(\frac{1}{2} U_1|0\rangle\langle0|U_1^++\frac{1}{2}U_2|0\rangle\langle0|U_2^+\right)\right]
\end{equation}
I've written $|0\rangle\langle0|$ since by symmetry any pure state will have the same entropy, the average is outside the entropy function because by hypothesis the set of unitaries are known, which means that we can distinguish between each set of unitaries, even if we don't know which unitary from the set has been applied.
 A: This is the solution for $n=2$, $d=2$:
You are trying to compute the average entropy of
$$
\rho(U_1,U_2) = U_1|0\rangle\langle0|U_1^\dagger + U_2|0\rangle\langle0|U_2^\dagger
$$
with $U_1$ and $U_2$ distributed according to the Haar measure.
This is equal to the entropy of 
$$
\rho'(U) = |0\rangle\langle0| + U|0\rangle\langle0|U^\dagger
$$
where $U=U_1^\dagger U_2$, which is of course still distributed according to the Haar measure. In turn, this is
$$
\tilde\rho(|\psi\rangle)= |0\rangle\langle0| + |\psi\rangle\langle\psi|
$$
with $|\psi\rangle$ a Haar-random qubit state.
We know that a Haar-random qubit state can be parametrized as 
$$
|\psi\rangle = \cos\tfrac\theta2 \,|0\rangle + e^{i\phi}\sin\tfrac\theta2\, |1\rangle\ ,
$$
where one needs to integrate in spherical coordinates (i.e., with a measure $\tfrac1{4\pi}\sin\theta\,\mathrm{d}\theta\,\mathrm{d}\phi$, $\theta\in[0,\pi]$, $\phi\in[0,2\pi]$).
We now have 
$$\tilde\rho(|\psi\rangle) = \frac12 
\left(\begin{matrix}1+\cos^2\tfrac\theta2 & e^{i\phi}\sin\tfrac\theta2\,\cos\tfrac\theta2\\
e^{-i\phi}\sin\tfrac\theta2\,\cos\tfrac\theta2 & \sin^2\tfrac\theta2\end{matrix}\right)\ .
$$
The entropy of this state is independent of $\phi$ (so we set $\phi=0$), and then we can easily check (e.g. using Mathematica) that the von Neumann entropy (defined with the logarithm base $2$) is
$$
H(\tilde\rho) = \tfrac12\left[-\cos^2\tfrac\theta4\log_2\cos^2\tfrac\theta4 +
\sin^2\tfrac\theta4\log_2\sin^2\tfrac\theta4\right]\ .
$$
The Haar-average can then again be evaluated with Mathematica and turns out to be
$$
\frac{1}{4\pi}\int_0^{2\pi}\mathrm{d}\phi
\int_0^\pi\sin\theta\,\mathrm{d}\theta\, H(\tilde\rho) = \frac13+\frac{1}{6\ln 2} \approx 0.5738 \ .
$$
A: Let me restate the problem in a more operational way, assuming that I have understood the OP's comments below the question. The key point is that the answer depends both on $n$ and on the number of times that the described procedure is repeated. 
Alice prepares $M$ identical systems in different states, denoted $\rho_{\mu}$. Each state $\rho_{\mu}$ is prepared by selecting a set of $n$ unitaries $\{U^{(\mu)}_i\}$ randomly according to the Haar measure, and applying one of them to some fixed initial state $\rho$ with probability $\frac{1}{n}$. Alice then picks one of the $M$ systems at random and sends it to Bob, along with the list of unitaries $\{U^{(\mu)}_i\}$ used in the preparation of each system. Bob, however, does not know which set of unitaries was used to prepare the specific system that he receives.
The state assigned by Bob is
\begin{align*}
\rho_B & = \frac{1}{M} \sum\limits_{\mu=1}^M \,\rho_{\mu} \\
& = \frac{1}{M} \sum\limits_{\mu=1}^M \, \left(\frac{1}{n}\sum\limits_{i=1}^n\, U^{(\mu)}_i \rho \,U^{(\mu) \dagger}_i\right) \\
& = \frac{1}{nM} \sum\limits_{k=1}^{nM}\, U_k \,\rho\, U_k^{\dagger},
\end{align*}
where $U_k = U^{(\mu)}_i$ with $k = i + (\mu -1)n$. Since each set of unitaries $\{U^{(\mu)}_i\}_{i=1}^n$ is uniformly distributed, so is the entire set of unitaries $\{U_k\}_{k=1}^{nM}$. The problem thus reduces to a single realisation of the procedure for each state $\rho_{\mu}$, but now with $M \times n$ unitaries in total. The correct entropy for Bob to ascribe is simply $H(\rho_B)$, with $\rho_B$ given above. 
The intuition here is that from Bob's point of view, the way in which Alice grouped the unitaries is not important. In reality only one unitary from the set was applied to the system that he receives, and each unitary has equal probability $\frac{1}{nM}$.
In general the result thus depends on the set of unitaries and their relation to the initial state. The problem simplifies in the limit of many repetitions $M\to \infty$, in which we have
$$\rho_B = \lim_{M\to\infty} \frac{1}{nM} \sum\limits_{k=1}^{nM}\, U_k \,\rho\, U_k^{\dagger} = \int \mathrm{d}U\, U\rho U^{\dagger} = \frac{1}{d} 1_d,$$
and the entropy is just $H(\rho_B) = \log d$. Note that in this limit, the answer is independent of $n$.
