Odds concerning monkeys and the lottery

[With Rye]

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!

[aahala]

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.

[El Zagna]

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.

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.

[Lockfist]

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.

[Hermitian]

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

[Electronic Chaos]

*hands OP the Heart of Gold*

[Sublight]

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 26², 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 26³, or 17576, which will take a few hours. Dave (26⁴, or 456976) will have to wait about 5 days. If your name is Yoshitsune, the chances are 1 in 26¹⁰, or 141167095653376, which means you'll have to wait roughly 4 million years for it to come up, but eventualy it will.

[muttrox]

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.

[muttrox]

Also note that even in your example, the monkeys did produce Hamlet, it just took a very very long time.

[ccwaterback]

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.

[MikeS]

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?

[SCSimmons]

http://www.brunching.com/randommonkeys.html

[Chronos]

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 26²⁰⁶⁰⁰⁰, which is approximately 10²⁹¹⁴⁸⁴. So if you had that many monkeys, you'd expect to get one copy of Hamlet out.

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

There has been work in a non-standard probability theory where this doesn't happen, but it hasn't reached widespread acceptance yet.

[NurseCarmen]

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.

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

[Xema]

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.

[PookahMacPhellimey]

Originally Posted by Sublight

If your name is Yoshitsune, the chances are 1 in 26¹⁰, 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?

[pjd]

Here is a link to a monkey shakespeare simulator ...

[muttrox]

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!

[micco]

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.

[panamajack]

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.

[Flash-57]

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

[jk1245]

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?

[micco]

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.

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

Yes.

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.

[Sublight]

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?)

[Shade]

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.

[El Zagna]

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.

[ultrafilter]

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?

[Will Repair]

Your chances of winning the lottery are only marginally improved by actually purchasing a ticket.

[js_africanus]

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!

[Shade]

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.

[El Zagna]

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.

[Shade]

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

[El Zagna]

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.