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.
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:
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,
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.
# 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 total_attempts += result # print the output for this word print ('Word: "' + word + '" | attempts:', str(result), ' | time:', str(result), '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.
- 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.
Also watch about Infinite Monkey Theorem
Family Guy S01E15 referencing the Infinite Monkey Theorem.
This one is a little bit strange though.