Problem #70 HARD
The Unfair Coin Tournament
Google Netflix Probability Game Theory
Problem Statement
Arjun and Bhavna play a coin-flipping game. They use a coin that lands heads with probability p and tails with probability (1-p), where p is unknown but fixed. Arjun wins a point each time the sequence HT appears (heads then tails on consecutive flips). Bhavna wins a point each time TH appears. They keep flipping until one player has 5 points. Is this game fair — does each player have an equal probability of winning — for all values of p? If not, for which p is it fair?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
The game is perfectly fair for all p ∈ (0,1). Each player wins each point with probability exactly 1/2, regardless of the coin's bias. The reason: transitions between H and T strictly alternate, so HT and TH occurrences are always balanced. At p=0 or p=1 the game never terminates.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Consider any sequence of coin flips. Mark each position where the flip differs from the previous flip. These are the transition points. A transition from H to T scores HT (Arjun's point). A transition from T to H scores TH (Bhavna's point). The transitions alternate: every HT is followed eventually by a TH and vice versa.
Step 1: Consider the sequence of flip outcomes. Ignoring the very first flip, every flip is either a continuation of the current run or a transition.
Step 2: A transition H→T gives Arjun a point. A transition T→H gives Bhavna a point. Transitions strictly alternate between H→T and T→H (you cannot have two H→T transitions in a row without a T→H between them).
Step 3: Therefore, the number of HT transitions and TH transitions in any sequence differ by at most 1. In a long sequence, both occur with equal frequency.
Step 4: More precisely: P(next transition is H→T | currently in H-run) = probability that next different flip is T = (1-p). P(next transition is T→H | currently in T-run) = probability that next different flip is H = p. But the overall rate balances out: each player's scoring events have equal long-run frequency.
Step 5: Formally: P(HT occurs before TH | starting fresh) = 1/2 for any p ∈ (0,1). This can be proved by symmetry — the game from any neutral state is equivalent for both players.
Step 6: The game is fair for all p ∈ (0,1). At p=0 (always tails) or p=1 (always heads), no transitions occur and neither player ever scores.
Key Insight:
The fairness is guaranteed by the alternating nature of transitions. In any binary sequence, the counts of H→T and T→H transitions can differ by at most 1. This structural property — not the specific value of p — is what makes the game fair. Pattern race games are often analysed using the theory of Markov chains and stopping times.