Section 6.3

Pattern Races

Which of two coin or die patterns appears first (Penney's game), via states of partial progress.

Toolkit

Model progress toward each pattern as a Markov chain on states of “longest relevant suffix matched so far,” then set up first-step equations for the probability (or expected time) of absorption, using overlaps between the two patterns to collapse states.

Key tools:

Conditional expectation / first-step analysis: for state $s$ , $\mathbb{E}[T_s] = 1 + \sum_x p(s,x)\mathbb{E}[T_x]$ , with boundary values $0$ at absorbing (pattern-complete) states.
Let $p_s = \mathbb{P}(\text{pattern A occurs first} \mid \text{current state } s)$ ; solve the linear system $p_s = \sum_x \Pr(x\mid s)\, p_x$ , with $p=1$ at an A-completion and $p=0$ at a B-completion.
Conway’s leading-number algorithm gives odds for Penney’s game directly via pattern self- and cross-correlations, as a shortcut to the full chain.
Exploit shared prefixes/suffixes between the two patterns to merge states and shrink the system.

Problems

6.8 HHT Before HTT+1 variation Medium Free