Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Of course, we've all heard the colloquialism "If a bunch of monkeys pound on a typewriter, eventually one of them will write Hamlet."

I have a (not very mathematically intelligent) friend who presented it as if it were a mathematical fact. Which got me thinking... Is this really true? Of course, I've learned that dealing with infinity can be tricky, but my intuition says that time is countably infinite while the number of works the monkeys could produce is uncountably infinite. Therefore, it isn't necessarily given that the monkeys would write Hamlet.

Could someone who's better at this kind of math than me tell me if this is correct? Or is there more to it than I'm thinking?

share|improve this question

closed as off-topic by Grigory M, Yiorgos S. Smyrlis, Lost1, Claude Leibovici, Thomas Andrews Jan 25 at 14:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – Grigory M, Yiorgos S. Smyrlis, Lost1, Claude Leibovici, Thomas Andrews
If this question can be reworded to fit the rules in the help center, please edit the question.

17  
@Jason: +1 for asking a question that elicits such golden answers as are found below! –  Sean Tilson Jan 12 '11 at 2:14
17  
Note that the set of finite-length strings of characters (i.e. "works") is countably infinite, not uncountable. –  Nate Eldredge Jan 12 '11 at 3:23
30  
Doesn't one monkey suffice? –  Rasmus Jan 12 '11 at 9:34
14  
dilbert.com/strips/comic/1989-05-15 –  GWLlosa Jan 12 '11 at 12:34
61  
“We’ve all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the Internet, we know this is not true.” (Robert Silensky) –  Ed Guiness Jan 12 '11 at 16:53

14 Answers 14

up vote 83 down vote accepted

Some references (I am mildly surprised that no one has done this yet). This is called the infinite monkey theorem in the literature. It follows from the second Borel-Cantelli lemma and is related to Kolmogorov's zero-one law, which is the result that provides the intuition behind general statements like this. (The zero-one law tells you that the probability of getting Hamlet is either zero or one, but doesn't tell you which. This is usually the hard part of applying the zero-one law.) Since others have addressed the practical side, I am telling you what the mathematical idealization looks like.

my intuition says that time is countably infinite while the number of works the monkeys could produce is uncountably infinite.

This is a good idea! Unfortunately, the number of finite strings from a finite alphabet is countable. This is a good exercise and worth working out yourself.

Edit: also, regarding some ideas which have come up in the discussions on other answers, Jorge Luis Borges' short story The Library of Babel is an interesting read.

share|improve this answer
3  
Hmmm... I must admit to being a bit surprised to find out that there's an "infinite monkey" theorem. –  Jason Jan 13 '11 at 1:32
14  
@Jason: of course, the theorem isn't really about monkeys. It's about a particular model of monkeys. (Mathematics cannot prove anything about the world: it can only prove things about models of the world.) One can argue, as so many are doing in this thread, for or against this model, but when people quote this result I am assuming that they are referring to the model. –  Qiaochu Yuan Jan 13 '11 at 1:53
1  
As Borges said, Infinites and Mirrors are evil. –  belisarius Jan 14 '11 at 3:40
2  
@Trufa "¿De qué otra forma se puede amenazar que no sea de muerte? Lo interesante, lo original, sería que alguien lo amenace a uno con la inmortalidad." –  belisarius Feb 3 '11 at 2:25
5  
I imagine the reason is no, and for relatively simple reasons. Monkeys won't see the use of typing. After at most a few keypresses they'll either get bored or destroy the typewriter in a fit. I doubt an infinite number of monkeys could even put together a full page full of nonsense but reasonable-length words with punctuation. You could ask the same question about spiders. Put an infinite number of spiders on typewriters and they won't produce Hamlet either, mostly because most spiders lack the strength to type. –  Ryan Budney Dec 2 '11 at 18:11

I found online the claim (which we may as well accept for this purpose) that there are $32241$ words in Hamlet. Figuring $5$ characters and one space per word, this is $193446$ characters. If the character set is $60$ including capitals and punctuation, a random string of $193446$ characters has a chance of $1$ in $60^{193446}$ (roughly $1$ in $10^{344000}$) of being Hamlet. While very small, this is greater than zero. So if you try enough times, and infinity times is certainly enough, you will probably produce Hamlet. But don't hold your breath. It doesn't even take an infinite number of monkeys or an infinite number of tries. Only a product of $10^{344001}$ makes it very likely. True, this is a very large number, but most numbers are larger.

share|improve this answer
36  
In fact one monkey alone would write Hamlet an infinite number of times given unlimited time. –  jericson Jan 12 '11 at 1:54
243  
+1 for: "True, this is a very large number, but most numbers are larger." –  Sean Tilson Jan 12 '11 at 2:08
63  
But what is even more alarming, is that the same monkeys - and probably (in the mathematical sense of the word) within the same time limit mentioned above by Ross Millikan - will write Hamlet with every possible typo imaginable. –  Fredrik Meyer Jan 12 '11 at 2:50
22  
@Fredrik Meyer: ...and there was I thinking the decline of English was down to textspeak and all forms of youthful disregard for conventions; when actually the inaccurate spelling movement is being led by a band of thespian-tendencied research monkeys. –  Orbling Jan 12 '11 at 3:38
96  
"but most numbers are larger". Not really. There's this infinite set of negative numbers to contend with. :) –  Haacked Jan 12 '11 at 8:34

If you have an infinite number of monkeys, then an infinite subset of them will just sit and type out Hamlet, letter-for-letter, straight away. So after a few hours you will have an infinite number of copies of Hamlet.

If you have a finite number of monkeys then you may have to wait. But given in infinite amount of time (and immortal monkeys, etc.), you'll get your Hamlet. Eventually.

share|improve this answer
9  
So infinite monkeys, no problem; finite monkeys, request infinite improbability drive for Christmas present. This poses the question, how do you count your monkeys? –  Orbling Jan 12 '11 at 3:41
34  
Fortunately, Hamlet is out of copyright. But they'll also write copies of everything that is in copyright, plus hexadecimal representations of binary files for every copyrighted movie, TV show, recording, etc., so they're still in big trouble. –  Mike Scott Jan 12 '11 at 8:46
27  
The problem is distinguishing the correct copies of Hamlet from the infinite number of copies with significant typographic errors --- for example, the one in which Hamlet and Ophillia create a time machine and run off together to America. –  vy32 Jan 12 '11 at 16:04
2  
@Orbling With an infinite improbability drive you get whales, not monkeys :D –  belisarius Jan 14 '11 at 3:44
2  
@Orbling And the quotes are mostly harmless –  belisarius Jan 14 '11 at 15:52

[Note that in my answer I am actually assuming that there are only a finite number of monkeys. I don't see what is gained by having both the number of monkeys and the time frame be infinite: mathematically speaking $\aleph_0 \times \aleph_0 = \aleph_0$, and it is somewhat confusing to contemplate infinitely many monkeys typing simultaneously: too much is happening at once. In fact, there might as well be only one monkey, or at any rate only one typewriter.]

Let me take the unusual (for me) step of considering the practical aspects of this question as well.

As Ross Millikan has explained, there is a simple mathematical model of monkey keyboard pounding under which it is easy to see that the claim is true: the probability that at least one of the monkeys will type out Hamlet approaches $1$ as the time $n$ approaches infinity.

However there is an assumption here: namely, that the pounding on the typewriter is random or sufficiently close to random. One way to formalize this is to say that after typing any $n$ characters, the probability of hitting any given key as the $n+1$st character is at least $P$, where $P$ is positive and independent of $n$.

The problem is that for actual typewriter banging, this is a very unlikely assumption. The issue is similar here to what happens if you ask someone to produce a random sequence of digits, say from $0$ to $9$, or even a random sequence of $H$'s and $T$'s (for "heads" and "tails"). Just closing your eyes and banging away will produce something very far from being random.

If the question is meant to apply to actual monkeys with their nonrandom motor behavior, then it is something else entirely. I would be tempted to say that the probability of producing Hamlet does not approach $1$ as time approaches infinity, but I'm not sure off the top of my head how to justify this.

share|improve this answer
29  
Pete: I think this might be my favorite answer to any question ever. I know you meant it seriously, and it is certainly a well thought answer, but I find some of the phrases hilarious. Only a mathematician could write the phrase "there is a simple mathematical model of monkey keyboard pounding". –  Sean Tilson Jan 12 '11 at 2:11
14  
Dear Pete, The paper Power laws for monkeys typing randomly: the case of unequal probabilities has some relevance to the issue considered in your answer, I think. Regards, –  Matt E Jan 12 '11 at 3:25
4  
This reminds me of a Dilbert strip: clipmarks.com/clipmark/4905F106-063A-401C-8631-392E2E49652A –  KCd Jan 12 '11 at 6:39
33  
I believe there was an actual experiment done with monkeys in a room with typewriters to see what exactly they would produce. If I recall correctly the monkeys destroyed the typewriters, science. –  JSchlather Jan 12 '11 at 8:19
6  
@Jacob Schlather. Not only did they destroy them, they treat them like toilets, too. –  Armstrongest Jan 12 '11 at 20:24

The answer is yes, With infinite time and all of the infinite monkeys will produce hamlet and every other works infinitely many times.

After the first keystroke of the infinitely many monkeys, there will be infinitely many hamlets if you just grabbed the first letter from each one of them.

Also at the first keystroke, infinitely of monkeys would have types the first letter of the entire hamlet already, this shows that if you have infinite number of monkeys you only each one of them to type just as many letters as the number of letters in hamlet to have already infinitely many copies of hamlet, so there is no need for infinite time to have one of them produced hamlet, infinitely many of the monkeys would produce infinitely many hamlets in finite amount of time as long as the finite amount of time is equal or greater than the time to type a single copy of hamlet. (this was already mentioned in Bennett McElwee's answer)

If you rephrase the question to : Would an infinite random sequence of letters in 2 dimensions contain at least one hamlet in every and each one of it's columns/rows? then the answer is yes, but there would be infinite number of hamlets contained in each row/column, As an infinite random sequence will contain all it's possible finite sub sequences, infinitely many times. ( Reference needed ).

share|improve this answer
    
I suspect this is incorrect.. Consider a random sequence using only 1's and 2's. No reason why it contains all possible numbers especially 123 inside it. –  picakhu Jan 12 '11 at 4:16
    
@picakhu : edited, of course a sequence of 1's and 2's wont have a 3 in it! :) added the finite subsequence into edit –  Arjang Jan 12 '11 at 4:32
    
I think this is still incorrect.. Assume that a 11 is banned. so we can have a random sequence like 121222212221222122222222212121212221212 which has no sub-sequence 11 in it. –  picakhu Jan 12 '11 at 4:37
    
@picakhu : Why random sequence of 1's and 2's is not allowed to have 11? of course if a subsequence is always take out from the sequence then it will not occur. –  Arjang Jan 12 '11 at 5:13
2  
@picakhu I could then just as easily say that the sequence 212 contains the sub-sequence 11 and the sequence 2122 does not contain the sub-sequence 22. If the interpretations are isomorphic, you are free to choose either one. That said, monkeys are unlikely to produce output that can be universally interpreted in more than one meaningful, non-trivial way. I.e., interpreting 'aa' as 'b' is meaningless in the general case, and the choice of computer character encoding (ASCII vs. UTF-8, say) is trivial. My point, I guess, is that random letter generators won't perform high-level encoding. –  WCWedin Jan 12 '11 at 22:19

It would probably be faster to apply selective pressure to breed intelligent, literary monkeys. Our common ancestor with chimps lived only 4 million years ago, and by design I'm sure we could make something similar happen faster starting with chimps, bonobos, or whatever.

We could probably get orcas and other whales up to speed very quickly, too!

share|improve this answer
6  
What is the probability that I now read the word bonobo for the SECOND time today after a lifetime of never having heard it - ahh the internets... –  mplungjan Jan 12 '11 at 12:54
2  
Even if you do that, why would they produce an exact copy of Shakespeare? I mean almost surely their history will be different than ours. –  timur Jan 13 '11 at 5:11
3  
@timur True; you would have to reproduce the exact conditions that lead to Hamlet it produce the same exact text at the same exact time. Or, as Carl Sagan put it, "If you want to make an apple pie from scratch, you must first create the universe." –  WCWedin Jan 13 '11 at 23:49
    
No, just pay them minimum wage to write it out. Before they become smarter than us and destroy the Statue of Liberty! –  Kevin Cantu Jan 14 '11 at 10:19
2  
Apparently Hollywood is already halfway there, judging by their product. –  cdjaco Jan 14 '11 at 23:23

Let me be the one who says NO. It is a bit hard to handle an infinite number of monkeys (because you will need an infinite number of bananas to feed them), but if you agree to have a finite number of monkeys and infinite time, I would guess that considering the time it should take for this to happen, it is likely that the universe would die before it actually does.

To quote a chat of one of my friends with my first year "intro to CS" professor:

professor: "So there is no chance that a fair coin would fall with the head side up 50 times in a row."

my friend: "No!, there is such a chance it's just very small...."

professor: "Well yes, its like the chance for all the nitrogen molecules in the air to gather around your head and have you die from lack of oxygen."

share|improve this answer
9  
Ultrafinitism takes out all the fun from mathematics. Especially from the parts dealing with infinite processes. –  Asaf Karagila Jan 12 '11 at 8:41
12  
From a [ultra]finitistic perspective, I don't think you can say "NO"; you can only say that the question is meaningless as there's no such thing as infinite time or infinite monkeys. –  ShreevatsaR Jan 12 '11 at 14:42
2  
And there would need to be an infinite amount of space to contain the monkeys... not to mention infinite typewriters... better ramp up typewriter production in China. –  Armstrongest Jan 12 '11 at 20:33
1  
@ShreevatsaR Talk about practical thinking. –  muntoo Jan 14 '11 at 6:10
    
Also, I doubt the monkeys will specifically twist their hands for each letter. The QWERTY keyboard was designed to make it slower/harder to type, after all, so I doubt the mindless monkeys will go to all that trouble to contort their 'inferior' hands. –  muntoo Nov 21 '11 at 6:59

Here's a rather interesting article discussing the probability of a monkey producing Shakespeare's works and uses a random letter generator to demonstrate some results.

share|improve this answer

Hamlet was indeed written after a finite number of monkeys (Shakespeare was a a primate from the family Hominidae!)

share|improve this answer
9  
Which makes it all the more remarkable, don't you think? –  Armstrongest Jan 12 '11 at 20:29
6  
Entertaining, but does not really answer the question. –  timur Jan 13 '11 at 5:03
7  
The important difference here is that the monkeys you are referring to are not randomly selected, nor do they type randomly. –  Konrad Rudolph Jan 13 '11 at 14:51
18  
hsdiljcmksl ndewjknxcjkw;jkei80900 –  Simon Jan 13 '11 at 16:27
1  
@Willie isupposeitwastoolongsorryigotcarriedaway –  muntoo Jan 15 '11 at 6:07

If there truly was an infinite amount of time and monkey, yes, it could happen. However, we know that time and monkeys are both limited. Let's say that the universe will be gone when there are no more neutrons. According to this article, that will be about 10^40 years. There are approximately 4*10^78 atoms. And let's just say that an atom monkey can type at 10^15 keys per second. Let's also assume that there are 40 keys on a typewritter (26 A-Z, numbers, period, comma, semicolon, and space). That'll give the following:

There will be 4e78*365*24*3600*1e15 key strokes per atom, giving a total of 1.26e101. There would then be 5.05e177 key strokes. 40^108=1.0531e+173. That means that there would be segments of around 108 characters of Hamlet around, but certainly not the whole work.

share|improve this answer
2  
+1 The answer is no because the question is impossible. Given that the mass and age of the universe are both finite, it is impossible to have an infinite number of monkeys typing for an infinite amount of time. –  Qwerky Jan 12 '11 at 16:26
8  
@Qwerky: I think you are interpreting the question too literally. That is one interpretation, but there are other interpretations less tied to physical reality. –  Qiaochu Yuan Jan 12 '11 at 17:38

Monkeys don't produce a proper random distribution on keystrokes. Not even a Markov-chain of keystrokes.

Given infinite time (and an undying support of monkeys) or just infinite monkeys, they will produce infinite text. But that does not need to imply that Hamlet will be part of this infinite long text.


[edit]

There is empirical evidence from such an experiment, reported by the BBC.

The actual text produced is obviously not that random at all.

(@Henry: Thx for these links.)

[/edit]

share|improve this answer
    
Did you mean "perhaps" instead of "eventually"? –  Rasmus Jan 16 '11 at 10:50
    
daah... yeah, of course. silly me. – The german word "eventuell" means "possibly" in english. It's one of those strange words... The inventor of the english language must have written some bugs in one of the first english dictionaries, which is now hardwired in the standard library. –  comonad Jan 27 '11 at 21:22
1  
Monkeys don't produce a proper random distribution on keystrokes. Not even a Markov-chain of keystrokes. How do you know? –  Did Nov 11 '11 at 20:57
    
Just look at the monkey, dude! Not better than a baby on the piano, nearly repeating the same wham from before. (Assumed that it's not Markov's child playing.) –  comonad Nov 12 '11 at 7:44
1  
@Didier: There is empirical evidence from an experiment reported by the BBC and I suspect that the actual text produced would fail most test of randomness. –  Henry Nov 14 '11 at 0:34

For some reason I want to attribute this reasoning to Douglas Hofstadter, though I couldn't tell you which of his books it's from. Here goes:

If you could get sufficient randomness from an infinite number of monkeys (this is trivial if you assume that by mere chance, a infinite subset will fit the bill – or you could follow Arjang's approach and aggregate across monkeys for more entropy, which has the benefit of getting results much faster), you already have every variation of every story ever told. You'll even have every story that ever could be told. Just get an infinite number of monkeys (or a slightly smaller number of computers) and opening a publishing business. Make a million bucks and retire.

But this rings false, especially since modern computing power (relative to the difficulty of the task) is practically infinite, putting the practice of this philosophy within reach. Just imagine trying it yourself. It's not the monkeys or the computers or the printers doing all of the work. Suddenly, you are wading through millions of pages of gibberish text looking for the book that will make you rich. Good luck. (It is the fact that the filtering process is much slower than the production process that makes me say that computer power is practically infinite.)

It's not the characters on the page that make Hamlet. Hamlet is a synthesis of information, a composition that can only be guided by intelligence. In a sea of random characters, the sequence that maps isomorphically to Hamlet is just more noise.

This may sound like a qualified "yes" in response to the question, but in reality it is an empathic "no." It is not the act of producing the character sequence of Hamlet in a random string that writes Hamlet – it is the act of finding Hamlet in a random string that writes Hamlet. The distinction may sound subtle, but the two tasks are profoundly different.

share|improve this answer
4  
"modern computing power […] is practically infinite" — I think you misunderstand what "infinite" means. "A very large number" is not "practically infinite". In fact, the world's total computing power isn't even, "relative to the difficulty of the task", close to 10^344000, which is roughly how big you need things to be for Hamlet to be produced. It's a minuscule insignificant fraction of that, which means that we have no chance of generating Hamlet today by an actual uniform random process. Yes, if it were generated, we'd have trouble finding it, but that's a far out concern. –  ShreevatsaR Jan 13 '11 at 8:03
1  
@ShreevatsaR A very large number" is not "practically infinite". I think the stress should be the word "practical" rather than "infinite." If the value could be either its current value or infinity without changing the bottleneck task (qualitatively or quantitatively), how is that anything other than practically infinite? It would be been better if I'd clarified that point more explicitly and earlier in the paragraph, though. –  WCWedin Jan 13 '11 at 20:53
    
@ShreevatsaR Yes, if it were generated, we'd have trouble finding it, but that's a far out concern. On second thought, though, I think this is where our opinions diverge. In my opinion, this is a more fundamental point than physical limitations, or even the theoretical implication of infinity. You could say I played a sly trick in redefining "generating Hamlet," but I was really trying to make a point about the nature of information. To sum it up differently, I would say, "The question is irrelevant, because data is not information without context." Or, in Hofstadter's words, "Mu." –  WCWedin Jan 13 '11 at 21:00
    
As far as I can see, the question is not about whether we can sift through the generated text to find intelligent text ("opening a publishing business. Make a million bucks…"), but whether a specific long text (Hamlet) may be generated by a random process at all. (That is, it's not the question here, though it may have been Hofstadter's, knowing his concerns.) So that part is simply irrelevant. And if you're looking for Hamlet specifically (letter-for-letter), it's a rather simple task that can be done with almost the same amount of resources as stepping through the generated text. –  ShreevatsaR Jan 15 '11 at 18:31
    
@ShreevatsaR: Given the context, you could fairly say that I answered "the wrong question." I would even agree. –  WCWedin Jan 17 '11 at 6:30

You don’t even need an infinite number of monkeys! For any $\epsilon > 0$ and $k \geq l(\text{Hamlet})$, there is some number $N$ such that $N$ monkeys at typewriters, each typing for $k$ keystrokes, will produce a copy of Hamlet with probability greater than $1-\epsilon$. (This holds under some quite weak conditions on our model of monkey typing.)

This is an example of the general “soft analysis to hard analysis” principle, championed by Terry Tao among others: most any proof in analysis may be transformed into a proof of a quantitative statement such as the one above.

This can be made precise in some generality using various rather beautiful proof-theoretic methods, such as variants of Gödel’s Dialectica translation; lovely results along these lines have been obtained by e.g. Avigad, Gerhardy and Towsner. In this particular case, the bounds we get will of course depend on the model of monkey typing used.

For instance, if we assume that the keystrokes are independently uniformly distributed, if our Hamlet-recognition criterion is case-, punctuation- and whitespace-insensitive, then for the case $k = l(\text{Hamlet})$,

$$N = \lceil \frac{\log \epsilon}{\log (1 - \frac{1}{26^{l(\text{Hamlet})}})}\rceil$$

will work. (The proof is an exercise for the reader.)

Project Gutenberg’s copy of Hamlet (first folio) weighs in at 117,496 alphanumeric characters. So if we want to produce Hamlet (first folio) with probability 1/2, in the minimal number of keystrokes, then by some quick slapdash estimating (rounding up a little to be on the safe side), something like $10^{170,000}$ monkeys should certainly suffice!

I guess empirical testing is out — ethical controls are so tricky. Anyone want to run some simulations?

share|improve this answer
1  
Oops — I see now that my answer overlaps somewhat with Ross Millikan’s excellent one above. However, there is a fair amount that is different, so I will leave this nonetheless… –  Peter LeFanu Lumsdaine Jan 13 '11 at 5:40

NOTE: By probability, I mean the chance of it happening per iteration, and starting with a new page each time.

Let's take a step back, shall we? (Not too many, because there's a cliff behind you.) Let's think of what the probability is of producing the following randomly:

A

Assuming there are only 26 characters (A-Z, uppercase), the probability would be $\frac{1}{26}$.

What about this:

AA

It'd be $(\frac{1}{26})^2$. This:

AAA

It'd be $(\frac{1}{26})^3$. And this:

XKCD

It'd be $(\frac{0}{26})^4$. [Just kidding, it's: $(\frac{1}{26})^4$].

So, for every character we add to the quote, it will be: $(1/26)^c)$, where $c$ represents the number of characters.

Basically, it would be a probability of $(\frac{1}{26*2+12})^c$ since the characters used could be: A-Z, a-z, .!?,;: "'/() Of course, there could be more characters, but that's just an example. :)

share|improve this answer
2  
Could I please have the ability to downvote myself? 10 months and 6 days later, I find out that I am an idiot. –  muntoo Nov 21 '11 at 7:02
1  
You can delete the answer, right? –  The Chaz 2.0 Feb 27 '12 at 14:50
    
@TheChaz I will leave it up here as proof that even a genius can be an idiot at times. –  muntoo Feb 28 '12 at 1:37
1  
Don't be so hard on yourself! Maybe this is proof that given a finite amount of time, a human with a keyboard will type... ________ ??? –  The Chaz 2.0 Feb 28 '12 at 3:13
    
Upvote from me. This is a genius answer, you proved the opposite, muntoo. (kidding, no offense :) –  Rock Jun 6 '12 at 5:09

protected by t.b. Nov 9 '11 at 18:53

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.