June 26, 2013

To answer the question what is the expected time for a monkey to type ABRACADABRA, assuming he types the letters of the alphabet randomly at times 1,2,3,… rigorously we will need to use a theorem from discrete martingale theory, Doob’s Optional Stopping Theorem.
This theorem states sufficient conditions for a stopped martingale to have the same expectation as its starting value.

Let $$X^j_i$$ denote the wealth of the jth gambler at time i
\begin{align*}
X_i^j =1 \; \text{if $i < j$,}
\end{align*}

otherwise if $$i \geq j$$,
\begin{align*}
X_i^j =
\begin{cases}
26^{i-j+1} \mathbb \;\text{with prob} \; p = {\frac{1}{26}}^{i-j+1} \;
\\
0 \mathbb \;\text{with prob} \; 1- p \;
\end{cases}
\end{align*}
Clearly $$X^j_i$$ is a martingale with expectation 1. Lets define the martingale starting from 0 $$M_n = \sum_{j = 1}^{j = n} X_n^j – n$$
If we can show that $$\mathbb E[M_T] = \mathbb E[M_0]$$ then the rest follows. This is where we invoke Doob’s Optional Stopping Theorem.
which gives us sufficient conditions. Showing  that $$\mathbb E[T] < \infty$$ and the increments $$M_n – M_{n-1}$$ are bounded is sufficient.

1. $$\mathbb E[T] < \infty$$

To prove this we use a lemma from page 101 of Probability with Martingales.

Suppose that $$T$$ is a stopping time such that for some $$N$$ in $$\mathbb N$$ and some $$\epsilon \geq 0$$, we have, for every n in $$\mathbb N$$:
\begin{align*} \mathbb P(T\leq n+N | \mathcal F_n) > \epsilon, a.s \end{align*}
Then $$\mathbb E[T] \leq \infty$$

In our problem we take $$N = 11$$ and the probability of the monkey typing ABRACADABRA in the next 11 keystrokes gives us a  value for $$\epsilon$$. We take $$\epsilon \; < \frac{1}{26}^{11}$$

2. $$|M_n(\omega) – M_{n-1}(\omega)| \leq K \; \forall (n,\omega)$$

The largest value attainable by $$M_n$$ is $$26^{11} +26^4 + 26$$ so the increments are bounded.

Hence at the stopping time $$T$$ we know that $$\mathbb E[M_T] = 0$$ from which follows $$\mathbb E[T] = 26^{11} +26^4 + 26$$