Stopping times and typing monkeys

536 Views Asked by At

This is a question about the "standard solution" in this question: Let $(X_t)_{t\in\mathbb{N}}$ be the stochastic process modeling a monkey who types a random letter (uniform distribution) of the 26 letters $\{\texttt{A},\ldots, \texttt{Z}\}$ each second. We define the $\tau := \inf\,\{t\in\mathbb{N} : X_{t-10} = \texttt{A}, X_{t-9} = \texttt{B}, \ldots, X_t = \texttt{A}\}$ (first occurrance of $\texttt{ABRACADABRA}$) and want to calculate $\Bbb{E}[\tau]$.

Now my question is if $S_t$ is the win of all the gamblers till time $t$, why can we set (this is the crucial step) $\Bbb{E}[S_\tau] = \Bbb{E}[S_0] = 0$? Why is $\tau$ a bounded stopping time?

1

There are 1 best solutions below

0
On BEST ANSWER

$\tau$ is a stopping time, almost surely finite, but it's not bounded. But there are variants of the Optional-Stopping Theorem that don't require $\tau$ to be bounded. For example, if a martingale $\{M_n\}$ has bounded increments and $T$ is a stopping time with $ET<\infty$, then $EM_T=EM_0$. The argument I've seen for the ABRACADABRA problem employs this version of the OST.

Why is $ET$ finite for the typing monkey? If the string you want the monkey to type has length $k$, then $P(T>kn)\le (1-\varepsilon)^n$ for some $\varepsilon>0$, since $T>kn$ implies that for sure the string wasn't seen starting at keystroke 1, nor $k$ keystrokes later, $\ldots$, nor at keystroke $(n-1)k+1$; these latter $n$ events are independent with the same non-unit probability.