# ABRACADABRA: Part 2

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\)

**Category**: Probability, Quant Puzzles