Infinite monkey theorem

According to the second Borel-Cantelli lemma, given enough time, a chimpanzee like this one typing at random will almost surely eventually type out a copy of one of Shakespeare's plays.

The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite time will eventually almost surely type the collected works of William Shakespeare, if not every single piece of literature that has ever, and will ever be written. Note that almost surely is being used in a precise mathematical sense here.

The theorem graphically illustrates the perils of reasoning about infinity by imagining a vast but finite number. If every atom in the Universe were a monkey producing a billion keystrokes a second from the Big Bang until today, it is still very unlikely that any monkey would get as far as "slings and arrows" in Hamlet's most famous soliloquy.

Intuitive proof sketch

The infinite monkey theorem is straightforward to prove, even without appealing to more advanced results. If two events are statistically independent, meaning neither affects the outcome of the other, then the probability of both happening equals the product of the probabilities of each one happening on its own. For example, if the chance of rain in Sydney on a particular day is 0.3 and the chance of an earthquake in San Francisco on that day is 0.008, the chance of both happening on that same day is 0.3 × 0.008 = 0.0024.

Now, suppose the typewriter has 50 keys, and the word to be typed is "banana". Typing at random, the chance that the first letter typed is b is 1/50, as is the chance that the second letter typed is a, and so on. These events are independent, so the chance of the first six letters matching "banana" is 1/50⁶. For the same reason, the chance that the next 6 letters match "banana" is also 1/50⁶, and so on.

Now, the chance of not typing "banana" in each block of 6 letters is 1 − 1/50⁶. Because each block is typed independently, the chance, X, of not typing "banana" in any of the first n blocks of 6 letters is X = (1 − 1/50⁶)ⁿ. As n grows, X gets smaller. For an n of a million, X is 99.99%, but for an n of 10 billion X is 53% and for an n of 100 billion it is 0.17%. As n approaches infinity, the probability X approaches zero; that is, by making n large enough, X can be made as small as one likes. If we were to count occurrences of "banana" that crossed blocks, X would approach zero even more quickly. The same argument applies if the monkey were typing any other string of characters of any length.

The same argument shows why infinitely many monkeys will (almost surely) produce a text as quickly as it would be produced by a perfectly accurate human typist copying it from the original. In this case X = (1 − 1/50⁶)ⁿ where X represents the probability that none of the first n monkeys types "banana" correctly on their first try. When we consider 100 billion monkeys, the probability falls to 0.17%, and as the number of monkeys n increases to infinity the value of X (the probability of all the monkeys failing to reproduce the given text) decreases to zero. This is equivalent to stating that the probability that one or more of an infinite number of monkeys will produce a given text on the first try is 100%, or that it is almost certain they will do so. The only difficulty remaining is in locating the successful monkey.

Formal statements

Although the infinite monkey theorem is usually stated informally, a precise formal statement clarifies its exact meaning. It is easiest to state in the computer science theory of strings, which are sequences of characters chosen from some finite alphabet. In this setting, the two statements above would be stated formally as follows:

• Given an infinite string where each character is chosen uniformly at random, any given finite string almost surely (with probability 1) occurs as a substring at some position (and indeed, infinitely many positions).
• Given an infinite sequence of such infinite strings, where each character of each string is chosen uniformly at random, any given finite string almost surely occurs as a prefix of one of these infinite strings (and indeed, as a prefix of infinitely many of these strings in the sequence).

Both follow easily from the second Borel-Cantelli lemma. Suppose our desired text has length n. For the second theorem, let E_k be the event that the kth string begins with the given text. Because this has some fixed nonzero probability p of occurring, the E_k are independent, and the below sum diverges, the probability that infinitely many of the E_k occur is 1. The first theorem is shown the same way, except that we divide the random string into nonoverlapping blocks of n characters each, and make E_k the event where the kth block equals the desired string.

$\sum _{i=1}^{\infty }P(E_{k})=\sum _{i=1}^{\infty }p=\infty .$

In fact, even going to infinity may be excessive. If the alphabet has size a, then it can be shown that the probability that one of the first aⁿ events occurs is at least 1/2. Thus, 20aⁿ tries would suffice to type the given text with probability very close to 1. The problem also parallelizes well; k monkeys can type the text k times as quickly (linear speedup). For small n this is not too bad; for example, a thousand monkeys typing random letters at 100 characters per minute (slower than a human with any typing experience at all) would very likely type the word "banana" within 6 weeks.

The theorem is an instance of Kolmogorov's zero-one law.

Because we need to be precise about whether it is the number of monkeys or the time available which is infinite, the name "infinite monkey theorem" is a misnomer; each individual monkey is finite. Mathematicians would say "infinite monkeys" only if they mean each monkey alone is infinite, and "infinitely many monkeys" if they mean that.

Origins

In a 1939 essay entitled "The Total Library", Argentine writer Jorge Luis Borges traced the infinite-monkey concept back to Aristotle's Metaphysics. Explaining the views of Leucippus, who held that the world arose through the random combination of atoms, Aristotle notes that the atoms themselves are homogenous and their possible arrangements only differ in position and ordering. The Greek philosopher compares this to the way that a tragedy and a comedy consist of the same "atoms", i.e., alphabetic characters. Three centuries later, Cicero's De natura deorum (On the Nature of the Gods) argued sarcastically against the atomist worldview:

He who considers this possible will also be able to believe that if innumerable characters of gold, each representing one of the twenty-one letters of the alphabet, were thrown together onto the ground, they might produce the Annals of Ennius. I doubt whether chance could possibly create even a single verse to read.

Borges follows the history of this argument through Blaise Pascal and Jonathan Swift, then observes that in his own time, the vocabulary had changed. By 1939, the idiom was "that a half-dozen monkeys provided with typewriters would, in a few eternities, produce all the books in the British Museum." (To which Borges adds, "Strictly speaking, one immortal monkey would suffice.") Borges then imagines the contents of the Total Library which this enterprise would produce if carried to its fullest extreme:

Everything would be in its blind volumes. Everything: the detailed history of the future, Aeschylus' The Egyptians, the exact number of times that the waters of the Ganges have reflected the flight of a falcon, the secret and true nature of Rome, the encyclopedia Novalis would have constructed, my dreams and half-dreams at dawn on August 14, 1934, the proof of Pierre Fermat's theorem, the unwritten chapters of Edwin Drood, those same chapters translated into the language spoken by the Garamantes, the paradoxes Berkeley invented concerning Time but didn't publish, Urizen's books of iron, the premature epiphanes of Stephen Dedalus, which would be meaningless before a cycle of a thousand years, the Gnostic Gospel of Basilides, the song the sirens sang, the complete catalog of the Library, the proof of the inaccuracy of that catalog. Everything: but for every sensible line or accurate fact there would be millions of meaningless cacophonies, verbal farragoes, and babblings. Everything: but all the generations of mankind could pass before the dizzying shelves — shelves that obliterate the day and on which chaos lies — ever reward them with a tolerable page.

The modern image of an infinite monkey collection was presented in Émile Borel's 1913 article "Mécanique Statistique et Irréversibilité" ("Statistical mechanics and irreversibility"). His "monkeys" are not actual monkeys; rather, they were a vivid metaphor for an imaginary way to produce a large, random sequence of letters. Borel said that if a million monkeys typed ten hours a day, it was extremely unlikely that their output would exactly equal all the books of the richest libraries of the world; and yet, in comparison, it was even more unlikely that the laws of statistical mechanics would ever be violated, even briefly.

The physicist Arthur Eddington drew on this image further in The Nature of the Physical World (1928), writing:

If I let my fingers wander idly over the keys of a typewriter it might happen that my screed made an intelligible sentence. If an army of monkeys were strumming on typewriters they might write all the books in the British Museum. The chance of their doing so is decidedly more favourable than the chance of the molecules returning to one half of the vessel.

These images, then, both invite us to consider the incredible improbability of a large but finite number of monkeys working for a large but finite amount of time producing a significant work, and compare this with the even greater improbability of certain physical events. Any physical process that is even less likely than such monkeys' success is effectively impossible; this is the statistical basis of the second law of thermodynamics.

The theorem as it is now stated, with infinite resources, arose in popular culture after around 1970, saying that an infinite number of monkeys typing for an infinite amount of time will produce a given text. To insist on both infinities, however, is excessive. A single immortal monkey who executes infinitely many keystrokes will almost surely eventually type out any given text, and an infinite number of monkeys will almost surely begin producing all possible texts immediately, with no wait. In fact, in both cases, all possible texts will almost surely be produced an infinite number of times (to be precise, an infinite number of monkeys typing k characters each will almost surely produce each work of length k an infinite number of times.)

It is sometimes reported that Borel's use of monkeys and typewriters in his theorem was inspired by an argument used by Thomas Henry Huxley on June 30, 1860, but this is very implausible. Huxley was involved in a debate with the Anglican Bishop of Oxford, Samuel Wilberforce, held at a meeting of the British Association for the Advancement of Science at Oxford, of which Wilberforce was a vice-president, and was sparked by the publication of Charles Darwin's Origin of Species seven months earlier, in November 1859.

No transcript of the debate exists, but neither contemporary accounts of it nor Huxley's later recollections include any reference to the infinite monkey theorem. It is most unlikely that Huxley would have referred to a typewriter. Although patents for machines resembling modern typewriters were granted as early as 1714, commercial production of typewriters did not begin until 1870, and a skilled debater like Huxley would hardly have let his point depend on a device whose existence would have been unknown to most of his audience.

The association of the debate with the infinite monkey theorem is probably an urban myth triggered by the fact that the debate certainly did include some byplay about apes: the bishop asked whether Huxley was descended from an ape on his grandmother's or his grandfather's side, and Huxley responded that he would rather be descended from an ape than from someone who argued as dishonestly as the bishop.

Probabilities

Ignoring punctuation, spacing, and capitalization, a monkey typing letters uniformly at random has one chance in 26 of correctly typing the first letter of Hamlet. It has one chance in 676 (26 times 26) of typing the first two letters. Because the probability shrinks exponentially, at 20 letters it already has only one chance in 26²⁰ = 19,928,148,895,209,409,152,340,197,376, roughly equivalent to the probability of buying 4 lottery tickets consecutively and winning the jackpot each time. In the case of the entire text of Hamlet, the probabilities are so vanishingly small they can barely be conceived in human terms. The text of Hamlet, even stripped of all punctuation, contains well over 130,000 letters which would lead to a probability of one in 3.4×10¹⁸³⁹⁴⁶. It should be noted that the probability of a dolphin tapping away at a typewriter with its nose has a 1.3×10¹⁸ chance of creating Hamlet.

The mere fact that there is a chance, however unlikely, is the key to the "infinite monkey theorem", because Kolmogorov's zero-one law says that such an infinite series of independent events must have a probability of zero or one. Since we have shown above that the chance is not zero, it must be one. To consider that an event this unlikely is almost guaranteed to occur given infinite time can give a sense of the vastness of infinity.

Gian-Carlo Rota wrote in a textbook on probability (unfinished when he died):

If the monkey could type one keystroke every nanosecond, the expected waiting time until the monkey types out Hamlet is so long that the estimated age of the universe is insignificant by comparison ... this is not a practical method for writing plays.

Literature and popular culture

The written word

Jonathan Swift's Gulliver's Travels (1782) anticipates the central idea of the theorem, depicting a professor of the Grand Academy of Lagado who attempts to create a complete list of all knowledge of science by having his students constantly create random strings of letters by turning cranks on a mechanism (Part three, Chapter five): although his intention was more likely to parody Ramon Llull.

In "Inflexible Logic" by Russell Maloney, a short story that appeared in The New Yorker in 1940, the protagonist felt that his wealth put him under an obligation to support the sciences, and so he tested the theory. His monkeys immediately set to work typing, without error, classics of fiction and nonfiction. The rich man was amused to see unexpurgated versions of Samuel Pepys' diaries, of which he owned only a copy of a bowdlerised edition.

A similar theme was struck in the story "The Library of Babel" by Jorge Luis Borges, depicting a library which contains books consisting of every single possible permutation of characters. The narrator notes that every great work of literature is contained in the library; but these are outnumbered by the flawed works (which are themselves vastly outnumbered by works of pure gibberish).

The theorem is also the basis of a one-act play by David Ives called "Words, Words, Words", which appears in his collection All in the Timing. In the one-act, three monkeys named Milton, Swift, and Kafka have been confined to a cage by a scientist until they can write Hamlet. There is a humorous short story by R.A. Lafferty entitled "Been a Long, Long Time", in which an angel is punished by having to proofread all the output text until some future time (after trillions of Universes have been created and died) when the monkeys produce a perfect copy of Shakespeare's works.

In Tom Stoppard's play Rosencrantz & Guildenstern Are Dead, one character says, "If a million monkeys..." and then cannot continue, as the characters are actually within Hamlet, one possible topic of this rule. He then finishes the sentence on a different topic.

One influential occurrence of the theorem transpires in The Hitchhiker's Guide to the Galaxy, in a scene where Ford Prefect and Arthur Dent, under the influence of the Infinite Improbability Drive, are ambushed by an infinite number of monkeys who want their opinion on the monkeys' script for Hamlet.

Michael Ende's The Neverending Story included a chapter in which some persons play a game with some dice with alphabetic characters carved on the faces. Rules are not clear but supposedly the dices are thrown and the results of them are the words, which are then collected. Sometimes, a coherent word or sentence will be formed and eventually all the stories of the world will appear in this game.

Television

Popular culture references to this theorem include The Simpsons (in the episode Last Exit to Springfield, Montgomery Burns has his own room with 1000 monkeys at typewriters, one of which is chastised for mistyping a word in the opening sentence of A Tale of Two Cities — "It was the best of times, it was the blurst of times? You stupid monkey!") and Family Guy (a group of monkeys is shown collaborating on a line from Shakespeare's Romeo and Juliet in a cut scene).

On The Daily Show, Jon Stewart promised that none of their material would be plagarized (after a few stories on the subject) because their show would be written by monkeys. A monkey was then shown typing material for the show; Jon was handed the monkey's latest output, only to reject it.

The Colbert Report provided an analysis of how many monkeys it would take for various works. This was in response to comments made in the news on monkeys typing out the Bible or the Koran. According to Colbert, one million monkeys typing for eternity would produce Shakespere, ten thousand (drinking) monkeys typing for ten thousand years would produce Hemingway, and ten monkeys typing for three days would produce Dan Brown.

In an episode of The Adventures of Jimmy Neutron, Sheen makes a science project that is very similar: He puts a bug in a glass dome, and places it in front of a hungry lizard on a keyboard. The idea is that the lizard will hit the keys with its feet while trying to get the bug, and will eventually "write a great American novel".

Comics and graphic novels

In the comic strip Dilbert, Dogbert tells Dilbert that his report would take "three monkeys, ten minutes".

The Animal Man comic by Grant Morrison contained an issue including a monkey who typed not only the works of Shakespeare, but comic books as well. The TPB this is included in featured an "infinite" number of Grant Morrisons typing on the cover.

Stand-up comedy

Comedian Bob Newhart has a stand-up routine in which a lab technician monitoring an "infinitely many monkeys" experiment discovered that one of the monkeys has typed "To be, or not to be; that is the gezortenblatt." Fellow comedian Ricky Gervais has tried to explain this theorem to Karl Pilkington. Russ Noble incorporates the theory into his act, saying that he actually has 100000 monkeys, but unfortunately only one typewriter. Irish comedian Neil Delamere theorises that, if the infinite monkey theorem is true, it must also hold true that "1,000,000 boa constrictors, with 1,000,000 accordians, would eventually bash out the entire works of Westlife.

Internet culture

In 2000, the IETF Internet standards committee's April 1st RFC proposed an "Infinite Monkey Protocol Suite (IMPS)", a method of directing a farm of infinitely many monkeys over the Internet.

WWDN, the blog of author and actor Wil Wheaton, uses the slogan, "50,000 monkeys at 50,000 typewriters can't be wrong." His witticism won him a Bloggie in 2002 for the category "Best Tagline of a Weblog." Robert Wilensky once jocularly remarked, "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." In a similar vein, Mad Magazine stated, "If an infinite number of monkeys typed 24-hours a day on an infinite number of computers, the result would be not unlike an AOL Chatroom."

Goats, a popular webcomic illustrated by Jonathan Rosenberg, featured a story line named infinite typewriters where several characters accidentally teleport to an alternate dimension. There they find that this dimension is populated by monkeys with typewriters, presumably typing the scripts of many other dimensions.

Music

The 1979 debut album by Leeds punk rock band the Mekons is called The Quality of Mercy is Not Strnen. Originally released on Virgin Records in the United Kingdom, its cover features a photo of a typing chimp (which, of course, is not a monkey at all).

Software Development methodology

Around 1990, two young turk programmers, Dan Lyke and Eric Bradway Wolf discussed the possibility of developing software by implementing an infinite number of virtual monkeys. The idea being that if an infinite number of monkeys could write the complete works of Shakespeare, then they should be able to fully implement the software Lyke and Wolf were working on. Virtual monkeys were an obvious choice over real monkeys due to the decreased overhead in bananas and easier cleanup. The theory was scrapped, however, because it was determined that the regression testing to determine which of the infinite number of versions of the program met the specifications would require an infinite amount of time.

Infinite monkey experiments

This is a thought experiment which clearly cannot be carried out in practice, since it calls either for infinite time or infinite resources. Nonetheless, it has inspired efforts in finite random text generation.

A website entitled "The Monkey Shakespeare Simulator", launched on July 1, 2003, contains a Java applet that simulates a large population of monkeys typing randomly, with the stated intention of seeing how long it takes the virtual monkeys to produce a complete Shakespearean play from beginning to end. Though it does not update its records anymore, the generator has generated sequences of at maximum 24 letters long. For example, it produced this partial line from Julius Caesar:

Flauius. Hence: home you idle CrmS3RSs
jbnKR IIYUS2([;3ei'Qqrm' 

Due to processing power limitations, the program uses a probabilistic model (by using a random number generator) instead of actually generating random text and comparing it to Shakespeare. When the simulator "detects a match" (that is, the RNG generates a certain value or a value within a certain range), the simulator simulates the match by generating matched text.

Evolutionary biologist Richard Dawkins employs the typing monkey concept in his 1986 book The Blind Watchmaker to demonstrate the abilities of natural selection in producing biological complexity out of random mutations. In the simulation experiment he describes, Dawkins has his Weasel program produce the Hamlet phrase METHINKS IT IS LIKE A WEASEL by typing random phrases but constantly freezing those parts of the output which already match the goal. The point is that random string generation merely serves to furnish raw materials, while selection imparts the information.

In 2003, scientists at Paignton Zoo and the University of Plymouth, in Devon in England reported that they had left a computer keyboard in the enclosure of six Sulawesi Crested Macaques for a month; not only did the monkeys produce nothing but five pages consisting largely of the letter S, they started by attacking the keyboard with a stone, and continued by urinating and defecating on it.

See also

• Pierre Menard
• Weasel program

External links

• The Parable of the Monkeys
• Monkey Shakespeare Simulator
• Real Life Parody of the Keyboard/Monkey Concept
• Monkeys Don't Write Shakespeare
• avoision.com: An attempt to recreate Genesis 1:1 from random text.
• Chance and Probability: Calculating how long it would take to randomly produce the complete works of Shakespeare.
• Mojo The Monkey: A look at the words produced by a monkey typist
• Monkey Literature: Parody of the Infinite monkey theorem with randomly generated poems.