# Expected number of coin tosses needed until all coins show heads

We flip $n$ fair coins every iteration of the game. Every coin that shows heads is removed from the game and we use the remaining $n-k$ coins to play the game again (where $k$ is the number of heads in that iteration). What is the expected number of iterations we need to complete before all the coins are gone.

• I think partition theorem is gonna help a lot – user160738 Jul 5 '14 at 19:22
• Here is a startling assertion that I once heard in a combinatorics seminar: Suppose you keep this process going until the number of remaining coins is ether $0$ or $1$. Then the probability that it stops at $0$ rather than $1$ does not approach a limit as $n\to\infty$, but instead the lim sup and lim inf differ by about $10^{-4}$. ${}\qquad{}$ – Michael Hardy Jul 5 '14 at 23:15

Note that each iteration of the game follows a binomial random variable, namely $$X_r \sim B(N_r, 1/2),$$ where $N_r$ is the number of remaining coins in each try.
Now, the expectation of a Binomial random variable equals the probability parameter times the number of experiencies, in this case $$\mathbb{E}(X_r)=\cfrac{N_r}{2}.$$ The formula above tells us about how many coins we might expect to keep at each iteration, that is, $N_0 = n$, $$N_1 = n - \frac{n}{2} = \frac{n}{2} = \frac{N_0}{2}$$ and so on. Therefore, $$N_r = \frac{N_{r-1}}{2}= \dots = N_02^{-r}=n2^{-r}.$$ Of course, this goes to zero when $r$ tends to $\infty$, so instead of asking when does this number equal zero, let's just compute when it is one, that is $$N_r = 1 \Leftrightarrow n2^{-r}=1 \Leftrightarrow r = \log_2 n.$$ Then, when only one coin remains, we can reasonably expect to draw heads after 2 tries, so there you go, you can expect $\log_2 n + 2$ tries to get rid of all the coins. Put either the floor or the ceiling function, both answers are correct, since this is an expectation, meaning that it is not necessarily the actual number of iteartions.
Hint: After $m$ flips, the chance that a given coin has been removed is $1-2^{-m}$. The chance that all the coins have been removed is then $(1-2^{-m})^n$. The chance the last coin is removed on flip $m$ is then $(1-2^{-m})^n-(1-(1-2^{-m+1})^n)$ because it has to survive through flip $m-1$.