Infinite Monkey Theorem Proof Sketch Probabilities

The infinite monkey theorem¹ says that, with absolute certainty, a monkey hitting keys at random on a typewriter keyboard will eventually type every book in France's Bibliothèque nationale de France ( National Library). The name is a popular misnomer for an idea from Émile Borel's book on probability, published in 1909, which introduced the concept of "dactylographic² monkeys." The theorem exemplifies a proposition in the theory of probability called Kolmogorov's zero-one law. Strictly speaking, what Borel was illustrating was only a special case of Kolmogorov's zero-one law, the more general statement of which had not yet been given (Kolmogorov's famous monograph on probability theory was not published until 1933).

A popular statement of the theorem is that an infiniteInfinity is a word carrying a number of different meanings in mathematics, philosophy, theology and everyday life. In theology, for instance in the work of Duns Scotus, the infinity of God carries the sense not so much of quantity (leading to the question 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 eventually type out any given text, and an infinite number of monkeys will begin producing all possible texts immediately, with no wait.

Subsequent restatements by other people have replaced the National Library not only with the British MuseumThe British Museum is one of the world's greatest and most famous museums. It was established in 1753 by Sir Hans Sloane, a physician and scientist who collected lots of literature and art, on its present site at Montague House in London, United Kingdom, but also with the Library of CongressThe Library of Congress the unofficial national library of the United States, is one of the most important libraries in the world. Originally founded as a research library for the United States Congress April 24th 1800, its original collection were the bo; a popular retelling says that the monkeys would eventually type out the collected works of William Shakespeare.

The literary notion may have its origin in Jonathan SwiftJonathan Swift ( November 30, 1667 October 19, 1745) was an Anglo-Irish writer and satirist. Jonathan Swift was born, after his father had been dead for seven months, to an English mother, and educated by his Uncle Godwin. After a not very successful care's Gulliver's TravelsGulliver's Travels ( 1726/ 1735) is a work of fiction pseudonymously authored by the British satirist Jonathan Swift. The first edition was published in 1726 with major changes by the publisher, since he was afraid the book in its original version would o (1782), part three, chapter five, in which a professorA professor is a senior teacher and researcher, usually in a college or university. Overview Professors give lectures and seminars in their field of study, such as science or literature. They also do advanced research in their fields and are supposed to d of the Grand Academy of Lagado is attempting 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.

1 Proof sketch

The infinite monkey theorem is relatively straightforward to prove. If two events are statistically independent, meaning neither affects the outcome of the other, then the probability of both happening is eqivalent to 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.8, the chance of both happening on that same day is 0.3 × 0.8 = 0.24.

Now, suppose the typewriter has 50 keys, and the monkey is trying to type the word "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 gets larger and larger, this number X gets smaller and smaller. For an n of a million, X is 99.99%, but for an n of 10 billion it is 53% and for an n of 100 billion it is 0.17%. As n approaches infinity, the probability X asymptotically approaches zero. 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 produce a text as quickly as it would be produced by a 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 a monkey failing to reproduce a 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 certain they will do so.)

2 Probabilities

Ignoring punctuation, spacing, and capitalization, and assuming a uniform distribution of letters, a monkey 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 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 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. (We cannot resist the temptation to quote from A.N. Whitehead, 'I will not go to infinity'.)"

In The Nature of the Physical World: The Gifford Lectures (Macmillan, New York, 1929, page 72) the physicist Arthur Eddington wrote:

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

In physics, then, the force of the "monkeys argument" lies not in the probability that the monkeys will "eventually" produce something intelligible, but in the practical reality that they will not. 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. Even real monkeys are not immortal.

3 Myth about origins

It is often reported, though highly improbable, 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. 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. 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, in effect, that he would rather be descended from an ape than the bishop. 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.

4 Infinite monkey experiments

"The Monkey Shakespeare Simulator" website, 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. As of 20 October 2004, matches as long as 22 consecutive letters, four words have been recorded ("Cymbeline" "1.Gent. You do not mee]2:RX)i]aE5 ...") (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 certain value or value within certain range], the simulator simulates the match by generating matched text).

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 Macaque s 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.

5 Literature and popular culture

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 that theory. (He had heard the British Museum version of the story.) His monkeys immediately set to work typing 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 bowdlerized edition.

A similar theme was struck in the story " The Library of Babel" by Jorge Luis Borges, which contains billions of volumes filled with random strings 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 outnumbered by the gibberish).

Popular culture references to this theorem include The Simpsons (in one episode, Montgomery Burns has his own room with 1000 dactylographic monkeys, 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."), Family Guy (a group of monkeys is shown collaborating on a line from Shakespeare's Romeo and Juliet in a cut scene) and The Hitchhiker's Guide to the Galaxy ( 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). In the comic strip Dilbert, Dogbert tells Dilbert that his report would take "five monkeys, ten minutes."

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.

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.

A rather jocular quote by Robert Wilensky on the theorem is, "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."

Comedian Bob Newhart has a stand-up routine in which a lab technician monitoring an "infinite number of monkeys" experiment discovered that one of the monkeys has typed "To be, or not to be; that is the gezortenblatt."

6 References

No words to describe monkeys' play (9 May 2003) BBC News
Monkey Theory Proven Wrong (9 May 2003) CBS News
RFC 2795 — The Infinite Monkey Protocol Suite (IMPS)

7 External links

8 Footnotes

¹ To some lay persons, "infinite monkeys" and "infinitely many monkeys" may seem synonymous; to mathematicians, the former is incorrect because each individual monkey is finite. ² The word dactylographic appears in the English translation of Borel's book, and seems to be an Anglicization of a French word for typewriting, but in English, dactylography has come to mean the study of fingerprints. ³ Finding any given text may take a long time. Probability theory Thought experiments

<Hide>

Home > Infinite monkey theorem