The ABRACADABRA Problem

How many random letter draws, on average, until you've seen the sequence "ABRACADABRA" appear as a run? Working this out by tracking every possible partial match by hand is painful. The martingale trick reframes the problem as a fair casino game, and the answer falls out almost by inspection.

The trick

Imagine a new gambler arrives before every letter draw and bets $1 that the next letters spell out "ABRACADABRA" starting right now, at fair odds (so a correct guess on a $k$-letter alphabet pays $k$ times the stake at each successive correct letter, and the gambler reinvests all winnings on the next letter). Every gambler's bet is a fair game, so the casino's expected profit is always zero regardless of when you stop. Stop at the first moment the target string has just appeared. The expected total money the casino has taken in equals the expected number of gamblers who have played, which is the expected stopping time — and the casino's winnings at that stopping instant can be computed directly from the overlaps in the target word with its own prefixes.

Worked example

For an 11-letter word over a 26-letter alphabet, the expected number of draws equals $\sum 26^k$ summed over every length-$k$ prefix of the word that is also a suffix of the word (including $k = 11$, the whole word). "ABRACADABRA" has two such self-overlaps: the whole word ($k=11$) and the prefix "A" which equals the suffix "A" ($k=1$). The expected number of draws is $26^{11} + 26^1$ — a huge number dominated by the $26^{11}$ term, with the small $26^1$ correction coming entirely from that one-letter self-overlap.