June 27, 2013

A colleague of mine asked me what if we wanted to know the expected time for the monkey to type the sequence of letters ABCDEFGHIJK and not ABRACADABRA what would the result be. Trudging through the mathematics gives $$\mathbb E[T] =26^{11}$$. Why is the expected time for the monkey to type ABRACADABRA longer than to type ABCDEFGHIJK even though the probability to get either in the next 11 keystrokes is $$\frac{1}{26}^{11}$$? The simple answer is there are less ways to get ABRACADABRA for the first time in a sequence (if it is long enough). Consider a sequence of length 22. If we look at the number of ways of getting ABCDEFGHIJK from position 12.
\begin{align*}
???????????ABCDEFGHIJK
\end{align*}
Each question mark can be any letter of the alphabet except the sequence ABCDEFGHIJK hence there are $$26^{11} – 1$$ ways to achieve this. Now lets consider the corresponding situation for ABRACADABRA.
\begin{align*}
$$26^4$$ possible combinations. Also the immediately preceding letters can’t be ABRACADABR for the same reason so that rules out 26 more possible combinations.