Coin Flipping Game

Question

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.

Answer 1

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.