How to (Randomly) Write Shakespeare

Take an immortal monkey, and have it bang on a typewriter from now until the end of time, then eventually the monkey would produce the complete works of Shakespeare. The saying goes something like that. Human’s aren’t really good at imagining things that are infinite, so while the saying appeals to some sense of intuition that we have about rare events eventually happening given a long enough time frame, it’s hard to imagine how randomly typing on a keyboard would eventually produce a coherent work of art. Even after an infinite amount of time.

You can read wikipedia about this theorem and almost surely you’ll find a bunch of gobbledy-gook and precise computations that are meaningless to the casual reader. “Okay, blah-blah-blah, the theorem is true, I’m getting a Starbucks.” I can relate, much of my undergrad felt that way. Sorry casual reader, this post is more gobbledy-gook, but I think it’s intuitive gobbledy-gook.

We can reframe the infinite-monkey theorem as follows: Consider a random string of $n$ letters, where $n$ is a positive integer. Let $p_n$ be the probability that the $n$ letters have substring of consecutive letters that spell out some phrase we care about. For example, take $n = 10$ , and let our phrase be the word “fun”, then $p_{10}$ is the probability that 10 random letters spells out the word “fun” somewhere inside. We can see pretty clearly that if $n < 3$ , then $p_n = 0$ , since there aren’t enough letters to actually spell our word “fun”. But when $n \geq 3$ , then $p_n$ is meaningful, since there is a non-zero probability this could happen. There is at least one way a random sequence of 10 letters could spell out “fun” somewhere in the middle. In other words, if you give your toddler a bunch of scrabble tiles, and ask her to spell out some random words for grandma, there is a non-zero probability your toddler is about to embarrass you.

So, this let’s us conclude that for $n \geq 3$ , we have $p_n > 0$ . However, this probability is very small. To see this, let’s think about how many different strings of length $3$ we could make. Since there are 26 letters in the alphabet, we have 26 choices for the first letter, 26 for the second letter, and 26 for the third letter to give $26^3 = 17576$ total choices. But there is only one way to spell “fun”, so the probability for $n = 3$ ends up being $p_3 = \frac{1}{17576}$ . This is basically a lottery.

However, if $n = 4$ , then we can spell “fun” in several ways. We could spell it as `Xfun’, or `funX’, where X is just some random letter. How many total ways can we do this? Well, for `Xfun’, the first letter is irrelevant, so there are 26 possible choices there. Then there is only one choice for the next letter, one choice for the third letter, and one choice for the last letter (`f’, `u’, `n’, respectively). So we end up with $26 \cdot 1 \cdot 1 \cdot 1 = 26$ ways to do this. In the second case, where X comes last, we also have 26 ways to spell `fun’. Then we have $26 + 26 = 52$ possible ways to spell `fun’ out of $26^4$ possible ways. So the probability ends up being $p_4 = \frac{52}{26^4} = \frac{2 \cdot 26}{26^4} = \frac{2}{26^3} = \frac{2}{17576} > p_3$ .

Huh.

So even though the increase in probability is minuscule, there is still an increase. Now if we had a monkey typing for an infinite amount of type, we are essentially letting $n \rightarrow \infty.$ Does it now follow that $p_n \rightarrow 1$ ? In other words, if we let $n$ get bigger and bigger, so the probability we see the word `fun’ appear somewhere in the n-string get better and better?

Actually, yes.

Intuitively we might see why this is true. The larger $n$ is, the more ways we can have the word `fun’ appear somewhere in our string, which is pretty fun itself. But does it work for some sequence of arbitrary length? Can it? Hamlet is about 130,000 words, does it make sense to talk about this?

Yes. We can prove this.

II.

We will prove that if we have some fixed string of $m$ letters (we’ll call this a phrase), and a random string of $n \geq m$ letters, then the probability the $n$ letter string contains the fixed sub-string of $m$ letters converges to 100% as $n$ is allowed to grow to infinity. That is, we will show that $p_n \rightarrow 1$ as $n \rightarrow \infty,$ where $p_n$ is the aforementioned probability.

Let $m$ be positive integer and consider a fixed phrase of $m$ letters in some order we care about. Define $p_n$ as the probability a random string of $n \geq m$ letters contains a sub-string of $m$ letters spelling out our desired phrase. We know that $p_n > 0$ , at least, but we can also show that it is an increasing function of $n:$ if we have $n + 1$ letters, the phrase could appear in the first $n$ letters with probability $p_n$ . If not in the first $n$ letters, then the last letter of the phrase would have to be the $(n + 1)$ th letter, which happens with some probability $q_n > 0.$ Since these events are mutually exclusive, we add them and get: $p_{n +1} = p_n + q_n > p_n.$

So, our sequence of probabilities $\{ p_n \}$ is an increasing sequence. From elementary real analysis, if we can find a sub-sequence contained in $\{ p_n \}$ which converges to $1 ,$ then the entire sequence converges to $1$ .

What kind of sub-sequence does this? Consider $p_{mn}$ , the probability of the desired phrase appearing in a string of length $m\cdot n.$ If $a$ is the probability a randomly selected string of length $m$ does not contain our desired phrase, then $a < 1$ . We can split up our string of length $m \cdot n$ into $n$ strings of length $m$ , so then the probability our desired phrase appears in at least one of these $n$ strings has probability

$1 - a^n \leq p_{mn} \leq 1.$

Since $a < 1$ , letting $n \rightarrow \infty$ implies $a^n \rightarrow 0$ . By the squeeze theorem $p_{mn} \rightarrow 1$ as $n \rightarrow \infty$ , but $\{ p_{mn} \}$ was a sub-sequence of $\{ p_n \}$ , so $p_n \rightarrow 1$ .

III.

Notice that we actually never specified $m.$ It was left as some arbitrary integer. If $m = 130,000$ , the proof still works, so we’ve actually proved that our immortal typing monkey can write Shakespeare on a long enough time frame. In fact, the monkey can type any particular text of finite length (if $m = \infty$ , then it’s not clear what happens next).

This proof is a generalization of an exercise I saw in the (excellent) book A Walk Through Combinatorics. Turns out counting is pretty fun. Who knew?

***

Even though the book is eventually written in the limit, the probabilities for any finite $n$ are extremely small. We probably can’t expect it to happen, even if we had an astronomical amount of monkeys typing until the heat death of the universe. Still neat, though.

How to (Randomly) Write Shakespeare

Published by Nathan

Leave a comment Cancel reply

Share this:

Related

Published by Nathan

Leave a comment Cancel reply