understanding probability theory... Infinite monkey theorem

[Ben90]

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.

To convince yourself you could write a program that terminates when you return to the origin and two out of three runs your program will run forever.

I didn't realize you were alive in the year infinity B.C. Otherwise your program hasn't gone through infinite iterations yet.

 

[TuxDave]

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.

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.

 

[TuxDave]

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.

 

[Ben90]

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.

 

[Harvey]

Originally posted by: sao123
The infinite monkey theorem states that:

due to the nature of infinity, a monkey hitting keys at random on a typewriter keyboard will almost surely eventually type out the collected works of William Shakespeare.
(or type every book in France's Bibliothèque nationale de France (National Library). as it was said in the original version)

I thought I had a pretty intuitive view of probability in practice (theory escapes me however) but this just seems almost impossible to me.

Need explaination.

Simple. You're unable to comprehend the concept of infinity.

But given an infinite amount of time, he will... shortly after he finishes typing all of that Shakespear text. :biggrin:

 

[TuxDave]

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.

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.

 

[BurnItDwn]

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.

 

[jimhsu]

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.

 

[nOOky]

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?

 

[serpretetsky]

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?

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.

 

[BurnItDwn]

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.

Every possibility is guaranteed if you have an "infinite" amount of time.

 

[nOOky]

So that would include it not happening ; )

 

[serpretetsky]

Every possibility is guaranteed if you have an "infinite" amount of time.

So that would include it not happening ; )

:\. I'm pretty sure contradictions are usually a sign that the logic is incorrect.

 

[BurnItDwn]

:\. I'm pretty sure contradictions are usually a sign that the logic is incorrect.

Your logic and N00ky's logic are incorrect. That is true.

 

[serpretetsky]

i'm confused. You said every possibility is guaranteed given infinite time. That sentence is a contradiction.

 

[BurnItDwn]

i'm confused. You said every possibility is guaranteed given infinite time. That sentence is a contradiction.

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.

 

[TuxDave]

i'm confused. You said every possibility is guaranteed given infinite time. That sentence is a contradiction.

Which is why we have a contradiction because that statement is false.

 

[DrPizza]

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.

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.

 

[Chapbass]

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.

 

[nOOky]

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.

 

[Pray To Jesus]

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.

 

[sm625]

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.

 

[Paul98]

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.

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.

 

[BurnItDwn]

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.

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".

 

[intx13]

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.

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.