1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think partition theorem is gonna help a lot $\endgroup$ – user160738 Jul 5 '14 at 19:22
  • $\begingroup$ 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{}$ $\endgroup$ – Michael Hardy Jul 5 '14 at 23:15
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Hello Ross, wondering if you could quickly describe how you'd finish this problem with your technique. Trying to improve my skills in probability. I understand the approach above by busman, but this one eludes me. $\endgroup$ – user365239 Dec 29 '16 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.