Remember Me?

 Straight Dope Message Board Remember Me?

#1
01-21-2004, 08:06 PM
 With Rye Guest Join Date: Mar 2001 Location: San Francisco Posts: 178
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!
__________________
#2
01-21-2004, 08:14 PM
 aahala Guest Join Date: Mar 2002 Posts: 1,781
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.
#3
01-21-2004, 08:23 PM
 El Zagna Guest Join Date: Jan 2001 Location: Austin, Texas Posts: 1,927
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.
#4
01-21-2004, 08:30 PM
 Lockfist Guest Join Date: Jun 2001 Posts: 424
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.
#5
01-21-2004, 11:36 PM
 Hermitian Guest Join Date: Jan 2004 Posts: 1,863
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."
#6
01-21-2004, 11:56 PM
 Electronic Chaos Guest Join Date: Nov 2001 Location: Nashville-ish Posts: 2,328
*hands OP the Heart of Gold*
#7
01-22-2004, 03:11 AM
 Sublight Guest Join Date: Aug 2000 Posts: 10,287
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.
#8
01-22-2004, 10:33 AM
 muttrox Member Join Date: Dec 2000 Posts: 2,107
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.
#9
01-22-2004, 10:35 AM
 muttrox Member Join Date: Dec 2000 Posts: 2,107
Also note that even in your example, the monkeys did produce Hamlet, it just took a very very long time.
#10
01-22-2004, 03:55 PM
 ccwaterback Guest Join Date: Jul 2003 Location: Megalopolis Posts: 4,810
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.
#11
01-22-2004, 04:28 PM
 MikeS Charter Member Join Date: Oct 2001 Location: New London, CT Posts: 3,770
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?
#12
01-22-2004, 05:05 PM
 SCSimmons Guest Join Date: Mar 2001 Location: Arlington, TX Posts: 3,261
__________________
-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
#13
01-22-2004, 05:08 PM
 Chronos Charter Member Moderator Join Date: Jan 2000 Location: The Land of Cleves Posts: 74,547
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
Check out my dice in the Marketplace
#14
01-22-2004, 05:12 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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.
#15
01-22-2004, 05:32 PM
 NurseCarmen Member Join Date: Mar 2002 Location: The Zen Arcade Posts: 8,292
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.
#16
01-23-2004, 02:08 AM
 Flash-57 Guest Join Date: Nov 2003 Posts: 246
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
#17
01-23-2004, 02:37 AM
 Xema Guest Join Date: Mar 2002 Posts: 11,670
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.
#18
01-23-2004, 07:00 AM
 PookahMacPhellimey Guest Join Date: Jul 2001 Location: Italy Posts: 2,114
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?
#19
01-23-2004, 08:15 AM
 pjd Guest Join Date: May 2003 Location: UK Posts: 103
Here is a link to a monkey shakespeare simulator ...
__________________
---------
Apples
#20
01-23-2004, 12:12 PM
 muttrox Member Join Date: Dec 2000 Posts: 2,107
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!
#21
01-23-2004, 12:57 PM
 micco Registered User Join Date: Apr 2001 Posts: 1,562
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.
#22
01-23-2004, 01:04 PM
 panamajack Guest Join Date: Apr 2000 Location: up the coast Posts: 4,417
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.
#23
01-23-2004, 01:16 PM
 Flash-57 Guest Join Date: Nov 2003 Posts: 246
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
#24
01-23-2004, 01:56 PM
 jk1245 Guest Join Date: Jul 2000 Location: Madison, WI Posts: 2,114
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?
#25
01-23-2004, 02:14 PM
 micco Registered User Join Date: Apr 2001 Posts: 1,562
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.
#26
01-25-2004, 09:54 AM
 Sublight Guest Join Date: Aug 2000 Posts: 10,287
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?)
#27
01-25-2004, 10:16 AM
 Shade Guest Join Date: Oct 2001 Location: Cambridge. No, the UK one Posts: 4,272
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.
#28
01-25-2004, 11:36 AM
 El Zagna Guest Join Date: Jan 2001 Location: Austin, Texas Posts: 1,927
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.
#29
01-25-2004, 12:15 PM
 ultrafilter Guest Join Date: May 2001 Location: In another castle Posts: 18,988
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?
#30
01-25-2004, 02:08 PM
 Will Repair Guest Join Date: May 2001 Location: Arcade Posts: 2,280
Your chances of winning the lottery are only marginally improved by actually purchasing a ticket.
__________________
WillRepair.com
...
#31
01-25-2004, 04:55 PM
 js_africanus Guest Join Date: Nov 2002 Location: Small City, Michigan Posts: 5,162
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!
__________________

Dolphin Gymnast
Not for sale. .....................................................................................Non-ad by me.
#32
01-25-2004, 05:39 PM
 Shade Guest Join Date: Oct 2001 Location: Cambridge. No, the UK one Posts: 4,272
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: Well, yes. Something with infinitessimal probability.
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: 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.
#33
01-25-2004, 07:41 PM
 El Zagna Guest Join Date: Jan 2001 Location: Austin, Texas Posts: 1,927
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.
#34
01-25-2004, 08:05 PM
 Shade Guest Join Date: Oct 2001 Location: Cambridge. No, the UK one Posts: 4,272
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'.
#35
01-25-2004, 08:16 PM
 El Zagna Guest Join Date: Jan 2001 Location: Austin, Texas Posts: 1,927
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.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     General Questions     Great Debates     Elections     Cafe Society     The Game Room     Thread Games     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit

All times are GMT -5. The time now is 12:35 PM.

 -- Straight Dope v3.7.3 -- Sultantheme's Responsive vB3-blue Contact Us - Straight Dope Homepage - Archive - Top

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