A monkey types letters uniformly and independently from a 26-letter alphabet. What is the expected number of keystrokes until the string ABRACADABRA first appears?

A monkey types letters uniformly and independently from a 26-letter alphabet. What is the expected number of keystrokes until the string ABRACADABRA first appears?

Approach: Put a gambler at every letter position, each staking a fair sequence of bets on the successive letters of the pattern, and apply optional stopping to the casino's total position.

26^11 + 26^4 + 26. At each time step a new gambler arrives and bets $1 at fair odds of 26 to 1 that the next letter is A, rolling any winnings onto the next letter of the pattern and leaving when a bet loses. Total wealth minus the number of gamblers who have arrived is a martingale, so optional stopping at the completion time T gives E[T] equal to the expected total holdings at that moment. When the pattern completes, the gambler who started 11 letters back holds 26^11, the one who started 4 letters back holds 26^4 because ABRA is both a prefix and a suffix, and the one who started on the last A holds 26. Pattern overlap is the whole content of the two extra terms, so E[T] = 3670344487444778.

Follow-up: What is the expected wait for a pattern of length 11 that has no self-overlap at all?

Key concepts: martingale, optional stopping, pattern overlap, fair odds.