Mathematics, philosophy, code, travel and everything in between. More about me…

English | Czech

Of Macbeth And 100,000 Monkeys (Maths For Normal People II)

Do you know what the largest natural number is? Where do the borders of the infinite realm lie? And how many monkeys does it take to write the complete works of Shakespeare? Come hither, ye finite mortal, and behold the glory of eternity that men have created in their minds!

In the previous article, we have been discussing only finite sets. Let us now take a look at the most basic of infinite sets – the set of natural numbers.

And So On

Natural numbers, or positive whole numbers, have been known for millennia. Everyone intuitively knows them. How many natural numbers do we know? We could start naming them one after one: 1, 2, 3, 4, 5, 6,… and so on. What does “and so on” mean? In this particular case, it means that if you add one to 6, you get a 7 which is also a natural number, and if you add one again, you end up with 8 which is natural as well. And so on.

This is a particular instance of inductive definition of a set. We define natural numbers in two steps (see my article What Are Natural Numbers for a more rigorous treatment):

1. “1” is a natural number,
2. if “$n$” is a natural number, then “$n + 1$” is natural as well.

Number 1 is natural by the first statement. Number 2 ($=1+1$) is natural by the second statement if we let $n = 1$, which we can do since we already know that 1 is natural. Number 3 ($=2+1$) is natural by the second statement if we let $n = 2$. And so on.

The set of all natural numbers is denoted $\mathbb{N}$. We could write $\mathbb{N} = \{1, 2, 3, 4, 5, \ldots\}$, where the dots stand for “and so on”.

The Boundary Of Infinity

Where am I going with all this? I am building up to an obvious conclusion: the set of all natural numbers is not finite, because there is no “largest natural number”. If you say that 999,999,999,999 is the largest, I say I can add one to it and get a still larger number. If you say that $N$ is the largest, I come up with $N + 1$. Whenever you take a set of numbers from 1 up to $N$, you have a finite set containing $N$ numbers. If you go from 1 to $N + 1$, you still have a finite set. Whether $N$ is a few million, a few billion, or a few billion billion billion, the set $\{1, 2, 3, \ldots, N\}$ is always finite and could be “counted” if you happen to have enough fingers. Since there is no upper bound to $N$ you can create your sets as large as possible. But they will always be finite.

People are often awed by big numbers and think that when you put many zeroes after a one you somehow get something huge. That is child’s play. Every finite number is ridiculously small when compared to infinity. You can keep adding as many zeroes as you want, but you can never make a finite number infinite. In other words, infinity cannot arise from anything finite. There is a gaping abyss between the world of finite and the world of infinite.

In theory, we could physically construct any finite set, e.g. by piling up enough rocks. In practice we would run into problems with petty physical constraints, like the limited number of atoms in the observable universe (only about $10^{80}$), but in theory, we can “touch” any finite set. But there is no conceivable way of actually “creating” an infinite set. It is an elusive idea arising only in our minds, and it is not possible to pinpoint the border between $\{1, 2, 3, \ldots, N\}$ and $\{1, 2, 3, \ldots\}$, however large $N$ may be.

The Number Of All Natural Numbers

The cardinality, or size of $\mathbb{N}$ is denoted by a Hebrew letter called Aleph, with a subscript of zero:

$$|\mathbb{N}| = \aleph_0$$

What we do here is we call infinity a number. $\aleph_0$ is the count of all natural numbers, and as such it is a number, even if it is infinity. This might be hard to believe, but just as 4 is a number, 234.18 is a number, $\frac{3}{4}$ is a number, infinity is also a number. A very strange number, but a number never the less.

The Largest Natural Number

If you have read about the standard construction of natural numbers, you know that every natural number contains all its predecessors ($n = \{0, 1,\cdots, n-1\}\,\, \forall n \in \mathbb{N}$). In the light of this fact, $\aleph_0$ might be called “the largest natural number”, since it contains all its predecessors – the whole infinity of them. The largest natural number is actually infinity. Doesn’t it sound unnatural? I don’t know about you, but I think this idea is goddamn beautiful! :-)

Of Macbeth And 100,000 Monkeys

To better understand the unfathomable size of infinity, let’s perform a small thought experiment. I shall prove the following eccentric statement:

If there are infinitely many monkeys and each one of them randomly hits a key of a typewriter, they are instantly going to produce the complete works of Shakespeare.

Let’s forget for a while about the complete works and start with Macbeth. The play opens with the following verses by the First Witch:

When shall we three meet againe?
In Thunder, Lightning, or in Raine?

There are 26 upper case and 26 lower case English letters, plus punctuation marks like commas, question marks etc. All in all, we can safely assume that a typewriter with 64 different keys is sufficient for typing all Shakespeare’s works.

When a monkey randomly hits a key on a typewriter with 64 keys, it has a chance of 1 in 64, or about 1.56%, of hitting “W”, the first letter of the play. On the other hand, the chances of hitting any other letter are 63 in 64, or 98.44%. Now we need to think a little about combining probabilities.

Probability Intermezzo

1. If we have two independent random events, we can calculate the probability of them happening at the same time by multiplying their particular probabilities. For instance, the probability of rolling a dice and getting a five is one in six, or $\frac{1}{6}$. The probability of tossing a coin and getting tails is one in two, or $\frac{1}{2}$. If we roll the dice and toss the coin at the same time, the probability of getting a five and tails equals $\frac{1}{6}\cdot\frac{1}{2}=\frac{1}{12}$, or one in twelve.
2. The probability of an event not happening is calculated by subtracting the probability that it does happen from one. For instance, the probability of throwing anything else than five on a dice is $1-\frac{1}{6}=\frac{5}{6}$, and the probability that we get any other combination that tails and five with our coin and dice is $1-\frac{1}{12}=\frac{11}{12}$.

With these rules in mind, we can derive that the probability of the first monkey hitting “W” and the second monkey hitting “h” at the same time are $\frac{1}{64}\cdot\frac{1}{64}=\frac{1}{4,096} \approx 0.0244\%$. The probability that they type a different combination is $1-\frac{1}{4,096} = \frac{4,095}{4,096} \approx 99.9756\%$. The probability of the first four monkeys hitting “W-h-e-n” is calculated the same way:

$\frac{1}{16,777,216}$ equals about 0.000005960464477539%, which makes this event really unlikely. On the other hand, the chance that the monkeys will write anything else than “When” is $1-\frac{1}{16,777,216} \approx 99.999994\%$. Don’t bet your money on randomly typing monkeys.

The whole play of Macbeth has a little over 100,000 characters (letters). If we wanted to calculate the probability that 100,000 monkeys won’t get it right, we just need to multiply $\frac{1}{64}$ 100,000 times and subtract it from one:

$$1 - \left(\underbrace{\frac{1}{64} \cdot \frac{1}{64} \cdot \ldots \cdot \frac{1}{64}}_{100,000 \text{ times}}\right) = 1 - \frac{1}{64^{100,000}} \approx 100\%$$

This number is so close to 100% that the difference is not imaginable at all. But it is crucial that the difference is there. If you give typewriters to 100,000 chimps, you cannot be absolutely sure that they won’t produce Macbeth!

Now, say that instead of 100,000 monkeys you have 100,001. How does it affect their chance to type the play? Monkeys 1 to 100,000 can give it a shot with the minuscule probability we have just calculated. But wait! What if only the first monkey messes up and all the monkeys from 2 to 100,001 get it right?

Now there are two possibilities how Macbeth can be typed. Therefore, the probability that it won’t be typed is a little different. In accordance with our first rule of combining probabilities, we have to multiply the two particular probabilities. Obviously, the probability that monkeys 2 to 100,001 get it wrong is the same as that monkeys 1 to 100,000 fail, so we just multiply the same number twice:

$$\left(1 - \frac{1}{64^{100,000}}\right) \cdot \left(1 - \frac{1}{64^{100,000}}\right) = \left(1 - \frac{1}{64^{100,000}}\right)^2$$

When a number is a little less than one, its square is a little less than the original number (for example, $0.9^2 = 0.81 < 0.9$). Therefore, the probability that 100,001 monkeys fail is a tiny bit smaller than the probability that only 100,000 monkeys fail. The difference is extremely small, but it is there.

What if we had even more monkeys? What about $N$, where $N$ may be any natural number greater than 100,000? The probability of their failure will be

$$\underbrace{\left(1 - \frac{1}{64^{100,000}}\right) \cdot \left(1 - \frac{1}{64^{100,000}}\right) \cdot \ldots \cdot \left(1 - \frac{1}{64^{100,000}}\right)}_{N \text{ times}} = \left(1 - \frac{1}{64^{100,000}}\right)^N$$

What happens if we let $N$ grow more and more? We already know that squaring a number less than one makes it smaller. The same applies for higher powers.

$$1 - \frac{1}{64^{100,000}} > \left(1 - \frac{1}{64^{100,000}}\right)^2 > \left(1 - \frac{1}{64^{100,000}}\right)^3 > \cdots > \left(1 - \frac{1}{64^{100,000}}\right)^N$$

The more we increase $N$, the more the probability of failure drops. For any finite $N$, it will remain positive. But if we had infinitely many monkeys (i.e. if $N$ were infinite), the probability of failure would be exactly zero. In other words, in the infinite sequence of monkeys there would be a successive 100,000 of them that would type Macbeth in the exact wording of William Shakespeare.

Note well that by multiplying $\left(1 - \frac{1}{64^{100,000}}\right)$ any number of finite times can never get you zero. That is a mathematical impossibility. You can get as close to zero as you want to, but unless you “multiply infinitely many times”, the probability will always be positive. “Multiplying infinitely many times” has a rigorous mathematical definition, but we don’t have to worry about it here (if you insist: $\lim_{n \to \infty} x^n = 0 \,\, \forall x \in (-1,1)$).

Let’s now return to the complete works of William Shakespeare. All together they have more than 5.5 million characters. Does it seem like a lot? Much bigger than Macbeth?

No. For our infinite band of monkeys armed with typewriters, no book is too long. The probability that 5.5 million monkeys type the complete works at random is obviously much smaller than 100,000 monkeys typing Macbeth. It is only

$$\frac{1}{64^{5,500,000}}$$

If you wanted to write this number down, you would write “0.”, then almost ten million zeroes, and then some tiny decimal digits.

But you know what? We don’t have 5.5 million monkeys. We’ve got infinitely many of them, and the rule about raising numbers smaller than one to different powers still holds:

$$1 - \frac{1}{64^{5,500,000}} > \left(1 - \frac{1}{64^{5,500,000}}\right)^2 > \left(1 - \frac{1}{64^{5,500,000}}\right)^3 > \left(1 - \frac{1}{64^{5,500,000}}\right)^4 > \cdots$$

And so does the rule about “infinite multiplication”. Just keep multiplying the probabilities for ever and you will get zero in the end. Well, there is no end, but you get the point.

Every finite quantity is ridiculously small compared to infinity, and in a sense, contained in it.

Our Knowledge Is But A Drop In The Ocean

One last thing for you to think about. Imagine the complete human knowledge written down in some huge library. Every single piece of information the humankind has ever discovered or created. Every single word that has ever been uttered on planet Earth, every single vision that could have been seen, every single sound that could have been heard, every single character that has ever been written.

The amount of all this information, however vast it may be, is finite. Whenever you think of the set of natural numbers, you have casually created in your mind something that can contain the whole human existence like a drop of water in an ocean without any boundary.

The power of thought?

March 13, MMXI — Mathematics, Maths For Normal People, Infinity.