Shakespeare’s Nightmare: Monkeys on Typewriters

If the monkey could type one keystroke every nanosecond, the expected waiting time until the monkey types out Hamlet is so long that the estimated age of the universe is insignificant by comparison … this is not a practical method for writing plays.

Gian-Carlo Rota

Simpsons S04E17 – “Last Exit to Springfield”

The idea of Infinite Monkey Theorem goes as follows: if an infinite number of monkeys sit in front of an infinite number of typewriters and randomly push the buttons, they will eventually end up typing any desired text, such as the whole works of Shakespeare.

Nevertheless, the odds are not very much in favor of the monkeys getting to finish the job. This will become more clear after calculating the probability of a monkey randomly typing meaningful words and sentences.

If each typewriter has 26 buttons, representing all letters of the alphabet, then the probability of a monkey randomly pressing the button for a certain letter will be 1 in every 26 attempts or 1/26. Similarly, the probability for the monkey to push the button for a certain letter and then immediately another desired letter will be 1/26 * 1/26 . Continuing on this fashion we can easily calculate the probability of any monkey randomly typing any string of length n:

Infinite Monkey Theorem - probabilities

The probability for a random process to generate a word that has only 8 letters is 1 in 208,827,064,576, one in every 200 billion attempts. To get a sense of how improbable that can be, take into account that chances of you being hit by a lightning over your lifetime in the U.S. are 1 in 700,000. Although the probability converges very quickly to values very close to zero, but it is still not zero. So, we can safely assert that, no matter how long the string that we want to type is, there is still a very teeny tiny possibility of generating that string.

Bear in mind that we also assumed that there are only 26 buttons on the typewriter, while in fact a standard American typewriter has 44 keys on it. Relaxing this assumption will further lower the probability to a great extent.

Let’s simulate this process of random typing in Python to see how long it takes for some common words to appear for the first time. To do so, let’s consider one of Shakespeare’s famous quotes in Macbeth.

To-morrow, and to-morrow, and to-morrow,

Creeps in this petty pace from day to day,

To the last syllable of recorded time;

And all our yesterdays have lighted fools

The way to dusty death. Out, out, brief candle!

Life’s but a walking shadow, a poor player,

That struts and frets his hour upon the stage,

And then is heard no more. It is a tale

Told by an idiot, full of sound and fury,

Signifying nothing.

I will try to randomly generate some of the words used in this text as if they were randomly typed by a monkey sitting in front of a typewriter. The goal is to see how many attempts would it take for a random process to generate meaningful phrases.

Let’s jump to the code.

Copy Code


# Infinite Monkey Theorem

# Importing the required libraries
import random
import time

# The alphabet as a string
alphabet = 'abcdefghijklmnopqrstuvwxyz'

# Function to simulate the typing of monkeys
def monkeys(word):
    '''Simulates the process of monkeys randomly typing until the desired word is created. '''
    
    # Marking the starting time
    start = time.time()
    
    # Variable to count the number of attempts
    counter = 0

    # Monkeys will be typing as long as we have not arrived at the word
    while True:
        # choose n letters
        letters = random.choices(alphabet, k = len(word))
        
        # joing the letters together and if it is the same as the word we want, quit the loop
        if ''.join(letters) == word:
            break
        else:
            counter += 1
    
    # Mark the end of time
    end = time.time()
        
    # calculate the duration
    duration = round(end - start, 2)
    
    # return duration and attempts
    return duration, counter
    

# Variables to store the total time and total attempts
total_time, total_attempts = 0, 0

# Words to look for
words = ['to', 'of', 'an', 'and', 'day', 'the', 'this', 'pace', 'from', 'fools', 'dusty', 'death']

print () # print an empty line

# Check all the words
for word in words:
    # Set the random seed so that the results will be replicable
    random.seed(2021)
    
    # calculate the duration and attempts it takes to arrive at this word
    result = monkeys(word)
    
    # update the total time and total attempts
    total_time += result[0]
    total_attempts += result[1]
    
    # print the output for this word
    print ('Word: "' + word + '" | attempts:', str(result[1]), ' | time:', str(result[0]), 'seconds')

# separate the final output from the rest
print ('-----------------------------------------------------------------------------------------------------')

# print the total
print ('In total, it took', str(total_attempts), 'attempts and', str(round(total_time,2)), 
       'seconds to randomly generate all these', len(words) ,'words.')
    

# Words to look for
words = ['to', 'of', 'an', 'no', 'it', 'is', 'and', 'day', 'the', 'all', 'our', 'way', 'this', 'pace', 
         'from', 'last', 'time', 'that', 'fools', 'dusty', 'death', 'brief', 'idiot', 'sound']
    

words = ['to', 'of', 'an', 'and', 'day', 'the', 'this', 'pace', 'from', 'fools', 'dusty', 'death']

You will find out a detailed explanation of the code at the bottom of the page. For now, let’s focus on the results.

Words with two letters have been found in almost no time, and after very few attempts. Three lettered words are also generated in less than a second, but the number of attempts has significantly increased. There is a clear and strong increasing trend in values. The words consisting of four and five letters appeared after a longer time and with more attempts. In total, it has taken more than 20 million attempts and a little bit more than a minute to generate these words separately.

What about words consisting of six letters? The next experiment deals with four words containing six letters.

Only one letter difference and the required attempts and the needed time have increased dramatically. The random process took more than 716 million attempts and a little bit more than one and a half hours to result in the word “either”. Hmmm, 3.5 hours to generate only four words is … not the best kind of performance though.

Code explanation

Before defining the function, I import the required modules and store the letters of the alphabet in a string.
Then I define a function to simulate the random typing of a monkey, similar to what the infinite monkey theorem suggests. Inside the function, the code initiates by marking the starting time, and then enters a loop to choose n random letters from the alphabet list, where n is the length of the given word. These letters are then joined together to form a string, and if the resulting string is the same as the word we are looking for, the loop is terminated and the total time and attempts to arrive at this word are returned.
The code then loops in the given list of words, applies the defined function to them and then updates the respective variables for total time and total attempts. The loop ends by printing one line of output, describing the time in seconds rounded to two digits, and the number of attempts made for that word. The code ends after printing the total time and total attempts for all the words.