The Infinite Monkey Paradox
Infinite Monkey Paradox

March 29, 2022

Share this article:

To most people the notion of infinity is unfathomable. That has to do with the strange behavior some things demonstrate when the concept of infinity is introduced. Think for example of an infinite time horizon. No one knows what it feels like for an infinite amount of time to pass. Maybe reality does not have a notion of infinity. In mathematics however, the notion of infinity is explored in much depth. One field of mathematics where infinity holds a lot of importance in particular is statistics. The Infinite Monkey Paradox is an example of infinity in statistics that seems counterintuitive and impossible at first, but after looking at the mathematics involved it might convince you.

Statistical convergence

The idea of infinity in statistics is often expressed through the theory of convergence. The methods of convergence that are most known are, convergence almost surely, convergence in probability and probability in distribution. In the Infinite Monkey Paradox we will need the notion of convergence almost surely. Let us consider a sequence of random variables (X_n). Then X_n converges to X almost surely if

    \[P\left( \lim_{x \rightarrow \infty} X_n = X \right) = 1.\]

This means that as n goes to infinity the probability that the event X_n is not equal to X happens with probability 0. To get a better feel for this we consider the following example. We start by tossing a fair coin. If the coin lands heads up then X_1 = \frac{1}{1}, but if the coin lands tails up we have  X_1 = - \frac{1}{1}.  After this we toss the coin again. If the coin lands heads up then X_2 = \frac{1}{2}, but if the coin lands tails up we have  X_2 = - \frac{1}{2}. We repeat this process by first tossing a coin and then assigning a value to X_n. Hence we find

    \[X_n = \begin{cases} \frac{1}{n} & \text{if the coin lands heads up} \\ -\frac{1}{n} & \text{if the coin lands heads up}. \end{cases}\]

We then use a theorem that states that absolute convergence to 0 implies convergence to 0. When looking at the sequence |X_n|, this is deterministic. As n goes to infinity we have that \frac{1}{n} goes to 0. Hence we can conclude that \lim_{x \rightarrow \infty} X_n = 0. This means that X_n goes to 0 almost surely. 

A problem involving the digits of pi

We will start by looking at a problem similar to the Infinite Monkey Paradox. Consider any integer. Then, it is believed that that integer will appear in the digits of \pi with probability 1. This, however, has not been proven yet. To prove this statement one will need to prove the normality of \pi. That is, all numbers 0 through 9 will appear infinitely many times in the digits of \pi and are distributed uniformly.

Let us assume that \pi is normal. Then take the integer 123 as an example. If we are ignorant and do not know what \pi looks like, but only that it is normal, we start at a point in the digits of \pi with a 1. The probability of finding such a point is 1/10. The probability that this 1 is followed by a 2 is 1/10. Furthermore, the probability that the sequence is followed by a 3 is 1/10 again. Hence the probability of this block of 3 numbers (123) appearing is (1/10)^3. So the probability of a given block of 3 digits not being 123 is 1 – 1/1000. Since the digits are independent of each other the probability of the sequence 123 not appearing in n blocks of 3 digits is (1 - 1/1000)^n. As \pi has infinitely many digits this probability goes to 0 as n goes to infinity.

Hence the probability of the pattern 123 appearing in the digits of \pi goes to 1. Since 123 was just an arbitrary example one can show that this holds for any finite pattern of numbers. The only thing that remains is to prove that \pi is normal, which is a very difficult task. 

The Monkey and the Typewriter

The Infinite Monkey Paradox is very similar to the problem described above. Consider a monkey behind a typewriter. This monkey hits one of the keys at random. Assume that the monkey has an equal probability to hit each of the keys. Now we let the monkey press keys in an infinite amount of time to create a sequence of symbols. Then the Infinite Monkey Paradox states that the monkey will type any given text almost surely. An example of this is the article that you are reading right now. This seems impossible at first, but is correct according to our notion of infinity.

Consider a standard typewriter with 50 keys and once again consider the pattern 123. Since the monkey hits each key with equal probability the probability that the monkey types a 1 is 1/50. The probability that this is followed by a 2 and then a 3 is (1/50)^3. So the probability that a given block of 3 symbols is not 123 is (1 – (1/50)^3). Since there are infinitely many independent blocks of 3 symbols the probability that at least one of these blocks is 123 is 1. Hence the probability that the monkey types exactly this article, symbol for symbol, is equal to 1. Now it seems rather cruel to force a monkey to type for eternity, so maybe the next time we consider this experiment we can let a computer do all the work. 

Read more

The fourth side of a triangle

The fourth side of a triangle

Yes, you are reading this correctly: a triangle can have four sides. If this sounds strange, I have to agree: this statement could be formulated in a more nuanced way: when we look from the point of view of the associated circles to the sides of a triangle, the fourth...