Race to Three Heads

Worked Solution

How to Think About It: The state is tiny: (your streak, their streak, whose turn), with streaks in $\{0,1,2\}$. Two observations turn this from an 18-equation grind into something you can reason through. First, role-swap symmetry: your winning probability in state $(a, b)$ with *their* turn equals $1$ minus *their* winning probability in $(b, a)$ with the mover's turn — so half the unknowns are mirrors of the other half. Second, and this is the interview move: you don't need the full system to get the number. Expand just one round (their flip, then yours) from the starting position — every branch lands in a state you can price roughly, and one branch lands in (approximately) the *mirror of the start*, which puts $P$ on both sides of the equation. Solving that little self-referential equation gives the answer to two decimal places.

Quick Estimate: Let $P$ = your win probability from the start (your streak 1, opponent about to flip). Play one round — opponent flips, then you flip. No one can finish within this round, so the four equally likely branches ($\tfrac14$ each) are:

• They T, you H $\to$ you sit at streak 2. Estimate it with its own one-liner: your next flip converts with probability $\tfrac12$ — instant win. Miss ($\tfrac12$) and your streak resets, leaving a roughly even race in which they move next, worth a bit under a coin flip to you ($\approx 0.45$). So $\tfrac12 \cdot 1 + \tfrac12 \cdot 0.45 \approx 0.72$ — call it $0.7$.
• They T, you T $\to$ fresh symmetric game, but *they* move first. How big is a mover's edge from scratch? Both of you need an uninterrupted $HHH$ ($\tfrac18$ per three-turn window); moving first just means they get each window one flip before you do — one extra $\tfrac18$-shot's worth of head start, a couple of points, not more. Mover $\approx 0.52$, so you $\approx 0.48$.
• They H, you H $\to$ your streak 2 vs. their 1. Same as the $0.7$ case, except their threat is live: from streak 1 they finish with $HH$ on their next two flips ($\tfrac14$) instead of needing the full $\tfrac18$ triple. A doubled threat that still usually misses shaves a couple of points: call it $0.68$.
• They H, you T $\to$ they hold streak 1, you hold 0: the mirror of your starting position, so your probability is about $1 - P$.

Now solve the one-line recursion:

$$P \approx \tfrac14\big(0.7 + 0.48 + 0.68\big) + \tfrac14(1 - P) \;\Rightarrow\; 5P \approx 2.86 \;\Rightarrow\; P \approx 0.572.$$

That is the whole trick — and note that every input was itself a tiny estimate of the same kind: convert-or-reset one-liners for the streak branches, a first-mover-edge argument for the fresh race, symmetry for the hard branch. Heuristics all the way down, each one checkable in your head. (The exact answer turns out to be $0.5706$ — the mental version is off by $0.002$.)

Approach: For the exact number, set up the mover-perspective values, collapse the 18 states to 9 via the role-swap symmetry, and back-substitute.

Formal Solution:

Part 1 — dynamics. Let $M(a,b)$ = P(you win $\mid$ streaks $(a,b)$, your turn) and $O(a,b)$ = P(you win $\mid$ streaks $(a,b)$, their turn). Flips are fair, streaks reset on tails, and hitting 3 ends the game:

$$M(2,b) = \tfrac12 \cdot 1 + \tfrac12\,O(0,b), \qquad M(a,b) = \tfrac12\,O(a{+}1,b) + \tfrac12\,O(0,b) \;\; (a \le 1),$$ $$O(a,2) = \tfrac12 \cdot 0 + \tfrac12\,M(a,0), \qquad O(a,b) = \tfrac12\,M(a,b{+}1) + \tfrac12\,M(a,0) \;\; (b \le 1).$$

Part 2 — symmetry collapse. Swapping roles swaps the streaks and the mover, so

$$O(a,b) = 1 - M(b,a),$$

which eliminates all nine $O$'s. Substituting into the $M$ equations leaves a $9\times9$ linear system in $M(a,b)$ alone, e.g. $M(2,b) = 1 - \tfrac12 M(b,0)$ and $M(a,b) = 1 - \tfrac12\big[M(b,a{+}1) + M(b,0)\big]$ for $a \le 1$.

Part 3 — solve. Back-substitution clears to denominator $913$. The full table (all values $/913$):

| $M(a,b)$ | $b=0$ | $b=1$ | $b=2$ | |---|---|---|---| | $a=0$ | $478$ | $392$ | $256$ | | $a=1$ | $546$ | $496$ | $288$ | | $a=2$ | $674$ | $640$ | $576$ |

Every equation can be spot-checked by inspection — for instance $M(2,0) = 1 - \tfrac12 M(0,0) = 1 - \tfrac{239}{913} = \tfrac{674}{913}$ ✓, and $M(0,0) = 1 - \tfrac12[M(0,1) + M(0,0)] \Rightarrow \tfrac32 M(0,0) = 1 - \tfrac{196}{913} = \tfrac{717}{913} \Rightarrow M(0,0) = \tfrac{478}{913}$ ✓.

The quantity we want is the start state — your streak 1, *their* flip:

$$O(1,0) = 1 - M(0,1) = 1 - \frac{392}{913} = \boxed{\dfrac{521}{913} \approx 0.5706}$$

Part 4 — sanity checks. The mental recursion's inputs were honest: the table gives $O(2,0) = 1 - M(0,2) = \tfrac{657}{913} \approx 0.72$ (we guessed $0.7$), fresh-game mover edge $M(0,0) \approx 0.524$ (we guessed $0.52$), $O(2,1) \approx 0.685$ (we guessed $0.68$), and the "mirror" branch $O(0,1) = 1 - M(1,0) \approx 0.402$ vs. our $1 - P \approx 0.43$ — the roughest input, and still only $0.03$ off, which the $\tfrac14$ weight shrinks to under a point of error. A 2M-game Monte Carlo gives $0.5707 \pm 0.0004$.

Answer: $P = \dfrac{521}{913} \approx 0.571$. Your edge compounds two effects: the 1-head head start (worth most of it) and favorable turn parity. And the reusable interview skill: expand one round, price the easy branches coarsely, use symmetry to write the hard branch as $1-P$, and solve the little recursion — it gets you to $0.57$ in under a minute without touching the $9\times9$ system.