Waiting Time Until a Pattern Appears

Flip a fair coin repeatedly. How many flips, on average, until you first see the pattern HTH? Now ask the same question for HHH. Both are specific three-flip sequences, each with probability $1/8$ on any given triple of flips — so a natural guess is that both take the same number of flips on average to appear. That guess is wrong, and the gap between the two answers is the entire lesson.

Try computing the expected wait for HTH before reading on, using the state-machine method from first-step conditioning.

The trap: treating "probability 1/8" as the whole story

If flips were grouped into non-overlapping blocks of three and you only checked each block once, then yes, both patterns would need an expected 8 blocks (24 flips) by the geometric-distribution logic. But real flipping doesn't reset every three flips — the pattern is checked continuously across a sliding window, and what happens when you almost match but fail differs sharply between the two patterns. That difference is entirely about self-overlap: does a prefix of the pattern coincide with a suffix of it?

Worked example: HTH, where a failure partially rescues you

Define states by "the longest suffix of what you've seen so far that is also a prefix of HTH": state 0 (no progress), state 1 (last flip was H), state 2 (last two flips were HT). Let $E_0, E_1, E_2$ be the expected additional flips needed from each state.

From state 0: flip. H (prob 1/2) advances to state 1. T (prob 1/2) stays at state 0 (T alone matches no prefix of HTH). $E_0 = 1 + \tfrac12 E_1 + \tfrac12 E_0.$

From state 1 (just saw H): flip. T (prob 1/2) advances to state 2 (now "HT" matches). H (prob 1/2) — you saw "HH"; the last flip, H, is itself a valid one-letter prefix of HTH, so you stay at state 1, not back to state 0. $E_1 = 1 + \tfrac12 E_2 + \tfrac12 E_1.$

From state 2 (just saw HT): flip. H (prob 1/2) completes HTH — done. T (prob 1/2) — you saw "HTT"; the longest suffix matching a prefix of HTH is nothing, so you drop all the way to state 0. $E_2 = 1 + \tfrac12(0) + \tfrac12 E_0.$

Solve: from the first equation, $\tfrac12 E_0 = 1+\tfrac12E_1 \Rightarrow E_0 = 2+E_1$. From the second, $\tfrac12E_1 = 1+\tfrac12E_2 \Rightarrow E_1=2+E_2$. Substitute into the third: $E_2 = 1+\tfrac12(2+(2+E_2)) = 1+\tfrac12(4+E_2)=1+2+\tfrac12E_2$, so $\tfrac12E_2=3$, $E_2=6$. Then $E_1=2+6=8$, and $E_0=2+8=10$.

Expected wait for HTH: 10 flips.

Worked example: HHH, where every failure sends you back to zero

Same method, states 0/1/2 by longest matching prefix. From state 2 (saw HH): H completes it; T sends you to state 0 — a total wipeout, because "HHT" shares no suffix with any prefix of HHH. From state 1 (saw H): H advances to state 2; T sends you back to state 0 completely. Every miss is a full reset. Running the same algebra (or reusing the geometric-style logic that a full-reset $k$-length pattern has expected wait $2+4+\cdots+2^k = 2^{k+1}-2$ for a fair coin) gives:

Expected wait for HHH: 14 flips.

The gap is entirely explained by self-overlap. HTH's prefix "H" reappears as its own suffix in a near-miss like "HH" (still one letter of progress banked); HHH's prefixes never survive a miss because any wrong flip after partial progress destroys the whole run. More self-overlap means partial credit survives failure more often, which means less re-accumulating from scratch, which means a shorter expected wait.

The transferable technique

Waiting-time-for-a-pattern problems are first-step conditioning with one extra step: your states are "longest prefix of the target currently matched," not just a flip count, and the crucial modeling question for each transition is "does a near-miss preserve any partial progress, or does it wipe the slate?" Draw the pattern's own prefixes against its own suffixes before writing a single equation — that overlap table tells you exactly where each failed flip sends you, and the rest is the same linear system you'd build for any first-step problem.