ABRACADABRA: Part 2

| June 26, 2013 | 0 Comments


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

ABACADABRA: Part 3 (Comment)

Tags:

Category: Probability, Quant Puzzles

Leave a Reply

Password Reset
Please enter your e-mail address. You will receive a new password via e-mail.