Section 11.2

Waiting for Patterns

Expected time until a run or pattern appears (HH, HTH, k in a row), via states or the fair-casino martingale.

Toolkit

Patterns in i.i.d. sequences can be timed either by a Markov chain on “longest matching prefix so far” or by a fair-casino (Conway leading-numbers) martingale, exploiting self-overlaps of the target string.

Markov chain approach: let $E_s$ be the expected additional time from state $s$ (current matched prefix); write first-step equations $E_s = 1+\sum_t p_{s\to t}E_t$ and solve, using symmetry to cut the state count when possible.
Run of $k$ successes (prob. $p$ each trial): starting fresh,

E[T]=\sum_{j=1}^{k}p^{-j}.

Non-self-overlapping two-symbol pattern (e.g. HT): expected wait is the sum of the expected waits for each symbol in sequence, since no progress is ever lost on failure.
Self-overlapping patterns (e.g. HTH) take longer than the naive product formula suggests, because a failed attempt can still leave a partial match; compare to the overlap-free case (e.g. wait 10 vs. 8 for HTH vs. HHH-type reasoning).
Conway’s leading-number trick: for a pattern $A$ , $E[T_A]=\sum_{k} 2^{k}$ summed over prefixes of $A$ that are also suffixes of $A$ (with appropriate base replacing 2 for biased/non-binary alphabets), giving a fast alternative to solving the full linear system.

Problems