Markov chain approach for expected amount of time when the monkey types a sequence.

Question

There is a monkey which every second picks a letter uniformly from the 26 letters of the English alphabet $\mathcal A$ and hits the key corresponding to that letter. He starts at time 0.

Question. What is the expected amount of time when the monkey first hits the sequence $AB$?

I want to see if this can be done via a Markov chain approach.

Suppose we have the state space $S$ as the set of all the pairs $\{xy:\ x, y\in \mathcal A\}$. So $S=\{AA, AB, AC, ..., BA, BB, BC, ...\}$. There is a natural natural graph on this state space. We join an (directed) edge between $xy$ and $yz$ for all $x, y, z\in \mathcal A$. The symmetry of the graph gives that the uniform distribution $\pi$ is the stationary distribution.

I basically want to know the following: Suppose it is given that the starting distribution is $\pi$ (the uniform distribution), then what is the expected time when one reaches the state $AB$.

(I realize that this is slightly different that the question I originally posed but this is good enough for me.)

Is there some general theorem about the expected time of reaching a particular state? At least for regular graphs?

Answer 1

This is a general theorem for when you have a random stream of i.i.d. uniform letters from a finite alphabet, and you want the expected time it takes for a particular word to appear consecutively.

Theorem: Let $X_1,X_2,\dots$ be i.i.d. uniformly distributed over a finite set $\Sigma$, with $|\Sigma|=m$. Let $w$ be a word of length $k$ with letters in $\Sigma$, so $w\in \Sigma^k$, and let $T=\inf \{t:(X_{t-k+1},X_{t-k+2},\dots,X_t)=w\}$ be the first time $w$ appears consecutively in $(X_i)_{i\ge 1}$.

$E[T]$ can be computed as follows. For each $1\le i\le k-1$, let $b_i$ equal $1$ if the substring of the first $i$ letters of $w$ equals the substring of the last $i$ letters of $w$, and let $b_i$ equal $0$ otherwise. Then

$$E[T]=m^k + \sum_{i=1}^{k-1}b_i m^i.$$

For example, with $w=AB$, since $A$ does not equal $B$, the expected time to see $AB$ is $26^2$. If you were instead waiting for $AA$, then the substring $A$ does equal $A$, so the expected wait time increases to $26^2+26$.

For a delightful proof of this theorem, see Expected number of consecutive guesses to get a given sequence of numbers.

Answer 2

Let $\mu$ denote the expectation if we start in a state where letter A was not the last typed letter.

Let $\nu$ denote the expectation if we start in a state where letter A was the last typed letter.

To be found is $\mu$ and we have the equalities:

• $\mu=\frac{25}{26}(1+\mu)+\frac1{26}(1+\nu)=1+\frac{25}{26}\mu+\frac1{26}\nu$
• $\nu=\frac{24}{26}(1+\mu)+\frac1{26}(1+\nu)+\frac1{26}1=1+\frac{24}{26}\mu+\frac1{26}\nu$

This leads to $\nu=25\cdot26$ and $\mu=26^2$.

Answer 3

One can compute expected hitting times using renewal theory. Specifically, if $P$ is the row-stochastic transition probability matrix then you have a linear system $((P-I)u)(x)=-1$ for $x$ other than the absorbing state(s) and $u(x)=0$ for the absorbing state(s). Here $I$ is just the identity matrix. Then $u(x)$ is the expected time to absorb starting from $x$, which you can then weight against whatever initial distribution you like.

In your case you can do this with a three state chain:

1. You've absorbed already
2. The previous letter wasn't A (or doesn't exist) and you haven't absorbed yet
3. The previous letter was A and you haven't absorbed yet

The natural way to study this problem using a Markov chain is to deterministically start in state 2 and wait for absorption into state 1.

This is really just a way of writing down the total expectation formula for each step, in combination with the Markov property and the homogeneity of the process. The funny "-1" is just the result of moving the "1" that represents "each time step consumes 1 time unit" to the right side of the equation.