Race to Four of a Kind
A single fair coin is tossed repeatedly. Player H wins as soon as 4 heads have appeared; Player T wins as soon as 4 tails have appeared. The game ends the moment either player wins.
- What is the maximum number of tosses after which a winner is guaranteed?
- What is the probability the game ends on exactly the 7th toss?
- Conditional on the first three tosses containing exactly 2 heads and 1 tail (order unknown), what is $P(\text{Player H wins} \mid \text{first 3 contain 2H, 1T})$?
Give closed-form answers for all three parts.
Hints
- For part (i), think about what state maximizes the number of tosses before someone must win -- what is the most balanced state possible?
- For part (ii), count the sequences of 6 tosses with exactly 3H and 3T. Check whether any of those sequences could have triggered an early game-ending.
- For part (iii), after conditioning on 2H and 1T in the first 3, H needs 2 more heads and T needs 3 more tails. This is a negative-binomial race -- enumerate the ways H's 2nd head can arrive before T's 3rd tail.
Worked Solution
How to Think About It: This is a race between two counters -- heads toward 4, tails toward 4. Think of it as a random walk on a grid where one coordinate tracks cumulative heads and the other tracks cumulative tails, and the game ends when either coordinate hits 4. Part (i) is about the geometry of this grid. Part (ii) is a combinatorial counting exercise. Part (iii) is a conditional negative-binomial race -- once you know the state after 3 tosses, you just need to figure out who finishes first from that state.
Quick Estimate: Part (i): both players can stall at 3 each (6 tosses), then the 7th must break the tie -- so 7. Part (ii): to reach toss 7, you need exactly 3H and 3T in the first 6, which happens with probability $\binom{6}{3}/2^6 = 20/64 \approx 0.31$. Part (iii): after 2H and 1T, H needs 2 more heads before T gets 3 more tails. H is ahead, so the probability should be above
Formal Solution:
Part (i): Maximum number of tosses.
The game continues as long as both head count
$\boxed{7}$
Part (ii): Probability the game ends on toss 7.
The game ends on toss 7 if and only if the first 6 tosses contain exactly 3 heads and 3 tails. Why is there no early-termination issue? Because if the first 6 tosses have exactly 3H and 3T, neither counter ever reached 4 -- you cannot have 4 heads when the total is only 3, and likewise for tails. So every ordering of 3H and 3T over 6 tosses keeps the game alive.
The number of such sequences is $\binom{6}{3} = 20$, and there are
$P(\text{end on toss 7}) = \frac{\binom{6}{3}}{2^6} = \frac{20}{64} = \boxed{\frac{5}{16}}$
Part (iii): $P(\text{H wins} \mid \text{first 3 contain 2H, 1T})$.
After 3 tosses with 2H and 1T, the state is: H needs 2 more heads, T needs 3 more tails. This is a negative-binomial race on fair coin flips. The game lasts at most
H wins on the $k$-th additional toss (for $k = 2, 3, 4$) if there are exactly $k - 2$ tails among the first $k - 1$ additional tosses and the $k$-th toss is heads.
- $k = 2$: Both additional tosses are heads. Probability: $(1/2)^2 = 1/4$.
- $k = 3$: Exactly 1 tail in the first 2, then heads. Probability: $\binom{2}{1}(1/2)^3 = 2/8 = 1/4$.
- $k = 4$: Exactly 2 tails in the first 3, then heads. Probability: $\binom{3}{2}(1/2)^4 = 3/16$.
Summing:
$P(\text{H wins} \mid 2\text{H}, 1\text{T}) = \frac{1}{4} + \frac{1}{4} + \frac{3}{16} = \frac{4 + 4 + 3}{16} = \boxed{\frac{11}{16}}$
Alternatively, this is a standard negative-binomial result: the probability that the $r$-th success arrives before the $s$-th failure in Bernoulli(
Answer: (i) $7$. (ii) $5/16$. (iii)
Intuition
This problem is really about racing counters on a fair coin, and each part tests a different combinatorial skill. Part (i) is about the pigeonhole principle applied to the game state -- if both players are one away from winning, the next toss must break the deadlock. Part (ii) exploits the clean observation that with exactly 3H and 3T, no early termination is possible, so you just need a single binomial coefficient. Part (iii) introduces the negative-binomial race framework, which appears constantly in quant interviews: two competing Poisson processes (or geometric/Bernoulli races), where you condition on the current state and ask who finishes first.
The broader lesson is that many interview problems about sequential games reduce to a race between two counters. Once you identify the state (how much each player still needs), the problem becomes a standard calculation. The negative-binomial race formula -- the probability that the $r$-th success arrives before the $s$-th failure -- is a workhorse tool worth memorizing. It shows up in everything from best-of-$n$ series to order-book queue models.