


02202013, 05:36 AM

#76

Platinum Member
Join Date: Jun 2009
Posts: 2,773

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.
Quote:
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.
Last edited by Ben90; 02202013 at 05:51 AM.



02202013, 10:16 AM

#77

Lifer
Join Date: Oct 2002
Posts: 10,291

Quote:
Originally Posted by 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.
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=...walkconstants
Don't kill the messenger.
__________________
post count = post count + 0.999.....
(\__/)
(='.'=)This is Bunny. Copy and paste bunny into your
(")_(")signature to help him gain world domination.



02202013, 10:47 AM

#78

Lifer
Join Date: Oct 2002
Posts: 10,291

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.
__________________
post count = post count + 0.999.....
(\__/)
(='.'=)This is Bunny. Copy and paste bunny into your
(")_(")signature to help him gain world domination.
Last edited by TuxDave; 02202013 at 10:56 AM.



02202013, 12:13 PM

#79

Platinum Member
Join Date: Jun 2009
Posts: 2,773

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.



02202013, 12:21 PM

#80

Administrator Elite Member
Join Date: Oct 1999
Location: Sherman Oaks, Ca.
Posts: 34,097

Quote:
Originally Posted by Looney
Quote:
Originally posted by: sao123
The infinite monkey theorem states that:
Quote:
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.
__________________
There are traitors and terrorists among us. They call themselves "Republicans." They are a greater threat to the U.S. than Al Qaeda and all the Al Qaeda wannabes. They have infested our democratic institutions with the sole objective of thwarting the will of the majority of our citizens.
And Whos's Watching Over Who's Watching Over You?
Tell me, who's telling who's telling you what to do what to do?



02202013, 12:42 PM

#81

Lifer
Join Date: Oct 2002
Posts: 10,291

Quote:
Originally Posted by 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.

There's definitely a nonzero 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.
__________________
post count = post count + 0.999.....
(\__/)
(='.'=)This is Bunny. Copy and paste bunny into your
(")_(")signature to help him gain world domination.



02212013, 02:39 PM

#82

Lifer
Join Date: Oct 1999
Location: Wauconda, IL
Posts: 18,282

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



02232013, 05:53 PM

#83

Senior Member
Join Date: Mar 2009
Posts: 692

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)
 = 1p
(number of possible random walks)
Which ends up being 1, for both the 1D and 2D cases.
Yes, infinities are weird.



02272013, 10:53 AM

#84

Senior Member
Join Date: Aug 2004
Posts: 752

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?
__________________
System 1: i72600K @ 4.4GHz, Asus P8P67 PRO, 2X8 GSKILL DDR3 1600, Hyper 212+, Sapphire 7970, Samsung 840 Pro 256GB  Win 8 Pro, Kingston HyperX 3K 120GB  Windows 7, all in a HAFX with an Asus VW266H.
System 2: FX6300 @ 4.5, Asus M5A97 R2.0, 2 x 4 GSkill 1600, Corsair Force GT 180  Windows 8, HD6870, 32" Panasonic monitor 1080p.
System 3: Asus laptop, Windows 8. Intel 160GB SSD, G50VtX5.



02272013, 12:23 PM

#85

Senior Member
Join Date: Jan 2012
Posts: 423

Quote:
Originally Posted by 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?

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.



02272013, 12:47 PM

#86

Lifer
Join Date: Oct 1999
Location: Wauconda, IL
Posts: 18,282

Quote:
Originally Posted by serpretetsky
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.



02272013, 01:01 PM

#87

Senior Member
Join Date: Aug 2004
Posts: 752

So that would include it not happening ; )
__________________
System 1: i72600K @ 4.4GHz, Asus P8P67 PRO, 2X8 GSKILL DDR3 1600, Hyper 212+, Sapphire 7970, Samsung 840 Pro 256GB  Win 8 Pro, Kingston HyperX 3K 120GB  Windows 7, all in a HAFX with an Asus VW266H.
System 2: FX6300 @ 4.5, Asus M5A97 R2.0, 2 x 4 GSkill 1600, Corsair Force GT 180  Windows 8, HD6870, 32" Panasonic monitor 1080p.
System 3: Asus laptop, Windows 8. Intel 160GB SSD, G50VtX5.



02272013, 01:08 PM

#88

Senior Member
Join Date: Jan 2012
Posts: 423

Quote:
Originally Posted by BurnItDwn
Every possibility is guaranteed if you have an "infinite" amount of time.

Quote:
So that would include it not happening ; )

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



02272013, 04:10 PM

#89

Lifer
Join Date: Oct 1999
Location: Wauconda, IL
Posts: 18,282

Quote:
Originally Posted by serpretetsky
. 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.



02272013, 05:01 PM

#90

Senior Member
Join Date: Jan 2012
Posts: 423

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



02272013, 05:20 PM

#91

Lifer
Join Date: Oct 1999
Location: Wauconda, IL
Posts: 18,282

Quote:
Originally Posted by serpretetsky
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.



02282013, 04:01 PM

#92

Lifer
Join Date: Oct 2002
Posts: 10,291

Quote:
Originally Posted by serpretetsky
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.
__________________
post count = post count + 0.999.....
(\__/)
(='.'=)This is Bunny. Copy and paste bunny into your
(")_(")signature to help him gain world domination.



02282013, 07:01 PM

#93

Administrator Elite Member Goat Whisperer
Join Date: Mar 2001
Location: Western NY
Posts: 43,112

Quote:
Originally Posted by 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 45 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.



03012013, 09:56 AM

#94

Platinum Member
Join Date: May 2004
Location: Arlington Heights, IL
Posts: 2,526

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.



03012013, 08:33 PM

#95

Senior Member
Join Date: Aug 2004
Posts: 752

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.
__________________
System 1: i72600K @ 4.4GHz, Asus P8P67 PRO, 2X8 GSKILL DDR3 1600, Hyper 212+, Sapphire 7970, Samsung 840 Pro 256GB  Win 8 Pro, Kingston HyperX 3K 120GB  Windows 7, all in a HAFX with an Asus VW266H.
System 2: FX6300 @ 4.5, Asus M5A97 R2.0, 2 x 4 GSkill 1600, Corsair Force GT 180  Windows 8, HD6870, 32" Panasonic monitor 1080p.
System 3: Asus laptop, Windows 8. Intel 160GB SSD, G50VtX5.



04092013, 07:38 AM

#96

Diamond Member
Join Date: Mar 2011
Posts: 3,522

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.



04092013, 08:36 AM

#97

Diamond Member
Join Date: May 2011
Posts: 4,321

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.
__________________
I am looking for a cheap upgrade to my 3 year old computer.
AT forum member #1: Buy a 4770k
I am looking for a way to get 10 more fps in TF2.
AT forum member #2: Buy a 4770k



04092013, 09:35 AM

#98

Platinum Member
Join Date: Jan 2010
Posts: 2,705

Quote:
Originally Posted by 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.

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.



04092013, 10:43 AM

#99

Lifer
Join Date: Oct 1999
Location: Wauconda, IL
Posts: 18,282

Quote:
Originally Posted by DrPizza
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".



04112013, 09:22 PM

#100

Member
Join Date: Apr 2013
Posts: 33

Quote:
Originally Posted by 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.

Actually, the only requirement is that the monkey's keyhittingsequence adheres to a distribution for which every event has a nonzero 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.



Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 05:09 PM.
