Let $A$ be a uniformly random subset of $\{1, 2, … , n\}$. Let $B$ be a random subset of $A$, also chosen uniformly. What is the probability that $B$ has $k$ elements?
My approach was as follows:
Note that the probability of a subset of a size $N$ set having $m$ elements is $\frac{\binom Nm}{2^N}$, since there are $2^N$ possible subsets and $\binom Nm$ ways to make a subset with $m$ elements. Then
\begin{align*}
\operatorname{Pr}(B \text{ has $k$}) &= \sum_j \operatorname{Pr}(B \text{ has $k$}, A \text{ has $j$}) \\
&= \sum_j \operatorname{Pr}(B \text{ has $k$} \, | \, A \text{ has $j$}) \operatorname{Pr}(A \text{ has $j$}) \\
&= \sum_{j=0}^n \Big(\frac{\binom jk}{2^j}\Big)\Big(\frac{\binom nj}{2^n}\Big) \\
&= \frac 1{2^n} \sum_{j=0}^n \frac 1{2^j} \binom jk \binom nj
\end{align*}
But the summation $$\sum_{j=0}^n \frac 1{2^j} \binom jk \binom nj$$ comes out to something nasty, which makes me doubt my answer. Where did I go wrong?
Best Answer
As @Semiclassical mentioned in a comment, uniformly choosing a subset is equivalent to independently flipping a fair coin for each element to decide whether to include it in the subset. Thus, each element is included in the final result with probability $\frac14$, and the probability for $k$ elements to be included is given by the binomial distribution, $\binom nk\left(\frac14\right)^k\left(\frac 34\right)^{n-k}=\frac{3^{n-k}}{4^n}\binom nk$, in agreement with Greg Martin’s comment about the sum at the end of the question.