Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite Monkey problem

  1. Jan 4, 2012 #1

    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?

  2. jcsd
  3. Jan 5, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
    [tex] (1/26)^{11} = u_n + (1/26)^7 u_{n-7} + (1/26)^{10} u_{n-10}. [/tex]
    The process is "aperiodic", so [itex] \lim_{n \rightarrow \infty} u_n = 1/\mu[/itex] exists, where μ is the mean time between renewals = mean time to first renewal. So, we have
    [tex] (1/26)^{11} = (1/\mu)[1 + (1/26)^7 + (1/26)^{10}], [/tex]
    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.

  4. Jan 5, 2012 #3


    User Avatar
    Science Advisor
    Homework Helper

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook