Expected value of coin reflip problem for large number of coins

The following is a modified Jane Street interview question.

Question: Given $$100$$ fair coins. For each head obtained, we get $$\1$$. If we can re-flip any number of coin once, what is the expected value of the game?

By 're-flip any number of coin once', I mean that we can flip those coins which do not give tails. For example, if we have $$4$$ coins and we obtain $$HTHT$$, then we can flip second and fourth coin again to increase our gains.

I know how to solve the problem for $$4$$ fair coins:

Without re-flipping, the expected value of the game is $$\2.$$ With re-flipping, we can calculate the additional gain in the following manner:

$$\frac{1}{16}\times 0 + \frac{4}{16}\times 0.5 + \frac{6}{16}\times 1 + \frac{4}{16}\times 1.5 + \frac{1}{16}\times 2 = 1.$$

So, the expected value with re-flipping for $$4$$ fair coins is $$\3$$.

I am able to do the above calculations in my head and get the answer without using pen and papers. However, if I am given $$100$$ coins, then I am not able to calculate the additional gain in my head as it is quite tedious.

I am wondering whether there is a shorter way to solve the $$100$$ coins problem without using pen and paper.

• Hint: imagine that you flip every coin twice and the losses are exactly the $TT$ coins.
– lulu
Commented Jan 11, 2020 at 15:32

Each coin has an expected value of $$\.75$$ since the only outcome which does not yield $$\1$$ is $$TT$$, a probability $$\frac 14$$ event.
By linearity the expected value of the $$100$$ coins is then $$.75\times 100=\boxed { 75}$$
Sanity check: with $$4$$ coins instead of $$100$$ this method would give $$.75 \times 4=3$$, in agreement with your calculation.