The Straight Dope

Go Back   Straight Dope Message Board > Main > General Questions

Reply
 
Thread Tools Display Modes
  #1  
Old 01-21-2004, 07:06 PM
With Rye With Rye is offline
Guest
 
Join Date: Mar 2001
Odds concerning monkeys and the lottery

I am really awful when it comes to statistics and tend to stay away from rather than try to understand it. But this, of course, doesn't work and now I'm plagued with this annoying curiousity about everyday topics dealing with the topic I can't seem to ignore.

For instance, are the odds of a lottery machine popping out the numbers (in order) 1 2 3 4 5 6 the same as any other number sequence? Surely, "1" has an equal chance coming out for the first slot as any number, and "2" the second slot, and so on. Unless each slot has some sort of dependency on another slot to determine which number comes out, but I don't see how this can be. Or I am just ignorant of what's happening. I remember vaguely about "mutual exclusiveness" from high school but I still haven't made sense of it. I ask because my philosophy teacher told the class a lottery ticket with an ordered sequence is just as likely as a ticket with a seemingly random one to win (or lose, if you prefer).

If that is true, then won't the assertion that a roomful of monkeys typing away on typewriters will eventually produce Hamlet also hold? Each letter has an even chance of being struck (assuming nonbiased monkeys with no developed preference for certains key combinations, of course). Can we then say that event will just as likely happen as any other? That seems sort of...wrong, at least non-intuitive, to me.

ACK, deliver me!
__________________
Reply With Quote
Advertisements  
  #2  
Old 01-21-2004, 07:14 PM
aahala aahala is offline
Guest
 
Join Date: Mar 2002
Any sequence of numbers is just as likely(unlikely) as another. It's we, not the bin the balls are in, who place significance on the outcome.
Reply With Quote
  #3  
Old 01-21-2004, 07:23 PM
El Zagna El Zagna is offline
Guest
 
Join Date: Jan 2001
Quote:
Originally Posted by With Rye
For instance, are the odds of a lottery machine popping out the numbers (in order) 1 2 3 4 5 6 the same as any other number sequence?
Yep, and welcome to the boards.

Quote:
Originally Posted by With Rye
If that is true, then won't the assertion that a roomful of monkeys typing away on typewriters will eventually produce Hamlet also hold?
Yep, given an infinite number of monkeys or one monkey with an infinite amount of time.

Each of these questions seems to be trying to come to terms with some of the non-intuitive properties of very large numbers or very remote possibilities. When dealing with an infinite number of possibilities, things that appear unlikely become - not just likely - but certain.
__________________
No sig for me, thanks.
Reply With Quote
  #4  
Old 01-21-2004, 07:30 PM
Lockfist Lockfist is offline
Guest
 
Join Date: Jun 2001
Quote:
Originally Posted by With Rye
...

If that is true, then won't the assertion that a roomful of monkeys typing away on typewriters will eventually produce Hamlet also hold? Each letter has an even chance of being struck (assuming nonbiased monkeys with no developed preference for certains key combinations, of course). Can we then say that event will just as likely happen as any other? That seems sort of...wrong, at least non-intuitive, to me.

ACK, deliver me!
This was actually attempted (to a small degree) - see the results here. Back story here.
Reply With Quote
  #5  
Old 01-21-2004, 10:36 PM
Hermitian Hermitian is online now
Guest
 
Join Date: Jan 2004
Concerning the monkeys...

Concerning the monkeys, in "theory" it can happen, but in reality, no. I jumped on this question because I just recently worked a problem with monkeys and Hamlet in my statistics class.
(Note for the following: Yes I know typing out lots of zeros is not good scientific practice, but sometimes it helps get the idea across the magnitude of larger numbers.)
According the my statistics book, the chances of Hamlet being typed out by 10,000,000,000 monkey, hitting 10 keys per second, for the age of the universe, which is 1,000,000,000,000,000,000 seconds, would be:

1 against 10^164345

10^164345 is an awesomely hugely unfathomable number (Over 164,300 digits long!!). My books proceeds to state that the whole monkeys and Hamlet business is complete and utter "nonsense."
Reply With Quote
  #6  
Old 01-21-2004, 10:56 PM
Electronic Chaos Electronic Chaos is offline
Guest
 
Join Date: Nov 2001
*hands OP the Heart of Gold*
Reply With Quote
  #7  
Old 01-22-2004, 02:11 AM
Sublight Sublight is offline
Guest
 
Join Date: Aug 2000
As others have already said, the odds against randomly producing something as long as Hamlet are too big to be pictured in any practical way. Try thinking of it this way: a monkey hitting a typewriter (or a computer spewing out random letters, same thing) once every second will eventually produce your first name. If your name is Ed, the chance of a perfect match is 1 in 262, or 676, which means you'll probably see your name come out in only 10 minutes or so. If it's Bob, the chance is 1 in 263, or 17576, which will take a few hours. Dave (264, or 456976) will have to wait about 5 days. If your name is Yoshitsune, the chances are 1 in 2610, or 141167095653376, which means you'll have to wait roughly 4 million years for it to come up, but eventualy it will.
Reply With Quote
  #8  
Old 01-22-2004, 09:33 AM
muttrox muttrox is offline
Member
 
Join Date: Dec 2000
Posts: 2,026
Quote:
Originally Posted by Hermitian
My books proceeds to state that the whole monkeys and Hamlet business is complete and utter "nonsense."
Your books are categorically wrong. The premise is an *infinite* amount of monkeys, with *infinite* time. Your example uses finite numbers of monkey a finite time limit, completely different.
Reply With Quote
  #9  
Old 01-22-2004, 09:35 AM
muttrox muttrox is offline
Member
 
Join Date: Dec 2000
Posts: 2,026
Also note that even in your example, the monkeys did produce Hamlet, it just took a very very long time.
Reply With Quote
  #10  
Old 01-22-2004, 02:55 PM
ccwaterback ccwaterback is offline
Guest
 
Join Date: Jul 2003
What's the old saying? "There's lies, damn lies, and statistics". Any time you deal with statistics, you have to qualify your realm as either "practical" or "theory". For instance, the monkey example is so unlikely that in all practicality the probability is zero, but in theory, it can be done. In the classroom and academia, some results can be shown to be highly unlikely, but statistically possible. In engineering and the "real-world" most of those highly unlikely probabilities are "rounded" to zero.
Reply With Quote
  #11  
Old 01-22-2004, 03:28 PM
MikeS MikeS is offline
Charter Member
 
Join Date: Oct 2001
Location: Williamstown, MA
Posts: 3,224
But wouldn't an infinite number of monkeys immediately produce not only "Hamlet", but all the works of Shakespeare, and every other work of literature, past and future?
Reply With Quote
  #12  
Old 01-22-2004, 04:05 PM
SCSimmons SCSimmons is offline
Guest
 
Join Date: Mar 2001
http://www.brunching.com/randommonkeys.html
__________________
-Christian
"You won't like me when I'm angry. Because I always back up my rage with facts and documented sources." -- The Credible Hulk
Reply With Quote
  #13  
Old 01-22-2004, 04:08 PM
Chronos Chronos is online now
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 52,721
In fact, an infinite number of monkeys would not only produce every work of literature, past, present, and future, but they would produce an infinite number of copies of each.

Project Gutenberg's full text of Hamlet weighs in at 206 KB, at one byte per character. Assuming, for simplicity, that the only characters are the 26 letters of the alphabet, that means that the odds of a given 206,000 character sequence being Hamlet are 1 in 26206000, which is approximately 10291484. So if you had that many monkeys, you'd expect to get one copy of Hamlet out.
__________________
Time travels in divers paces with divers persons.
--As You Like It, III:ii:328
Reply With Quote
  #14  
Old 01-22-2004, 04:12 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
The probability that the monkeys will produce Hamlet is 1, but they are not guaranteed to do so. It's a feature of standard probability theory that, when there is an infinite number of possible outcomes, some events may have probability 0 and still occur.

There has been work in a non-standard probability theory where this doesn't happen, but it hasn't reached widespread acceptance yet.
Reply With Quote
  #15  
Old 01-22-2004, 04:32 PM
NurseCarmen NurseCarmen is offline
Member
 
Join Date: Mar 2002
Location: The Zen Arcade
Posts: 8,267
I always thought it was more of a commentary on infinity, so lay people could wrap their head around the immensity of it.

Either that, or it was a knock against Willy S.
__________________
Never trust the government. Trust the corporations even less.
Adams Trinity Hotel is the worst hotel in all of Ireland.
Reply With Quote
  #16  
Old 01-23-2004, 01:08 AM
Flash-57 Flash-57 is offline
Guest
 
Join Date: Nov 2003
See now, the question of monkeys and typewriters can be greatly simplified with a little bit of editing. Every time a monkey types a letter, check to see if the letter is the corrent next letter from Hamlet. If not, make the monkey erase the letter and type another.

Actually, you could create Hamlet pretty fast with just one monkey and a computer to erase incorrect characters.

And, you wouldn't need a monkey--a random number generator would work better. It wouldn't be that hard to write a simple script to test this theory.

Anyone know how many letters (include punctuation) in Hamlet?

Let's say there are 10,000 letters in Hamlet (a number I pulled from thin air). Each letter would need an average of 47 guesses (there are 94 characters on my keyboard) to guess it. So, that's about a half million guesses. My computer could do that in a day or so.
__________________
-- Flash-57
Reply With Quote
  #17  
Old 01-23-2004, 01:37 AM
Xema Xema is offline
Guest
 
Join Date: Mar 2002
Quote:
Originally Posted by Flash-57
See now, the question of monkeys and typewriters can be greatly simplified with a little bit of editing. Every time a monkey types a letter, check to see if the letter is the corrent next letter from Hamlet...

... that's about a half million guesses. My computer could do that in a day or so.
So we can expect to get Hamlet merely by providing a copy of Hamlet?

Impressive, sure, but perhaps not a miracle of modern technology.
Reply With Quote
  #18  
Old 01-23-2004, 06:00 AM
PookahMacPhellimey PookahMacPhellimey is offline
Guest
 
Join Date: Jul 2001
Quote:
Originally Posted by Sublight
If your name is Yoshitsune, the chances are 1 in 2610, or 141167095653376, which means you'll have to wait roughly 4 million years for it to come up, but eventualy it will.
I'm very bad at judging these things, but I wonder if it must necessarily come up in the given timeframe. Isn't this just and average and couldn't Yoshitsune be unlucky and have to wait much longer than the 4 million years?

Even more interesting is the question of whether the name Yoshitsune MUST come up given an eternity of random generating. Is it in the nature of what eternity is that this HAS to happen? Or is there a really really incredibly slim chance that "Yoshitsune" never comes up?
Reply With Quote
  #19  
Old 01-23-2004, 07:15 AM
pjd pjd is offline
Guest
 
Join Date: May 2003
Here is a link to a monkey shakespeare simulator ...
__________________
---------
Apples
Reply With Quote
  #20  
Old 01-23-2004, 11:12 AM
muttrox muttrox is offline
Member
 
Join Date: Dec 2000
Posts: 2,026
Quote:
Originally Posted by Flash-57
Actually, you could create Hamlet pretty fast with just one monkey and a computer to erase incorrect characters.
If you're going to change the rules, why stop there? Let's postulate a copy of Hamlet and and a xerox machine. Or a computer that has Hamlet as a word document... look, all I do is hit print!
Reply With Quote
  #21  
Old 01-23-2004, 11:57 AM
micco micco is offline
Guest
 
Join Date: Apr 2001
Quote:
Originally Posted by PookahMacPhellimey
I'm very bad at judging these things, but I wonder if it must necessarily come up in the given timeframe. Isn't this just and average and couldn't Yoshitsune be unlucky and have to wait much longer than the 4 million years?
It depends on the "randomness" of whatever is generating your output. With monkeys typing, you could be unlucky because they could produce the same wrong output many times before they got around to the right output. In other cases where you're systematically exhausting possibilities, you're guaranteed to hit the right output once before you hit the time limit because you never repeat anything.

This is a common metric for people who brute-force encryption keys. If you're systematically testing each encryption key, then you will eventually find it. You can't get unlucky and have to wait longer than your max limit because you design your algorithm not to repeat trials. In these cases, the rule of thumb is that you will probably find the right key when you've run through half the key space. You might have to test them all, but you might hit it in the first try. This measure of "likely" is only really relevant if you're trying to brute force a lot of keys and want an average requirement. Since you're going to hit some early and some late, your average requirement is testing half the possibilities.

On the otherhand, with monkeys typing there is no guarantee. Their quality control is notoriously lax.
Reply With Quote
  #22  
Old 01-23-2004, 12:04 PM
panamajack panamajack is offline
Guest
 
Join Date: Apr 2000
Quote:
Originally Posted by PookahMacPhellimey
I'm very bad at judging these things, but I wonder if it must necessarily come up in the given timeframe. Isn't this just and average and couldn't Yoshitsune be unlucky and have to wait much longer than the 4 million years?

Even more interesting is the question of whether the name Yoshitsune MUST come up given an eternity of random generating. Is it in the nature of what eternity is that this HAS to happen? Or is there a really really incredibly slim chance that "Yoshitsune" never comes up?
You're correct. No particular sequence must come up in a finite length of time. Even with an infinite amout of time, it isn't guaranteed (according to traditional probability theory). This was the point ultrafilter stated more formally.
Reply With Quote
  #23  
Old 01-23-2004, 12:16 PM
Flash-57 Flash-57 is offline
Guest
 
Join Date: Nov 2003
Quote:
Originally Posted by Xema
So we can expect to get Hamlet merely by providing a copy of Hamlet?

Impressive, sure, but perhaps not a miracle of modern technology.
True. I was changing the rules a bit. But then, you'd need a copy of Hamlet anyway to determine if one of the monkeys had actually recreated the play.

The initial argument seemed to be that enough randomness will eventually create any desired result. My addition of "guided randomness" will simply help randomness arrive at the final result much quicker.

Besides, you wouldn't really need a copy of Hamlet to help guide the monkeys along. Even some simple rules would speed things up considerably (such as tossing out a "v" that followed a "g" or a third "p" in a row).
__________________
-- Flash-57
Reply With Quote
  #24  
Old 01-23-2004, 12:56 PM
jk1245 jk1245 is offline
Guest
 
Join Date: Jul 2000
Couple of thoughts (I'm not a statistics guru):

1) How are the odds changed if you give the monkeys a keyboard with only 27 keys on it (letters plus a space bar)?

2) The odds are equally likely that they'd type Hamlet on their first try as any other, correct?

3) In the "Yoshitsune" example (gotta remember that name), the time given is the max, right? Is there any way to calculate the expected time? I would think that there is a 50% chance your name would be found in half the time. Is this correct?
Reply With Quote
  #25  
Old 01-23-2004, 01:14 PM
micco micco is offline
Guest
 
Join Date: Apr 2001
Quote:
Originally Posted by jk1245
1) How are the odds changed if you give the monkeys a keyboard with only 27 keys on it (letters plus a space bar)?
If you want to actually calculate the odds, you have define what character set you're using. If you allow the monkeys to type a lot of characters which aren't part of the desired output, the odds go up. If you limit them to the characters in the output you desire, the odds are better simply because you're excluding the possibility of characters which would contribute to a failure. Of course, if you're going to be picky about capitalization and punctuation, you're dealing with more than 27 characters, more like 56+ depending on the actual punctuation marks which appear in Hamlet.

Quote:
2) The odds are equally likely that they'd type Hamlet on their first try as any other, correct?
Yes.

Quote:
3) In the "Yoshitsune" example (gotta remember that name), the time given is the max, right? Is there any way to calculate the expected time? I would think that there is a 50% chance your name would be found in half the time. Is this correct?
See my earlier post. The time is the max if you're preventing the monkeys from ever duplicating their work. This requires highly trained monkeys with good memories. If you're restricting your trials so they're unique (no repeats) then, by definition, there is a 50% chance you'll hit in the first half of the trials.
Reply With Quote
  #26  
Old 01-25-2004, 08:54 AM
Sublight Sublight is offline
Guest
 
Join Date: Aug 2000
Quote:
Originally Posted by PookahMacPhellimey
I'm very bad at judging these things, but I wonder if it must necessarily come up in the given timeframe. Isn't this just and average and couldn't Yoshitsune be unlucky and have to wait much longer than the 4 million years?
You're absolutely right, the 4 million years was just a rough guess of about how long it would probably take, within an order of magnitude or so. It could take much longer, and there's no guarantee that it will happen in any finite amount of time.

Regarding ultrafilter's post: while it's true that given an infinite number of possible outcomes, there is a there is a chance that a particular outcome will never happen, even given an infinite amount of time, I don't think it applies here. If you just look at Hamlet-sized blocks of text (about 200,000 characters), then the number of possible samples is finite, though extremely large. Given an infinite amount of time, therefore, a perfect copy of Hamlet would have to come up at some point.

(My favorite short story is Library of Babel. Does it show?)
Reply With Quote
  #27  
Old 01-25-2004, 09:16 AM
Shade Shade is offline
Guest
 
Join Date: Oct 2001
Quote:
Regarding ultrafilter's post: while it's true that given an infinite number of possible outcomes, there is a there is a chance that a particular outcome will never happen, even given an infinite amount of time, I don't think it applies here. If you just look at Hamlet-sized blocks of text (about 200,000 characters), then the number of possible samples is finite, though extremely large. Given an infinite amount of time, therefore, a perfect copy of Hamlet would have to come up at some point.
That's an interesting point. However, I don't think it happens here, since it's 'possible' that the monkey hits 'a' every time. Then he never gets Hamlet. IIRC The monkey typing 'aaa...' is an example of what ultrafilter said: it has probability 0, yet can happen. So is any other sequence of letters.
Reply With Quote
  #28  
Old 01-25-2004, 10:36 AM
El Zagna El Zagna is offline
Guest
 
Join Date: Jan 2001
Quote:
Originally Posted by ultrafilter
The probability that the monkeys will produce Hamlet is 1, but they are not guaranteed to do so. It's a feature of standard probability theory that, when there is an infinite number of possible outcomes, some events may have probability 0 and still occur.
Well, I'm having a hard time getting my mind around this. That seems to violate the nature of infinity that I've come to know and love. The idea that something with a probability of 1 may not ever occur in an infinite number of tries is curious enough, but the idea that something with a probability of 0 can somehow occur is just... NO WAY!

The only thing that keeps me from snorting in indignation at the very notion is that I've been fooled by the nature of infinity before.
__________________
No sig for me, thanks.
Reply With Quote
  #29  
Old 01-25-2004, 11:15 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by bnorton
Well, I'm having a hard time getting my mind around this. That seems to violate the nature of infinity that I've come to know and love. The idea that something with a probability of 1 may not ever occur in an infinite number of tries is curious enough, but the idea that something with a probability of 0 can somehow occur is just... NO WAY!

The only thing that keeps me from snorting in indignation at the very notion is that I've been fooled by the nature of infinity before.
Yeah, it's bad to intuit about the nature of infinitary processes. They're weird.

Would it help if I told you that every infinite sequence of characters has probability 0?
Reply With Quote
  #30  
Old 01-25-2004, 01:08 PM
Will Repair Will Repair is offline
Guest
 
Join Date: May 2001
Your chances of winning the lottery are only marginally improved by actually purchasing a ticket.
__________________
2008 William Lynes
WillRepair.com
...
Reply With Quote
  #31  
Old 01-25-2004, 03:55 PM
js_africanus js_africanus is offline
Guest
 
Join Date: Nov 2002
To the OP, may I suggest reading How to Lie With Statistics? Additionally, The Cartoon Guide to Statistics is very good, and Calculated Risks is super (IMO).


But don't let that stop you from posting questions!
__________________
This is not a Sponsored Link

Dolphin Gymnast
Not for sale. .....................................................................................Non-ad by me.
Reply With Quote
  #32  
Old 01-25-2004, 04:39 PM
Shade Shade is offline
Guest
 
Join Date: Oct 2001
Let me recount the reasoning in a pseudo-Socratic dialogue because I'm bored

Shade: Let's see. The probability of 'aaaa...' must be zero because it's so unlikely that all the letters are 'a'.
Shade: Does everything have probability zero?
Shade: No, something must happen. Umm.. ummm.. yeah, 'abadfijzasetpq...' might be better.
Shade: But you're actually thinking of all sequences like that. If you pick THAT sequence (assuming we know how an infinite sequence ends), it must be probability 0; it's not more likely that the sequence starts 'abad' than 'aaaa' [ed: if you don't get this bit, read one of the many dialogues on the subject ] so why should it be different for long ones?
Shade: OK, OK, so any sequence is prob 0.
Shade: It must be!
Shade: But... SOMETHING must happen!
Shade: Well, yes. Something with infinitessimal probability.
Shade: Umm..
Shade: Colloquially.
Shade: OK. And all these zeros add to one?
Shade: I don't like it, but what else could happen?
Shade: AHA! It's like a line: the length of any point is zero, but they can be added up to get a length!
Shade: Yeah! Right! I think...
Shade: Cool.
Shade: But I bet the maths works out wrong. You can't deal with infinities that easily.
[Current state of mathematical research in the world ex machina]: Actually, I did the maths earlier and it it wasn't easy, but eventually I got that. Your intuition was, surprisingly, right.
Shade: But.. my intuition also says other stuff. Shouldn't we be dealing wih infinitessimal ('just' over zero) numbers?
[maths]: Well, maybe. But trust me, the first way works out more useful in the end. Go with it.
Shade: OK.
Reply With Quote
  #33  
Old 01-25-2004, 06:41 PM
El Zagna El Zagna is offline
Guest
 
Join Date: Jan 2001
Quote:
Originally Posted by Shade
Shade: Let's see. The probability of 'aaaa...' must be zero because it's so unlikely that all the letters are 'a'.
But it's not 0, it's damn close to 0 but not 0. Or to put it in terms of the little calculus that I remember, it approaches zero as the sequence's length approaches infinity. Add up an infinite number of things damn close to 0 and you get 1, I guess.
__________________
No sig for me, thanks.
Reply With Quote
  #34  
Old 01-25-2004, 07:05 PM
Shade Shade is offline
Guest
 
Join Date: Oct 2001
Firstly, sorry - my internal dialogue was just supposed to show the thought process, not be perfectly rigorous. Perhaps I should have made clear exactly what is normally accepted.

But I assure you that by far the standard and almost universal way of defining probabilities, the probability of an event is a real number.

If so, the probabilities in this case can be consistently defined, and the prob. of 'aaa...' would be 0, but it 'can still occur'. I'm sure you could define probabilities using infinitessimals (numbers 'damn close to zero' ie. not zero, but between zero and any real number) somehow, which can be defined in terms of limits iirc, but I suspect that doing so is a can of worms.

Also, remember the 'it approaches' type argument is risky. For instance, P(first letter is 'a'), P(first two letters are 'a'), P(first three letters are 'a') etc. approach 0, and P(all letters are 'a') is 'close' to 0. But P(first three letters contain strings of 'a's of any finite length) is 0, and is if we replace 'three' by anything, but P(all letters contains strings of 'a's of any finite length) is close to 1. Sorry I don't have a better example, but basically, I've learnt the hard way 'be very careful with infinity'.
Reply With Quote
  #35  
Old 01-25-2004, 07:16 PM
El Zagna El Zagna is offline
Guest
 
Join Date: Jan 2001
Quote:
Originally Posted by Shade
But P(first three letters contain strings of 'a's of any finite length) is 0, and is if we replace 'three' by anything, but P(all letters contains strings of 'a's of any finite length) is close to 1. Sorry I don't have a better example, but basically, I've learnt the hard way 'be very careful with infinity'.
I'm afraid I don't know what you're saying there, but I do agree that one should be very careful with infinity.
__________________
No sig for me, thanks.
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 01:13 PM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright 2013 Sun-Times Media, LLC.