Given an infinite number of monkeys and an infinite amount of time, would one of them write Hamlet?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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!

Answer 7

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, it's like the chance for all the nitrogen molecules in the air to gather around your head and have you die from lack of oxygen."

Answer 8

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.

Answer 9

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.

Answer 10

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]

Answer 11

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.

Answer 12

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 = \left\lceil \frac{\log \epsilon}{\log \left(1 - \frac{1}{26^{l(\text{Hamlet})}}\right)}\right\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?

Answer 13

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