Solving Waiting-Time Puzzles With Optional Stopping

You already know one way to find the expected wait for a coin pattern like HTH: set up states, write a linear system, solve it. That works, but it gets messy fast for longer patterns. There's a second method — the gambling-team trick — that gets the same answer for HTH in a few lines of arithmetic and no simultaneous equations at all. It's built on the optional stopping theorem, and once you see it, you'll never set up a state machine for these again if you don't have to.

Try to guess the trick before reading on: what if, instead of tracking states, you imagine people placing bets?

The trap: thinking martingale tools only apply to gambler's ruin

Optional stopping usually gets introduced through gambler's-ruin-style problems — a random walk, a stopping time, done. It's easy to miss that the same theorem, applied to a cleverly designed betting scheme, solves pattern-waiting problems directly, sidestepping the whole state-machine apparatus.

Building the machine: the fair-bet accounting

At each flip $t=1,2,3,\dots$, a new gambler arrives with $1 and bets it's about to see the pattern start. If the pattern is length $k$, a gambler who is still "alive" after $j$ correct flips has, fairly, turned their $1 into $2^j$ dollars (since each flip is a fair 50/50 bet and a fair game preserves expected value — betting $1 on a coin at 2-to-1 odds either doubles it or loses it, keeping expectation at $1). The moment a gambler's predicted flip is wrong, they lose their entire current stake.

Because every individual gambler is playing a martingale (a fair game), and the total money in play at the stopping time $T$ (the first time the pattern appears) is a stopped martingale, the optional stopping theorem says the casino's expected net take is zero: total dollars gamblers put in equals total dollars they have when the pattern finally appears, in expectation. Gamblers put in $1 at each of the $T$ flips, so the amount staked is exactly $T$ dollars. The payout side is computed pattern by pattern, using self-overlap exactly as before — but now it falls out of simple bookkeeping instead of a linear system.

Worked example: HH, checked against the known answer

At the stopping time, whichever gamblers are still "alive" collect based on how much of the pattern's suffix matches their own bet sequence. For HH (no internal overlap beyond the whole word), only the gambler who just arrived on the very last flip and the one from the flip before are still active when HH completes: the gambler who entered on the final flip has correctly called 1 flip, and the gambler who entered one flip earlier has correctly called both flips.

$$E[T] = \sum_{\substack{\text{suffixes of pattern that}\\ \text{are also prefixes of it}}} 2^{(\text{length of that suffix})}.$$

In words: sum $2^j$ over every way the pattern overlaps itself (including the trivial overlap of the whole pattern with itself). For HH, only the trivial full overlap ($j=2$, contributing $2^2=4$) and the single-letter overlap of "H" with itself ($j=1$, contributing $2^1=2$) exist — every prefix of HH is "H" and "HH," and both happen to also be suffixes of HH. Sum: $4+2=6$. $E[T] = 6$, matching the first-step-conditioning answer from the waiting-time page exactly.

Worked example: HTH, redone with almost no algebra

For HTH, check each prefix against the full pattern's suffix of the same length: the whole pattern HTH matches itself ($j=3$, contributes $2^3=8$); the length-1 prefix "H" also equals the length-1 suffix "H" ($j=1$, contributes $2^1=2$); the length-2 prefix "HT" does not equal the length-2 suffix "TH," so it contributes nothing.

$$E[T] = 2^3 + 2^1 = 8+2 = 10.$$

$E[T]=10$, matching the state-machine answer from the waiting-time page exactly, in three lines instead of a three-variable linear system.

The transferable technique

When a state-machine setup starts to feel unwieldy — long patterns, several overlapping prefixes — look for a betting scheme where each bettor's fortune is a martingale and the quantity you want (a waiting time) is exactly the stopping time. The optional stopping theorem then converts "solve a linear system" into "sum $2^j$ over self-overlaps," which is mechanical rather than algebraic. This is the same idea behind the ABRACADABRA problem and any "expected time until a specific string appears" question — recognise the martingale, and the answer is often a one-line sum.