# Coin Flipping Game

A friend asked me a question today. Consider the following coin flipping game. At round 1 of the game, we have a $100$ fair coins, and we flip them all. If we get any heads, we set those aside, and begin round 2 with the remaining coins. During round $i$ the player gets 2 tries. If the player gets all tails 2 times in a row during any round, then he loses. Also, the game ends if he ends up getting all the $100$ coins flipped to heads. The question is, what is the expected number of coins that the player can get? I am hoping for a closed form solution. I feel like this should have an easy solution, but I don't see it.

• So, the game continues until either two throws give no further "heads" or all coins are "heads" ? And you want $E$(number of "heads") ? If so, I don't think that this is easy. A simulation could give an approximate value, but to calculate the exact value will be difficult. – Peter Feb 16 '18 at 11:32
• @Peter Yes that is correct. I was able to use simulation to find an answer. It may be true a closed form is nearly impossible, but I was unsure if I was missing some combinatorial approach. – rabbitsLikeCarrots Feb 16 '18 at 13:52
• Please show the result of your simulation! – Peter Feb 16 '18 at 14:08

If $$\ E_r\$$ is the expected number of coins the player gets when he starts with $$\ r\$$ coins, then $$\ E _0=0, E_1 =\frac{1}{4}\cdot 0 + \frac{3}{4}\cdot 1=\frac{3}{4} \$$, and you can calculate $$\ E_1, E_2, \dots, E_{100}\$$ recursively from the formula $$\begin{eqnarray} E_r &=& \frac{1}{4^r}\cdot 0\ + \frac{2^r+1}{4^r}\sum_\limits{j=1}^r{r \choose j}\left(j+E_{r-j}\right)\\ &=&\left(1+\frac{1}{2^r}\right)\frac{r}{2} +\frac{2^r+1}{4^r}\sum_\limits{j=1}^r {r \choose j}E_{r-j}\ . \end{eqnarray}$$ I doubt if there's a simple closed form expression for $$\ E_r\$$. For the first few I get $$\ E_2= \frac{55}{32}\approx 1.72, E_3=\frac{5589}{2048}\approx 2.73, E_4=\frac{489,413}{2^{16}}\approx 3.73\$$, and $$\ E_{100}\approx 99.7327\$$.
Addendum: In the above analysis I was assuming that the player got two tries in every round, including the first. It wasn't clear to me whether this was the case or not. For the purposes of calculating $$\ E_{100}\$$ from the above recursion it has to be assumed that all the games with fewer than $$100$$ coins are played this way. But if this isn't the case for the actual game, the formula for $$\ E_{100}\$$ in terms of $$E_0, E_1, \dots, E_{99}\$$ would have to be modified as follows: $$E_{100}=50 + \frac{1}{2^{100}}\sum_\limits{j=1}^{100} {100 \choose j}E_{100-j}\ .$$ The difference in the numerical value of $$\ E_{100}\$$ given by this formula and the previous one is so tiny that my $$16$$-decimal precision of my calculator wasn't sufficient to detect it.