# Infinite Monkey problem

1. Jan 4, 2012

### Firepanda

I would have thought this would just be 2611 (in whatever units) for the expected time taken, does anyone know where the other two terms come from?

Should my expectation be drawn from some kind of distribution?

Thanks

2. Jan 5, 2012

### Ray Vickson

You can view the process as a discrete-time renewal process, where a "renewal" occurs at time n if the last letter of "abracadabra" happens at time n. Following the logic in Feller, "Introduction to Probability Theory and Its Applications, Vol. I" (Wiley, 1968), pp. 323--328), let un = Pr{renewal occurs at time n}, and note that we have
$$(1/26)^{11} = u_n + (1/26)^7 u_{n-7} + (1/26)^{10} u_{n-10}.$$
The process is "aperiodic", so $\lim_{n \rightarrow \infty} u_n = 1/\mu$ exists, where μ is the mean time between renewals = mean time to first renewal. So, we have
$$(1/26)^{11} = (1/\mu)[1 + (1/26)^7 + (1/26)^{10}],$$
which gives you what you want. To really grasp what is going on you need to go and read Feller or some more modern books that deal with Renewal Theory.

Alternatively, you can set up a somewhat complicated Markov chain representation and compute a mean first-passage time. However, the renewal argument is much, much simpler---assuming you know what it is about in the first place.

RGV

3. Jan 5, 2012