# Infinite monkey theorem

(more precise) |
(move paragraph to better place) |
||

Line 6: | Line 6: | ||

In fact, in such an infinite sequence of events, any specified sequence must occur an infinite number of times! | In fact, in such an infinite sequence of events, any specified sequence must occur an infinite number of times! | ||

− | |||

− | |||

==Arbitrary events over time== | ==Arbitrary events over time== | ||

Line 14: | Line 12: | ||

When viewed from this perspective, the complete works of Shakespeare ''must'' (with probability one) result eventually simply because it is possible to ''intentionally'' type such a text in an appropriate amount of time (say, a year). Thus, random typing over the same time period must also be able to produce the same result with some positive probability. (Every possible collection of "Shakespearean-length" strings of characters would be equally likely in random typing, and one of those strings matches the works of Shakespeare, so the probability is one divided by the number of such collections of characters — a large denominator, to be sure, but not infinite and thus the probability is not zero.) The result then follows from the fact that an infinite amount of time can be divided up into an infinite number of such time periods (years, in this case). | When viewed from this perspective, the complete works of Shakespeare ''must'' (with probability one) result eventually simply because it is possible to ''intentionally'' type such a text in an appropriate amount of time (say, a year). Thus, random typing over the same time period must also be able to produce the same result with some positive probability. (Every possible collection of "Shakespearean-length" strings of characters would be equally likely in random typing, and one of those strings matches the works of Shakespeare, so the probability is one divided by the number of such collections of characters — a large denominator, to be sure, but not infinite and thus the probability is not zero.) The result then follows from the fact that an infinite amount of time can be divided up into an infinite number of such time periods (years, in this case). | ||

+ | |||

+ | Note that another setting involving a similar idea is looking for specific sequences of numbers in the decimal expansion of [[wikipedia:pi|pi]] (3.14159265...). Unfortunately, whether the digits of pi behave (in ways that are relevant to this discussion) like a random sequence of digits is currently [[wikipedia:normal number|an open question]]. | ||

==Applying the theorem in the real world== | ==Applying the theorem in the real world== |

## Revision as of 05:30, 23 October 2009

This article has been flagged as a **work in progress**.

The original author is still working on this article. Please direct all non-minor edits to the discussion page.

The **infinite monkey theorem** is a result in probability theory stating (informally) that any event that is at all possible must occur eventually, as long as one waits long enough. The name of the result is based on the popular notion that "a monkey typing randomly on a typewriter forever will eventually produce the complete works of William Shakespeare".

To state the theorem more formally, one must consider an unending sequence of random events (the pressing of random keys in this case), each of which has some chance of matching any of a set of possible outcomes (the letters of the English alphabet along with spaces and punctuation — note that for "random" typing, all individual keys are equally likely to be pressed, but this is not strictly required, as long as each key has some fixed, non-zero probability of being chosen at each step). The theorem then states that the probability that a specific sequence of interest (the string of characters comprising the works of Shakespeare) will appear somewhere in the unending sequence of random events approaches one (certain to happen) as the length of random events grows to infinity.

In fact, in such an infinite sequence of events, any specified sequence must occur an infinite number of times!

## Arbitrary events over time

This framework can be extended to any kind of event occurring over an infinite stretch of time. By considering as the sequence of random events the occurrence or non occurrence of the desired outcome in different periods of time (say, every second, or minute, or day, etc.), we can say that as long as there is some positive probability, no matter how small, that the event *could* happen in any given time period, then it *will* (almost surely) happen eventually, given an infinite amount of time to wait.

When viewed from this perspective, the complete works of Shakespeare *must* (with probability one) result eventually simply because it is possible to *intentionally* type such a text in an appropriate amount of time (say, a year). Thus, random typing over the same time period must also be able to produce the same result with some positive probability. (Every possible collection of "Shakespearean-length" strings of characters would be equally likely in random typing, and one of those strings matches the works of Shakespeare, so the probability is one divided by the number of such collections of characters — a large denominator, to be sure, but not infinite and thus the probability is not zero.) The result then follows from the fact that an infinite amount of time can be divided up into an infinite number of such time periods (years, in this case).

Note that another setting involving a similar idea is looking for specific sequences of numbers in the decimal expansion of pi (3.14159265...). Unfortunately, whether the digits of pi behave (in ways that are relevant to this discussion) like a random sequence of digits is currently an open question.