Optimal Coin Pair Reflipping
Four fair coins are flipped. After seeing the outcome, you may repeatedly choose any pair of coins and reflip both. Each reflip costs you $\$1$. When you stop, your payoff is the number of heads showing, minus the total cost of reflips.
- What is the optimal strategy?
- What is the expected net payoff under optimal play?
Hints
- Think about the expected number of heads you get when you reflip a pair. How does that compare to the pair's current value in each possible state?
- Since reflips are free and unlimited, consider what the best achievable payoff is. Can you guarantee reaching it by repeatedly reflipping underperforming pairs?
- Group the four coins into two independent pairs. Each pair is an absorbing Markov chain: stop at 2H, reflip at 0H or 1H. Absorption at 2H is certain (probability $1/4$ per attempt), so each pair contributes exactly 2 to the final payoff.
Worked Solution
How to Think About It: Without the cost, this problem is trivial — you keep reflipping any non-HH pair until all four coins show heads, always reaching a payoff of 4. Adding the $\$1$ reflip cost creates a genuine optimization problem.
Key Insight: When you reflip a pair of coins, the expected number of heads in that pair after the reflip is 1 (since each coin is fair). So reflipping is only worthwhile if the current pair has fewer than 1 head on average relative to cost — i.e., if the pair currently shows 0 heads (TT).
Analysis by cases. After the initial flip, count the number of heads $h \in \{0, 1, 2, 3, 4\}$:
- $h = 4$ (HHHH): Stop immediately. Payoff = 4.
- $h = 3$ (three H, one T): Reflipping any pair containing the T costs \$1 and gives expected heads in that pair = 1. Currently the pair has 1H + 1T = 1 head. So expected gain = $1 - 1 = 0$, minus \$1 cost. Not worth it. Stop. Payoff = 3.
- $h = 2$ (two H, two T): Reflip the TT pair. Cost = \$1. Expected heads in the reflipped pair = 1, currently 0. Expected gain = $1 - 0 - 1 = 0$. Break-even — but there's a chance of getting HH (payoff improves by 2) which makes it slightly positive in expectation when you consider the option to stop. Actually: reflip TT gives expected heads = 1, so expected payoff change = $+1 - 1 = 0$. It's exactly break-even, so you are indifferent. Stop or reflip once — same expected payoff = 2.
- $h = 1$ (one H, three T): Pick any TT pair. Reflipping costs \$1, expected new heads = 1 (was 0). Expected payoff after one reflip: expected total heads $\approx 2$, having paid \$1. Marginal expected gain = $+1 - 1 = 0$. Again break-even. Payoff = 1.
- $h = 0$ (TTTT): Reflip any pair. Cost \$1, expected heads gain = 1. New expected state ≈ $h = 1$ case. After one reflip, expected net = $1 - 1 = 0$ gain. Payoff = 0.
Conclusion: The optimal strategy is: always stop immediately. The expected payoff equals the initial expected number of heads = $4 \times 1/2 = 2$.
Reflipping is never strictly profitable because each reflip resets a pair to expected value 1 head at a cost of \$1 — exactly break-even. The free reflips made the original problem trivial; the \$1 cost makes reflipping pointless.
Answer: Expected net payoff = $\$2$ under optimal play (stop immediately).
Intuition
This problem tests whether you can see through a trivial setup to the real optimization question. Without cost, the problem is boring — reflip until all heads. With cost, you need to compare the expected gain from a reflip against its price.
Each reflip of a pair resets two coins to fresh fair flips. The expected number of heads in a fresh pair is exactly 1, and the cost is exactly \$1. This means reflipping a pair with 0 heads gains you 1 expected head for \$1 (break-even), reflipping a pair with 1 head gains 0 expected heads for \$1 (losing), and reflipping a pair with 2 heads loses 1 expected head and costs \$1 (terrible). The optimal strategy is simply: never reflip, and your expected payoff is the initial expected head count of 2.