Sunday, February 18, 2024

Infinite Monkey Theorem, Debunked

If you let a monkey hit random keys on a typewriter for an infinite amount of time, will it happen to write the complete works of Shakespeare? Common wisdom says that not only will it write Shakespeare, but it will “almost surely” type every possible text an infinite number of times.

The proof idea goes like this: the probability to produce a permutation matching the complete works of Shakespeare is very small, but still greater than zero, so it will “almost surely” happen.

This is assuming that the monkey will eventually produce such permutation with a non-zero probability.

What if some permutations are simply not possible? There could be several reasons why this particular monkey and this particular typewriter could not have written Shakespeare. In order of increasing complexity:

  • Some letters on the keyboard are broken, so some letters in the works of Shakespeare could not be typed.
  • Due to the clumsiness of the monkey, it is only able to hit the space bar before or after hitting the letters above it. This means that every word has to always begin and end with ‘z’, ‘x’, ‘c’, ‘v’, ‘b’ ‘n’, or ‘m’. Shakespeare often used words that do not satisfy this criteria, so the works of Shakespeare could not have been written.
  • The monkey is not able to repeat what it types within a certain number of words, so phrases like “to be or not to be” can never be written.

Infinity does not mean that it will allow every permutation. An example is the infinite sequence that concatenates the set of numbers consisting of only even digits: 0 2 4 6 8 20 22 24 26 28 40 42 44 46 48 etc. This sequence is infinite, but it would never contain the number ‘1’.

(On the other hand, the sequence of all even numbers concatenated will contain all finite numbers, including the odd numbers; since starting from 10—which is still an even number—we simply ignore the last digit and look at the tens and above, e.g. 123 is contained in 1230 1232 1234...)

This is not an argument about “almost surely” being practically zero. Instead, we are simply saying that infinite monkey is not almost surely, as the output is handicapped in some way albeit still infinite.

If we want to apply the infinite monkey theorem elsewhere, infinity alone is not sufficient. We have to also show that the desired permutation has a non-zero probability to happen, as this is not a given. On the contrary, an application that only establishes infinity can be disproven by showing that the desired output actually has a zero probability of happening.

∞ ⨉ 𝜀 = ∞ but ∞ ⨉ 0 = 0

In reality, we often confuse the mechanism of the permutation with the existence of output. We cannot say that the complete works of Shakespeare exists in the output implies that it must have been produced by the monkey. What if we have a programmed typewriter such that, if the monkey hits ‘s’ a million times in a row, would insert the complete works of Shakespeare? The complete works “exists” in the output, but it is not produced through the monkey's mechanism of permutation.

(This is analogous to the panspermia hypothesis saying that life could have been introduced from an external source rather than permuted naturally within the system. The hypothesis allows that a system capable of sustaining finite life may not have been able to produce life infinitely.)

Showing that some improbable event has zero probability of being produced could be quite difficult but “almost surely” doable. However, if we try to categorically argue that “almost surely” is practically zero, then the argument is only “almost surely” believable.

No comments: