We use optional analytics, advertising and affiliate technologies to
measure usage, attribute advertising and improve EverythingQuant.
You can accept or reject non-essential tracking.
You are given an even coin, and 100 flips of this coin. You can choose to flip, or cash-out. Every time you flip a heads, $5 is added to your winnings. You can cash-out only when a heads is present, But you will no longer be able to play the game. If you reach the end of the 100 flips, and the last flip is a tails, then you receive no money. What is the optimal strategy for this game?
Solution
As with all optimisation questions, we will pose a family of strategies and then compare their expected values. Our success metric will be expected value, since this tells us how much money we make on average per game.
Let us first look at a simple strategy:
wait until the very end, and only cash out if one of the final flips gives us a heads.
Suppose we decide that the first \(100-n\) flips are always played, and then during the final \(n\) flips we cash out at the first heads that appears. If no heads appears in those final \(n\) flips, we get nothing.
This gives us a clean way to compare strategies.
During the first \(100-n\) flips, the expected number of heads is
\[
E[H] = (100-n)\cdot \frac{1}{2} = \frac{100-n}{2}.
\]
If a heads appears at some point in the final \(n\) flips, then when we cash out, we expect to have collected
\[
\frac{100-n}{2} + 1
\]
heads in total: the average number from the first \(100-n\) flips, plus the one heads that finally lets us stop.
Each heads is worth \(\$5\), so conditional on successfully seeing at least one heads in the final \(n\) flips, the expected cashout amount is
\[
5\left(\frac{100-n}{2}+1\right).
\]
Now the probability that at least one of the final \(n\) flips is heads is
\[
1 - \left(\frac{1}{2}\right)^n = \frac{2^n-1}{2^n}.
\]
So the expected value of this “start banking in the last \(n\) flips” strategy is
\[
E[X_n] = 5\left(\frac{100-n}{2}+1\right)\frac{2^n-1}{2^n}.
\]
This is the quantity we want to maximize.
Let us compute a few values.
For \(n=1\), we ignore the first \(99\) flips and only rely on the last flip:
\[
E[X_1] = 5\left(\frac{99}{2}+1\right)\frac{1}{2} = \$126.25.
\]
For \(n=2\), we start banking on either of the last \(2\) flips:
\[
E[X_2] = 5\left(\frac{98}{2}+1\right)\frac{3}{4} = \$187.50.
\]
For \(n=3\),
\[
E[X_3] = 5\left(\frac{97}{2}+1\right)\frac{7}{8} = \$216.56.
\]
For \(n=4\),
\[
E[X_4] = 5\left(\frac{96}{2}+1\right)\frac{15}{16} = \$229.69.
\]
For \(n=5\),
\[
E[X_5] = 5\left(\frac{95}{2}+1\right)\frac{31}{32} = \$234.92.
\]
For \(n=6\),
\[
E[X_6] = 5\left(\frac{94}{2}+1\right)\frac{63}{64} = \$236.25.
\]
For \(n=7\),
\[
E[X_7] = 5\left(\frac{93}{2}+1\right)\frac{127}{128} = \$235.64.
\]
Since \(n=6\) gives a higher expected value than both \(n=5\) and \(n=7\), this identifies the optimum in this family of threshold strategies.
So the best simple strategy is:
begin cashing out on any heads that appears in the last \(6\) flips.
Equivalently, always continue through the first \(94\) flips, and then from flip \(95\) onward, stop as soon as you see a heads.
This gives an expected payoff of
\[
\$236.25.
\]
A more formal dynamic programming approach can be used to prove this exactly, but for interview purposes, this threshold argument is usually the cleanest presentation and gets to the correct strategy quickly.