"Ford!" he said, "there's an infinite number of monkeys
outside who want to talk to us about this script for Hamlet they've
worked out."
Douglas Adams, The Hitchhiker's Guide to the Galaxy
(1979).
This quote is perhaps the most famous reference to the Infinite
Monkeys Theorem. This theorem states that if you put an infinite
number of monkeys behind typewriters, eventually one will write the
script for Hamlet. Alternatively a finite number of monkeys with
infinite time will also accomplish this. The implication is that a
problem or task of any complexity can be solved using brute force
trial-and-error, even without intrinsic knowledge of a system, nor
the intelligence to adapt to a situation.
The infinite monkeys theorem applies to (generally large)
systems where the dataset is either sampled entirely in a systematic
manner, or completely at random.
An example of sampling the entire dataset is finding a computer password
or cryptographic key by brute force; one would simply try all possible
character combinations (e.g.: aaaa,aaab, aaac...) until the proper
solution is found. This would take a very long time, especially
if there is no additional information about the length of the password,
or the characters that are allowed. Nevertheless, this technique can be
quite effective for smaller datasets. For instance, if the Coca Cola
company wants to introduce a new beverage, they may survey people about
a few of the properties of the drink, such as color, flavor, and
carbonation. If each property has two options, they could do a market
survey on the entire dataset, and serve the survey group a total of 8 drinks:
- Lemon / Yellow / Carbonated
- Lemon / Yellow / Non-Carbonated
- Lemon / Red / Carbonated
- Lemon / Red / Non-Carbonated
- Raspberry / Yellow / Carbonated
- Raspberry / Yellow / Non-Carbonated
- Raspberry / Red / Carbonated
- Raspberry / Red / Non-Carbonated
Using common sense, a researcher would only consider yellow lemon
or red raspberry drinks, but the general idea is clear. For
larger numbers of combinations in the dataset, this method becomes
impractical very quickly. If we want to survey another property, the
number of drinks doubles (24 = 16). If there are three
choices for each category, the number of possibilities increases to
33=27.
An example of random sampling of a large dataset is (to a certain
degree) evolution. The combination of different genetic material, and
mutations allow for a seemingly infinite number of genotypes,
each of which are more or less adjusted to a dynamic environment (not
taking into account the factors that make up natural selection).
Another example in this category is the mathematics of irrational numbers such as e, and pi. It is often assumed that pi is a normal number, i.e. any arbitrary, finite string of digits is represented
somewhere in the digits of pi. The string of digits could be your
phone number, social security number, or even Hamlet in ASCII values. However, there is no formal proof of this yet.
One final example in the time domain is the prophecies of
Nostradamus. Given a final number of arbitrary, vague prophecies, and
an infinite amount of time, each and every prophecy will prove to be
true.
The history of the infinite monkeys theorem is not entirely
known. Most certainly, Douglas Adams is not the source of the
theorem, as it was reported much earlier than that. It may be as old as
the typewriter itself. Or perhaps one of the infinite monkeys
scribbled it into the soil with a stick a few thousand years ago.
However, the first historical notion of the infinite monkeys theorem
is in French, by Emile Borel1 (1913):
... Concevons qu'on ait dressé un million de singes
à frapper au hasard sur les touches d'une machine à
écrire et que, sous la surveillance de contremaîtres
illettrés, ces singes dactylographes travaillent avec ardeur dix
heures par jour avec un million de machines à écrire de
types variés. Les contremaîtres illettrés
rassembleraient les feuilles noircies et les relieraient en volumes. Et
au bout d'un an, ces volumes se trouveraient renfermer la copie exacte
des livres de toute nature et de toutes langues conservés dans
les plus riches bibliothèques du monde. Telle est la
probabilité pour qu'il se produise pendant un instant très
court, dans un espace de quelque étendue, un écart notable
de ce que la mécanique statistique considère comme la
phénomène le plus probable...
Let's consider that we trained one million monkeys to
randomly strike the keys of a typewriter, and that under surveillance of
illiterate foremen the monkey typists ardently work for ten hours per
day on one million typewriters. The illiterate foremen would collect the
blackened sheets and compile them into volumes. And after one year,
those volumes would contain the exact copy of books on any subject,
in any language, in the largest libraries around the world. This is the
probability that occurs during one very short moment, at some place, a
remarkable event that statistical mechanics considers to be the event
with the highest probability
The first mention of the infinite monkeys theorem in English
is attributed to Sir Arthur Eddington2 (1929):
...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.
There are numerous other mentions of the infinite monkeys
theorem; too many to sum up. Although one of them I found
particularly interesting: L. H. C. Tippett was a statistician who was the
first to produce a large table with random numbers for
statistical purposes (in fact, the table consisted of 41 600) numbers.
On one occasion, Tippet was introduced by Edward Condon, the director
of the Bureau of Standards. Condon illustrated the idea that random
events by chance may lead to a meaningful sequence, such as the
possibility that a monkey may write a Shakespeare play. Referring to the
book of random numbers, he then remarks that in fact Tippett had
written a book that could have been produced by a monkey.
Another interesting writing on the infinite monkeys theorem is
by the poet Lucio3, regarding an address at the British Association for
the Advancement of Science (a.k.a. the British Ass.). The
second two stanzas are:
Give me half a dozen monkeys
Set them to the lettered keys
And instruct these simian flunkies
Just to hit them as they please
Lo! The anthropoid plebians
Toiling at their careless plan
Would in course of countless aeons
Duplicate the lore of man
Thank you, thank you, men of science
Thank you, thank you British Ass!
I for long have placed reliance
On the tidbits that you pass
And this season's nicest chunk is
Just to sit and think of those
Six imperishable monkeys
Typing in eternal rows
And since we're on the topic of poetry, allow me to close by quoting
a Dilbert comic strip4, where Dilbert writes a poem and presents it
to Dogbert.
DOGBERT: I once read that given infinite time, a thousand monkeys
with typewriters would eventually write the complete works of
Shakespeare.
DILBERT: But what about my poem?
DOGBERT: Three monkeys, ten minutes.
Factual Sources:
1: Émile Borel, ``Mécanique Statistique et Irréversibilité,''
J. Phys. 5e série, vol. 3, 1913, pp.189-196.
2: A. S. Eddington, The Nature of the
Physical World: The Gifford Lectures, 1927. New York: Macmillan,
1929, page 72.
3: Warren Weaver, Lady Luck, Anchor Books, Garden City,
NY, 1963, 239-240
4: Scott Adams, Dilbert comic strip, 15 May 1989.
http://www.research.att.com/~reeds/monkeys.html (many more examples of the infinite monkeys theorem)
William S. Peters, Counting for Something - Statistical Principles and Personalities, Springer Verlag, 1986