Optimal Re-Flip Strategy for a Coin Game
You flip $n$ fair coins and receive a payoff $f(H)$ that depends on the number of heads $H$. After seeing the result, you have one chance to re-flip all $n$ coins simultaneously -- or you can keep what you have.
What is the optimal strategy for deciding whether to re-flip? Specifically:
- Derive the general decision rule in terms of $f(H)$ and the distribution of $H$.
- Identify the threshold $H^{*}$ for the symmetric case where the payoff is simply $f(H) = H$ (i.e., you earn one dollar per head).
- Briefly explain why re-flipping a subset of coins is not better than re-flipping all-or-nothing.
Hints
- Think of re-flipping as receiving a draw from the same unconditional distribution. What is that draw worth in expectation?
- Compare your current payoff $f(H)$ to the expected payoff $\mu = E[f(H)]$ of a fresh flip. The optimal rule is a simple threshold.
- For $f(H) = H$ with $n$ fair coins, $\mu = n/2$. Re-flip if $H < n/2$, keep otherwise -- the decision is symmetric around the mean.
Worked Solution
How to Think About It: This is an optimal-stopping problem with exactly one chance to reset. For the *all-or-nothing* option, the key fact is that re-flipping all $n$ coins is an independent draw from the same unconditional distribution -- it does not matter what you saw, because a fresh full re-flip is always worth $E[f(H)]$. So you keep iff your realized payoff beats that mean. The honest comparison is therefore: is my current $f(H)$ above or below $\mu = E[f(H)]$?
A separate and important point (Part 3): if instead you were allowed to re-flip a *subset* of the coins, that flexibility is strictly better, not worse, for a payoff like $f(H)=H$ -- you would keep the heads and re-flip only the tails. The claim that subset re-flipping is dominated by all-or-nothing is false; it is the all-or-nothing rule that is the restriction.
Quick Estimate: Take $n=10$, $f(H)=H$, so $\mu = E[H] = 5$. Under the all-or-nothing rule you end with $\max(H,5)$; computing $E[\max(H,5)]$ over the Binomial$(10,\tfrac12)$ gives about $5.62$ -- a modest lift over the always-keep value of $5$. If subset re-flipping were allowed, keeping heads and re-flipping tails gives $h + (n-h)/2$ given $h$ heads, with unconditional mean $3n/4 = 7.5$ -- much higher.
Approach: For the stated all-or-nothing option, compare the realized payoff to the fresh-draw mean $\mu$. Then specialize to $f(H)=H$. Finally, analyze subset re-flipping directly to see it dominates.
Formal Solution:
*Part 1 -- general all-or-nothing rule.* Let $H \sim \text{Binomial}(n,\tfrac12)$ and $\mu = E[f(H)] = \sum_{k=0}^{n} f(k)\binom{n}{k}2^{-n}$. After observing $H=h$ you choose between keeping ($f(h)$ for sure) and re-flipping all $n$ coins (an independent draw, expected $\mu$ regardless of $h$). To maximize expected payoff,
$\text{re-flip iff } f(h) < \mu, \quad \text{keep iff } f(h) > \mu, \quad \text{indifferent if } f(h)=\mu.$
This is the entire content of the rule: the re-flip value is the constant $\mu$, so the decision is just a threshold on $f(h)$.
*Part 2 -- threshold for $f(H)=H$.* Here $\mu = E[H] = n/2$, so
$\text{re-flip iff } H < \tfrac{n}{2}, \qquad \text{keep iff } H \ge \tfrac{n}{2}.$
The cutoff is the real number $H^{*} = n/2$. For odd $n$ no integer lands on it, so you re-flip when $H \le \lfloor n/2\rfloor$ and keep otherwise. For even $n$ the value $H=n/2$ is achievable and you are genuinely indifferent there (keeping and re-flipping both give $n/2$ in expectation). For $n=10$, $H^{*}=5$: re-flip on $H\in\{0,\dots,4\}$, keep on $H\in\{5,\dots,10\}$.
*Value of the all-or-nothing option.* The payoff under optimal play is $\max(f(H),\mu)$, so the gain over always-keeping is $E[\max(f(H),\mu)]-\mu = E[(f(H)-\mu)^{+}] \ge 0$. For $f(H)=H$, $n=10$: $E[\max(H,5)] \approx 5.615$, versus $5$ for always-keep.
*Part 3 -- subset re-flipping is BETTER, not dominated.* Suppose you may choose any subset $S$ of coins to re-flip. For $f(H)=H$ the contributions are additive across coins, and each coin contributes
$h + \tfrac{1}{2}(n-h),$
and unconditionally
$E\!\left[H + \tfrac12(n-H)\right] = \tfrac{n}{2} + \tfrac12\!\left(n-\tfrac{n}{2}\right) = \frac{3n}{4}.$
For $n=10$ this is $7.5$, which exceeds the best all-or-nothing value ($\approx 5.615$). So subset re-flipping strictly improves on all-or-nothing whenever the coin shows a mix of heads and tails -- it is never dominated by it. (Intuitively, all-or-nothing forces you to throw away good coins along with bad ones; subset re-flipping lets you discard only the bad ones. The two coincide only in the degenerate cases of all-heads or all-tails.)
Answer: 1. Re-flip iff $f(H) < E[f(H)]$ (keep iff above the fresh-draw mean $\mu = E[f(H)]$; indifferent if equal). 2. For $f(H)=H$, $\mu=n/2$, so the threshold is $H^{*}=n/2$: re-flip when $H<n/2$, keep when $H\ge n/2$ (indifferent at $H=n/2$ for even $n$). 3. Subset re-flipping is strictly better, not dominated: for $f(H)=H$ you keep the heads and re-flip the tails, achieving expected payoff $3n/4$ (e.g. $7.5$ for $n=10$), well above the best all-or-nothing value ($\approx 5.615$).
Intuition
This problem is a clean illustration of the value of an option. The right to re-flip is a real option -- it lets you replace a bad draw with the expected value of a fresh one. The optimal strategy is always to exercise the option when your realized outcome is below the option's expected payoff, and never otherwise. This is the same logic behind any call option: exercise when the asset price (your current payoff) is below the strike (the expected value of re-flipping). The gain from holding the option is exactly $E[(f(H) - \mu)^{+}]$ -- the expected upside you capture by selectively re-flipping.
In real trading, this structure appears constantly: you hold a position and you get one chance to reset (roll to a different expiry, switch the underlying, re-hedge). The naive mistake is to anchor on sunk costs -- 'I got unlucky, I should definitely re-flip.' The correct reasoning ignores the past entirely. The re-flip distribution is independent of history, so your decision depends only on whether your current position is above or below what the reset gives you in expectation. This is why experienced traders talk about 'marking to market' your decision -- the history of how you got here is irrelevant; only the current state vs. the alternative matters.