How can we solve the Infinite Monkey problem using gambling monkeys?

[Firepanda]

I would have thought this would just be 26¹¹ (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

 

[Ray Vickson]

I would have thought this would just be 26¹¹ (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

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 u_n = 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

 

[Dick]

There is also a really cute trick solution of this using gambling monkeys. http://complexzeta.wordpress.com/2008/02/08/martingale-monkeys/