Keep or Play: Optimal Replay in a Coin-Flipping Game
You are offered the following game. You flip a fair coin repeatedly until you land tails. For each head you flip before that first tails, you earn $\$h$. Once tails appears, you can either keep your payout or abandon it and play a second round under the same rules. If you replay, your first-round earnings are forfeited and you must accept whatever the second round gives you (no further replays).
Find the optimal strategy and the fair value of this game when $h = 10$.
Hints
- Compare what you earned in round 1 to what you would expect from a fresh round. When is it worth giving up your current payout?
- The number of heads before the first tails follows a $\text{Geometric}(1/2)$ distribution. What is the expected single-round payout, and for which outcomes does your payout fall below that?
- You should replay only when you got zero heads (immediate tails). Use the memoryless property to compute $E[\text{payout} \mid \text{at least one head}]$, then combine the two cases.
Worked Solution
How to Think About It: This is an optimal stopping problem with one replay option. The key question is: when should you walk away from your first-round earnings and gamble on a fresh round? The answer depends on comparing what you already have to what you expect from replaying. Since each round is independent, the expected value of the second round is just the expected value of a single round -- so you should replay exactly when your first-round payout falls below that benchmark.
Quick Estimate: In a single round, the number of heads before the first tails follows a $\text{Geometric}(1/2)$ distribution (counting failures before the first success). The expected number of heads is $(1 - 1/2)/(1/2) = 1$, so a single round is worth $h = \$10$ on average. You should replay only when you earned less than $\$10$, which means you got zero heads -- that is, the very first flip was tails. That happens with probability $1/2$. So roughly half the time you take a fresh round (worth $\$10$ on average) and half the time you keep a payout that, conditional on having at least one head, should be worth more than $\$10$. The game value should be somewhere above $\$10$ -- let's guess around $\$15$.
Approach: Compute the expected single-round payout, determine the optimal replay threshold, then use the law of total expectation to combine both cases.
Formal Solution:
Let $N$ be the number of flips until the first tails. Then $N \sim \text{Geometric}(1/2)$ with $E[N] = 2$. The number of heads is $N - 1$, so the single-round payout is $h(N - 1)$ with expected value:
$$E[h(N-1)] = h(E[N] - 1) = h(2 - 1) = h$$
The optimal strategy is to replay if and only if your first-round payout is less than $h$ (the expected value of a fresh round). Since payouts come in multiples of $h$, you replay exactly when you earned $0$ (i.e., zero heads, which means the first flip was tails).
Now compute the expected value of the optimal strategy by conditioning on the first flip:
- Case 1: First flip is tails (probability $1/2$). You earned $\$0$, so you replay. The second round has expected payout $h$.
- Case 2: First flip is heads (probability $1/2$). You already have $\$h$ in the bank. By the memoryless property of the geometric distribution, the remaining flips (until tails) are distributed exactly like a fresh game. So the expected number of additional heads is $E[N] - 1 = 1$, giving an additional expected payout of $h$. Total expected payout in this case is $h + h = 2h$.
By the law of total expectation:
$$E[\text{game}] = \frac{1}{2} \cdot h + \frac{1}{2} \cdot 2h = \frac{3h}{2}$$
Answer: The optimal strategy is to keep your payout whenever you flip at least one head, and replay only when you get immediate tails (zero heads). The fair value of the game is $3h/2 = \$15$ when $h = 10$.
Intuition
The core principle here is one you see constantly in trading and risk management: compare what you have to your outside option. Your first-round payout is a known quantity; the second round is a fresh draw from the same distribution. Replaying is profitable exactly when your current position is below the expected value of that fresh draw. Since payouts are discrete multiples of $h$ and the expected single-round value is exactly $h$, the only outcome worse than the benchmark is zero heads -- and that bright-line threshold makes the strategy trivially simple.
The memoryless property of the geometric distribution is doing real work here. Once you have flipped at least one head, your future flips look exactly like a brand-new game -- so your conditional expected payout given at least one head is $h$ (the one head you already have) plus $h$ (the expected additional heads from the remaining flips), giving $2h$. This memoryless structure shows up whenever you model arrival times or waiting processes in markets, and recognizing it immediately simplifies many interview problems.