Introduction to Probability · Problem 11.2.36

Markov Chains — Grinstead & Snell

Mathematics — Probability · absorbing-markov-chains

Problem

We consider next a game called Penney-ante by its inventor W. Penney. There are two players; the first player picks a pattern A of H's and T's, and then the second player, knowing the choice of the first player, picks a different pattern B. We assume that neither pattern is a subpattern of the other pattern. A coin is tossed a sequence of times, and the player whose pattern comes up first is the winner. To analyze the game, we need to find the probability pAp_A that pattern A will occur before pattern B and the probability pB=1−pAp_B = 1 - p_A that pattern B occurs before pattern A. (a) Show that the odds that the first player will win are given by John Conway's formula: pA1−pA=pApB=BB−BAAA−AB.\frac{p_A}{1 - p_A} = \frac{p_A}{p_B} = \frac{BB - BA}{AA - AB}. Hint: Explain why E(TB)=E(TA or B)+pAEA(TB)E(T^B) = E(T^{A \text{ or } B}) + p_A E_A(T^B) and thus BB=E(TA or B)+pA(BB−AB)BB = E(T^{A \text{ or } B}) + p_A(BB - AB). Interchange A and B to find a similar equation involving the pBp_B. Finally, note that pA+pB=1p_A + p_B = 1. Use these equations to solve for pAp_A and pBp_B. (b) Assume that both players choose a pattern of the same length kk. Show that, if k=2k = 2, this is a fair game, but, if k=3k = 3, the second player has an advantage no matter what choice the first player makes.
Intuitive explanation

The key insight is that Conway's formula captures a subtle asymmetry: the probability that pattern A wins depends not just on how likely each pattern is to appear in isolation, but on the overlap structure between them—specifically, how much of pattern B appears within pattern A, and vice versa. By conditioning on which pattern appears first and using the hint to relate expected waiting times, you can derive a ratio that reveals why the second player, who chooses after seeing A, can always exploit these overlaps to gain an edge. For part (b), you'll verify this advantage by computing the formula for all possible 2- and 3-letter patterns, discovering that symmetry breaks down as pattern length increases.

Intuitive explanation

The key insight is that Conway's formula captures a subtle asymmetry: the probability that pattern A wins depends not just on how likely each pattern is to appear in isolation, but on the overlap structure between them—specifically, how much of pattern B appears within pattern A, and vice versa. By conditioning on which pattern appears first and using the hint to relate expected waiting times, you can derive a ratio that reveals why the second player, who chooses after seeing A, can always exploit these overlaps to gain an edge. For part (b), you'll verify this advantage by computing the formula for all possible 2- and 3-letter patterns, discovering that symmetry breaks down as pattern length increases.

Related theory

Browse the problem library