understanding probability theory... Infinite monkey theorem

Discussion in 'Highly Technical' started by sao123, May 1, 2006.

  1. Ben90

    Ben90 Platinum Member

    Joined:
    Jun 14, 2009
    Messages:
    2,866
    Likes Received:
    0
    I'm having a hard time believing that a three dimensional random walk won't eventually lead back to the origin (infinite times). Just as a monkey will type any finite length string infinite times, any trip back to the origin is just a string of directions. I don't see how adding dimensions changes anything. Even if our monkey is at the edge of the observable universe, he has a nonzero chance of traveling the roughly 10^60 planck lengths forward in dimension 1, 10^60 planck lengths forward in dimension 2, 10^60 planck lengths backwards in dimension 3. In fact our monkey has a nonzero chance of traveling back taking the exact same route with all the whoopty swirls that led him out there to begin with.

    I didn't realize you were alive in the year infinity B.C. Otherwise your program hasn't gone through infinite iterations yet.
     
    #76 Ben90, Feb 20, 2013
    Last edited: Feb 20, 2013
  2. TuxDave

    TuxDave Lifer

    Joined:
    Oct 8, 2002
    Messages:
    10,577
    Likes Received:
    1
    What. You haven't seen the end of infinity yet? Get to work!

    But seriously, that's what makes it surprising. I'm not making the claim or making the proof. I'm reiterating what has already been proven and its surprising that you will not go back home an infinite number of times.

    http://www.ngorski.com/index.php?id=polyas-random-walk-constants

    Don't kill the messenger. :p
     
  3. TuxDave

    TuxDave Lifer

    Joined:
    Oct 8, 2002
    Messages:
    10,577
    Likes Received:
    1
    While I can't regurgitate the proof with full understanding, I can say something regarding your analogy on monkeys on typewriters.

    1 monkey, infinite time. The probability of a monkey eventually typing out the works of Shakespeare = 100%. It'll probably look like ...[garbage]Shakespeare's Works[garbage]...

    The probability of a monkey getting it right without typos is pretty damn close to zero and once you screw up the first letter, infinite time isn't going to help him.
    However, the probability of infinite number of them trying even in a finite period of time gets you back to 100%.

    So back to the drunk walk problem. If we say typing on a typewriter is a walk in 13 dimensions where A is the opposite of Z and B is the opposite of Y etc...

    The probability of visiting a spot he's been before = 100% and it'll be like the first monkey problem.

    ...[random junk]AABZYZ[random junk]...

    But the problem is a little different. It's not the probability of visit SOME spot that he's been before. It's the probability of getting home which means you start counting from the beginning. The probability is definitely higher than typing Shakespeare without typos since there's many ways to get back home and only one way of typing something out. If I had to guess how the proof worked (or at least my naïve way of approaching it), you have to take an even number of steps to get home.

    P(2) = probability of walking home after two steps (up/down + down/up etc...)
    P(4) = 4 steps...
    etc....

    And if you add it all the probabilities up to infinity and it doesn't equal 1.... then you have the surprise. So I guess if you send a robot out into space and let it go in random directions, you're not guaranteed it'll visit a specific point in space... that is.. unless you unleash an infinite number of them.
     
    #78 TuxDave, Feb 20, 2013
    Last edited: Feb 20, 2013
  4. Ben90

    Ben90 Platinum Member

    Joined:
    Jun 14, 2009
    Messages:
    2,866
    Likes Received:
    0
    I'll try not to shoot the messanger, I am just having a hard time creating a limit for infinity. I do understand the differences between writing out the works of shakespear and a random walk whose "answer" changes every iteration.

    It doesn't matter how many steps the walk goes through, there is always going to be a solution to get back to the starting point no matter how many dimensions there are. Even though the probability decreases as the monkey takes more steps, there will always be a chance to go one step closer in the right direction. Get lucky enough times and you are back home.

    Something that I feel relates is the .999... = 1 conundrum. I do feel this is different because no matter how long into the sequence the monkey is, it has only taken a finite amount of steps and always has a nonzero chance of getting home.
     
  5. Harvey

    Harvey Administrator<br>Elite Member
    Administrator

    Joined:
    Oct 9, 1999
    Messages:
    35,040
    Likes Received:
    3
    But given an infinite amount of time, he will... shortly after he finishes typing all of that Shakespear text. :biggrin:
     
  6. TuxDave

    TuxDave Lifer

    Joined:
    Oct 8, 2002
    Messages:
    10,577
    Likes Received:
    1
    There's definitely a non-zero probability of taking the minimum number of steps to get straight back home from where you are. And if you had infinite tries from that same spot, you are guaranteed to get home. But for every wrong step you take, you have to add an additional correct step later. With more degrees of freedom, you require more perfect balance of right and wrong steps in all directions at the same time. It's definitely a surprise conclusion for 3 or more dimensions. That's why this thread reminded me of it when someone said after infinite amount of time, everything is possible an infinite number of times.
     
  7. BurnItDwn

    BurnItDwn Lifer

    Joined:
    Oct 10, 1999
    Messages:
    21,802
    Likes Received:
    12
    You know, these numbers are fvckin crazy.


    Looks like early/1st gen commercially successful keyboards have 44 keys (43 various characters and shift...)

    Given 43 possible keys, or 43 key+shift combinations .... there's 86 posibillities. At 80,000 or so characters long (around 18000 words, asuming 4-5 characters per word avg.)

    1/86 to the 80,000 pwr ...


    Odds are 1 out of 7.517~ * 10 ^ 154759 posibillities

    That's a number 154760 digits long.


    Assuming a monkey can type 1 character per second. that's about 22 hours for 1 *copy* of macbeth.
    Theres about 8766 hours per year (24 per day * 365 + 6 to factor in leap year)

    Thus a monkey can type 80000 characters about 400 times in a year.

    Thus, each year, the monkey could try out approx ONE per every (1.879~ * 10 ^ 154757 possibilites)


    If you had a million monkeys, and a million years ...
    You would only try out one per every (1.879~ * 10 ^ 154745) posibillities

    If you had a million groups of a million teams of a million monkeys and gave them a million years

    you would only have gone through one out of every 1.879 * 10 ^ 154733 posibillities.


    If you had a million groups of a million teams of a million monkeys and they have been working nonstop for 10 billion years.
    You would have gone through one out of every 1.879 * 10 ^ 154729 posibillities.


    If you had a Billion universes in your multiverse, and in each universe,
    you had a billion teams of a billion groups of a billion monkeys,
    and they all entered characters at the rate of 1 per second for 24 hours every day for 10 billion years,
    then you would have covered approximatly one out of every 1.879 * 10 ^ 154717 possibilities.
     
  8. jimhsu

    jimhsu Senior member

    Joined:
    Mar 22, 2009
    Messages:
    703
    Likes Received:
    0
    The thorny issue is that even for 1D and 2D random walks, there are an infinite number of *possible* random walks that do not lead back to the origin. Consider the random walk with a path of x(N+1) = x(N) + 1; the probability of such a random walk is infinitely small (in fact, the probability of any specific infinite walk occurring is also infinitely small). Thus, you have:

    (number of random walks that don't go to zero)
    ------------------------------------------------------ = 1-p
    (number of possible random walks)

    Which ends up being 1, for both the 1D and 2D cases.

    Yes, infinities are weird.
     
  9. nOOky

    nOOky Senior member

    Joined:
    Aug 17, 2004
    Messages:
    871
    Likes Received:
    1
    If, given an infinite period of time, a monkey randomly banging away on a keyboard will type out Shakespeare's works is a possibility, there must also exist the possibility that the monkey will also never hit upon the correct combination even given an infinite amount of time, correct?
     
  10. serpretetsky

    serpretetsky Senior member

    Joined:
    Jan 7, 2012
    Messages:
    549
    Likes Received:
    0
    Well, this thread is saying that it's not a possibility, but that it is guaranteed.

    But yes, i agree that those are the two possibilies, the monkey can either write out shakespeare's work, or not.
     
  11. BurnItDwn

    BurnItDwn Lifer

    Joined:
    Oct 10, 1999
    Messages:
    21,802
    Likes Received:
    12
    Every possibility is guaranteed if you have an "infinite" amount of time.
     
  12. nOOky

    nOOky Senior member

    Joined:
    Aug 17, 2004
    Messages:
    871
    Likes Received:
    1
    So that would include it not happening ; )
     
  13. serpretetsky

    serpretetsky Senior member

    Joined:
    Jan 7, 2012
    Messages:
    549
    Likes Received:
    0
    :\. I'm pretty sure contradictions are usually a sign that the logic is incorrect.
     
  14. BurnItDwn

    BurnItDwn Lifer

    Joined:
    Oct 10, 1999
    Messages:
    21,802
    Likes Received:
    12
    Your logic and N00ky's logic are incorrect. That is true.
     
  15. serpretetsky

    serpretetsky Senior member

    Joined:
    Jan 7, 2012
    Messages:
    549
    Likes Received:
    0
    i'm confused. You said every possibility is guaranteed given infinite time. That sentence is a contradiction.
     
  16. BurnItDwn

    BurnItDwn Lifer

    Joined:
    Oct 10, 1999
    Messages:
    21,802
    Likes Received:
    12
    That depends on what you define a possibility.
    Each possible 80000 character long string is a possibility. All possibilities, including the one which results in Shakespeare's work are inevitable.

    Shakespeare's work not happening is not a possibility, because it is impossible given an infinite amount of time and true randomness.
     
  17. TuxDave

    TuxDave Lifer

    Joined:
    Oct 8, 2002
    Messages:
    10,577
    Likes Received:
    1
    Which is why we have a contradiction because that statement is false.
     
  18. DrPizza

    DrPizza Administrator Elite Member Goat Whisperer
    Administrator

    Joined:
    Mar 5, 2001
    Messages:
    49,629
    Likes Received:
    153
    Your logic is flawed, because you assume you're going to check again after 80,000 characters. If the first character was wrong, there's nothing that says MacBeth wouldn't be the 1st through 80,001th character. Or the 2nd through 80,002nd characters, etc.
     
  19. Chapbass

    Chapbass Platinum Member

    Joined:
    May 31, 2004
    Messages:
    2,913
    Likes Received:
    1
    The problem with using "monkey typing on a keyboard" is that when people imagine monkeys banging on a keyboard they don't imagine a truly random scenario. For example, a "typical" monkey banging on a keyboard will never push just a single key in a "section" on the keyboard. They'll hit half the keyboard at once. Knowing this, it will almost always type out multiple keys in a single section with each "keystroke". Even if this only happens once in every 10 keystrokes, then the monkey will never reproduce a sort of novel no matter how much the time.

    Much more accurate example would be a computer randomly picking out letters, becuase that could be much more "random", where as an actual monkey scenario isn't actually random.

    Granted I'm rambling and I skipped pages 2 and 3, so this could've been mentioned already.
     
  20. nOOky

    nOOky Senior member

    Joined:
    Aug 17, 2004
    Messages:
    871
    Likes Received:
    1
    Exactly what I was thinking. Mathematically the concept is 100% correct given truly random entry on the key board. But the factor is the monkey typing on a key board, which may not be a good example. Because, even given an infinite time period, there is still a chance that the monkey will never type that sequence, ever. Ever.
     
  21. Pray To Jesus

    Pray To Jesus Diamond Member

    Joined:
    Mar 14, 2011
    Messages:
    3,642
    Likes Received:
    0
    Have fun playing with infinite time. Its good to learn about our universe and find out if time and space is infinite, and the reason that we believe so.
     
  22. sm625

    sm625 Diamond Member

    Joined:
    May 6, 2011
    Messages:
    7,767
    Likes Received:
    22
    It is a bullcrap theory. A trillion trillion monkeys pounding away at a trillion trillion keyboards for a trillion trillion years will never ever type even one page of shakespeare. There is just no way no matter what the general probability stat says. There are many reasons for this. One is the simple fact that monkeys do not and cannot mash keys in a truly random fashion. There are too many nonrandom key combinations required to be pressed in order to ever assemble anything legible. And since all it takes is one mistake to ruin the page, the page will never get complete. No matter what the raw statistic says, the real probability is zero. Think of it as a sort of hysteresis.
     
  23. Paul98

    Paul98 Diamond Member

    Joined:
    Jan 31, 2010
    Messages:
    3,533
    Likes Received:
    3
    It is given that the monkeys are hitting random keys.

    trillion trillion might as well be 0 compared to infinity. You can calculate the probability that a page, or book will be typed. You can calculate how long it would take to give a good probability.

    But I don't really like these type of ways to try and think of infinity, as these monkeys will never type infinite characters. No matter how long you wait it won't be an infinite amount of time.
     
  24. BurnItDwn

    BurnItDwn Lifer

    Joined:
    Oct 10, 1999
    Messages:
    21,802
    Likes Received:
    12
    Thanks Doc

    That essentially takes away several orders of magnitude from the total number of posibillities.

    Still, the scale of the numbers are so many digits long, that it's well beyond my "scale comprehension".
     
  25. intx13

    intx13 Member

    Joined:
    Apr 3, 2013
    Messages:
    33
    Likes Received:
    0
    Actually, the only requirement is that the monkey's key-hitting-sequence adheres to a distribution for which every event has a non-zero probability. It doesn't have to be a uniform distribution. As long as we're assuming that a monkey can type for all eternity, we might as well assume he'll hit every key sooner or later and that he's not following a pattern.

    Another way to visualize the concept is that everything a monkey types has meaning in some made up language. An infinite number of languages can be defined for any alphabet.
     
Loading...