INFINITE MONKEY THEOREM
By: Patrick Cuthbertson 2014
EXPLANATION
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text. Common examples of the works are the complete works of William Shakespeare or all of the books in the British Museum. In the context of the theorem, almost surely means that it happens with probability one, and the monkey is a metaphor for a purely abstract random sequence generator.
HISTORY
One of the earliest instances of the infinite monkey theorem is attributed to French mathematician mile Borel, who used it in his 1913 article Mcanique Statistique et Irrversibilit. He used it as a comparison to show that even though it would be highly unlikely for a million monkeys typing in a random fashion to recreate all of Shakespeares works, it is even more unlikely that the laws of statistical mechanics would ever be violated. Also, he used to illustrate examples of geometric distributions when the number of trials is infinite.
PROOF
A simple proof of this theorem stems from the probabilities of independent events.
Suppose that the chance of there still being snow on the ground tomorrow is .83 and the chance of drawing a king out of a deck of cards is 1/13, then the chance of both happening is .83 x 1/13 = .0638.
Now suppose that the typewriter has 63 keys, and the word to be typed is hamlet. If the button presses are random and independent, then the chance that the first letter typed is h is 1/63, and the chance that the second letter typed is a is also 1/63, and so on. So, 1 1 1 1 1 1 the probability of typing hamlet is 63 63 63 63 63 63 = 1.59939 1011 . Thus, the chance of not typing hamlet is 1 1/636 and the chance of not typing 1 hamlet after n trials is (1 6 ) .
63
So as n increases, the chance of not typing hamlet decreases, such that when n = 100 billion, the chance of not typing hamlet is .202099. So, the chance of having hamlet typed on that trial or before that trial is .796901.
APPLICATION TO MATHEMATICS
The infinite monkey theorem is a useful device to show the power of a geometric distribution such that the cumulative distribution function shows that the larger the number of trials, n, the greater the probability of at least one success on or before the nth trial. This allows for an eventuality of anything almost surely happening. This knowledge of geometric distributions and how they function when the number of trials approaches infinity, can be used in various other applications, such as in random document generation, where programs generate random sequences of letters, numbers, and symbols to try to simulate what it would be like if this was actually attempted. It can also be used to test random number generators using overlapping m -tuple tests, which concern overlapping m-tuples of successive elements in a random sequence.
SOURCES
http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Infinite_monkey_theorem.html
