Ricochet is the best place on the internet to discuss the issues of the day, either through commenting on posts or writing your own for our active and dynamic community in a fully moderated environment. In addition, the Ricochet Audio Network offers over 50 original podcasts with new episodes released every day.
Weekend Geek: Strictly Speaking, One Immortal Monkey Would Suffice
This will be a recurring (maybe) series of posts on science, mathematics, and related topics. Apparently, there’s an appetite for this sort of thing at Ricochet. Who knew?
I can’t promise this will be a weekly feature, but call it one in a row so far. Some of you may be put off by math. I hope I can reel you in. Trying to discuss science without mathematics is a little like trying to discuss great works of art without seeing them or great musical works without hearing them. I’ll walk the reader through the math and make it as simple as it can be, but no simpler. Relax, you’ll love it.
Shall we begin?
Monkeying Around…
I’m sure we’ve all heard that “given enough monkeys with typewriters and enough time, they will eventually type the complete works of Shakespeare.” True or false? Not to get all Clintonian, but it depends on the meaning of the word “enough.” Some “scientists” have experimented with actual monkeys, only to find that they were more interested in breaking the typewriters and pooping on them. I certainly hope my tax dollars didn’t pay for that.
In another study, computer simulations were used to look for randomly generated sequences of 9 characters that would match something out of Shakespeare, so that they could be manually reassembled. Sorry, that’s cheating. First, computers are many orders of magnitude faster than live monkeys. Second, looking for short sequences in random order, then manually sorting and reassembling them, is vastly different from producing the complete works of Shakespeare, already arranged in the correct order, in one sequence.
Let’s forget about live, breathing, pooping monkeys for a bit. What we are really postulating is that a long enough sequence of random characters will contain the specific, non-random string we are looking for. This will be simpler if we start off small. Let’s assume we are typing only random digits and looking for the string “123” (just the numbers, not the punctuation). We might ask how long a sequence we would need to type to guarantee that string’s appearance. But it would be the wrong question. There is simply no finite length that would guarantee such a thing. The right question is framed in terms of probabilities.
Suppose you have a 1,000-digit sequence. What is the probability that the string “123” appears in it somewhere? There are 998 possible starting locations where it could appear. The probability that the string appears somewhere is equal to one minus the probability that it does not appear anywhere. This, in turn, is equal to the probability that the sequence does not appear starting in location 1 times the probability that it does not appear starting in location 2, and so on, up to location 998.
The formula is as follows, both symbolically and numerically (stay with me, you can do this):
L = Length of the sequence = 1,000 digits
N = Length of the desired string = 3 digits
K = Number of possible values of each digit = 10
p = Probability that one particular string out of the sequence matches the desired string
p = 1/K^N = 0.001 (I am using ^ to signal an exponent – Ricochet apparently doesn’t do superscripts)
p’ = Probability that one particular string out of the sequence does not match the desired string
p’ = 1-(1/K^N) = 0.999
P’ = Probability that no string out of the sequence of length L matches the desired string
P’ = [1-(1/K^N)]^(L-N+1) = 0.999^998 = 0.368432
P = Probability that at least one string out of the sequence of length L matches the desired string
P = 1 – [1-(1/K^N)]^(L-N+1) = 1 – 0.999^998 = 0.631568
Now, let’s go the other direction. Suppose that instead of postulating the length of the sequence, you postulate a probability that the string appears. To determine the minimum length of the sequence, you just solve the last of the above equations for L. I’ll do it by witchcraft, for now, to save you a bit of time:
L = K^N ln [1/(1-P)] + (N-1) where ln is of course the natural logarithm. This works if you plug in the above numbers:
K^N ln [1/(1-P)] + (N-1) = 10^3 ln [1/(1 – 0.631568)] + (3-1) = 1000.5 (chalk up the .5 to roundoff error).
Now, back to the original problem.
I found a file containing the complete works of Shakespeare on the Internet. Deleting the legal notices and other blurbs, Word counts 4,927,356 characters, including spaces. Old typewriters tended to have around 51 keys on the keyboard, counting the space bar, shift, shift lock, and return keys (for those with electric return). I have little basis for the following assumption other than gut feeling, but let’s say around 1% of the characters in Shakespeare require use of the shift or shift-lock key. Let’s assume the monkey is not going to hold down a shift key while typing other keys; we are assuming one key at a time, so a capital letter requires pressing the shift lock key, then the desired letter, then the shift key to release the lock. We therefore increase the number of characters by 2%: 1.02 x 4927356 = 5,025,903 keystrokes. How long would it take one monkey with a 51-key typewriter to have a 90% chance of producing the complete works of Shakespeare?
P = 0.90
N = 5,025,903 keystrokes in Shakespeare’s complete works
K = 51 keys to choose from on the keyboard
L = K^N ln [1/(1-P)] + (N-1) = 51^5,025,093 (2.30258) + 5,025,902.
The result L (the total number of keystroke typed) can be expressed in scientific notation as 2.711 x 10^8,582,082, an unimaginably large number (this was determined using logarithms, which are essential for numbers like this that are way too large to calculate directly).
Assuming our persistent primate can type 10 keystrokes per second nonstop (equivalent to about 120 words per minute), he can manage 864,000 keystrokes per day and 315,576,000 keystrokes per year, and will have a 90% chance of honoring William in just 8.6 x 10^8,582,073 years. Time to hire some extra help!
We’re a bit fuzzy on global monkey population numbers. We tend only to count the endangered species. But let’s assume a billion monkeys can be rounded up and put to work. All work tirelessly and ceaselessly, without pausing to eat, sleep, poop, or make new monkeys. So divide the required length of time by one billion. Now, only 8.6 x 10^8,582,064 years will be required. Most likely, within ten thousand (10^4) years the works of Shakespeare will have been forgotten; within one billion (10^9) years monkeys will be extinct; and within ten billion years (10^10) the earth will have been swallowed by the sun. Therefore, for all practical purposes, “enough” monkeys with “enough” time cannot possibly produce the works of Shakespeare, although Finnegan’s Wake wouldn’t take very long (read a few pages of it, you’ll see what I mean).
Ah, but what about infinite monkeys with infinite time? That’s different. Go back to the probability equation:
P = 1 – [1-(1/K^N)]^(L-N+1)
Notice that the quantity (1/K^N) is extremely small, but greater than zero. So the quantity [1-(1/K^N)] is less than one. As L approaches infinity (mathematicians never like to talk about a number “equaling” infinity), the quantity [1-(1/K^N)]^(L-N+1) approaches zero, so the probability P approaches 1, or certainty. Note that infinite monkeys are not required. One monkey with infinite time will reproduce the complete works of Shakespeare, as well as the complete works of Marcel Proust, and every other work of literature that has ever been written or could be written (although I wish the monkey wouldn’t bother with Naked Lunch), backwards and forwards, with and without every possible spelling error, in English and every other language that exists or doesn’t exist, within the limitations of the character set available on the monkey’s typewriter.
If you have an infinite number of monkeys, you only need a finite period of time. The number of keystrokes required to produce the works of Shakespeare can be performed in 5.8 days, by my reckoning. If you set an infinite number of monkeys to the task, at least one of them will do just that.
Published in General
About the author:
I am a licensed professional engineer with over 30 years of experience in mechanical engineering in the electric power industry, mostly in nuclear power. I have been working on cars since I was a teenager, have rebuilt a few engines and transmissions, and do most of my own repairs on household appliances, although there are a few recalcitrant items like iPods that mock my feeble attempts to repair them. I have always been fascinated by science and math. I also love to cook (and eat, obviously), and I am unfortunately getting a little too good at both.
There is a really great story from io9 about this whole thing. I actually took part in a distributed computing project about 15 year ago called “The Monkey Shakespeare Simulator”. The simulator assumed 1 million monkeys on 1 million typewrites per user and despite turning out 10^35 pages of words the longest string they reached was only 23 characters.
“It was the best of times, it was the blurst of time?! You stupid monkey!”
When anyone does “blurst” into the room is usyally when the people already there clear out, and quickly.
“A vast, poor Urich, I threw him, Horatio.”
“I find it difficult to imagine you being able to do that, Hamlet.”
Bob Newhart did a skit about this years ago that ends “to be or not to be, that is the gazornanplatz”
Insects could do a better job than monkeys. They were actually considered for one experiment. It went back and forth between the scientists and the mathmaticians. To bee or not to bee that is the question?
Give one monkey a crayon and about 5 minutes and it will create the wisdom of Joe Biden.
For a more realistic question, how many lifetimes (using today’s actuarial tables) would I have to live to have a 90% chance of winning a 10 million dollar lottery? I have tried to no avail to explain “odds” to my wife but the standard retort is ” somebody is going to win it”. She has used up only about half a lifetime trying to find the answer.
Very cool. Thank you. No doubt replacing the monkey with a computer generating random key strokes would not solve the problem in reasonable time either. Some numbers are just unimaginably large.
An infinite (but by nature countable) arrangement of letters containing the complete works of Shakespeare could be assembled from one monkey’s infinite string, or from infinite monkeys’ finite strings.
(EDIT: Though if a monkey typed forever… yes, I guess it could be uncountable… for example strings of ones and zeros that never terminate…)
I have trouble with the statements I read about infinite random sequences. While it is exceedingly likely that an infinite sequence will contain any arbitrary n-character string you want, there is no guarantee that any individual length n substring would match your target. Therefore I reason that there is no guarantee that every possible string is present, however likely it may be.
To put it another way, though highly improbable, it’s possible for an infinite string of random characters to be a repetition of “Spaulding, get your foot off the boat!” forever. Nothing against Ted Knight, but such a string would not contain any works of Shakespeare.
Which raises another set of questions: Is the string of characters countably infinite? In an infinite string of random characters could you find any other arbitrary infinite string of random characters? Does it also contain any possible semi-infinite string?
“Alas, poor ape, how thou sweat’st.” Henry IV, Part II
Perhaps a sly self-reference by the real author.
You wascally wabbit! What is your physics doing in my math? ;-)
There’s a big difference between an infinite supply of monkeys and one monkey with infinite time–if you’re sitting there waiting for Hamlet to emerge. Seems like you’ll forever be stuck in the state where, to quote another great work of English lit, tomorrow is only a day away.
Of course, we limit this to Shakespeare, but you get to Hamlet you might just have to read the Feminine Mystique or any number of Paul Krugman columns.
To be fair the probability of this happening really depends more on the kind of monkey you are using than anything else. After all the works were originally created by a kind of monkey. Presumably if one employs a similar breed the results should be forthcoming.
While that is theoretically possible, the probability of the string repeating approaches zero as the length of the string approaches infinity.
I think so. Since keystrokes are discrete, you can always devise a way to count them.
I don’t see how you could make a case for either of those, especially if you dispute the idea that you could find any other finite string. There are some things about infinity that we simply cannot know. This may be one of them.
BSB,
You’re assuming, of course, that the monkey sits there and types. Unfortunately, there are an infinite number of other things that a monkey could do to and with a typewriter, most of which entail destroying it for all of eternity. So, I’m not buying it.
“Semi-infinite string” was a physics joke – wave equations :-)
Right, I covered that in the first paragraph. You have to assume that the monkey is an extremely efficient typist. Even with optimal assumptions, I show that it takes forever.
I would like to thank whoever edited this piece and added the picture (which I tried to do at 1:00 AM and failed). I’m thinking Claire, since I can’t imagine who else would be up at that time of night.
I observe the experiments being carried out on Twitter…
That hurt my head. I may have to read some Vogon Poetry to cleanse the mental pallet.
A clever old design engineer told me when I was a pup that the proper sales pitch at the beginning of any project is: Given enough time, we’ll come up with something. Many years later, on receiving ill-deserved praise for finally figuring out a long-standing, nettlesome hitch in the giddyup, I restated that as: We don’t so much solve problems here as outlast them. I see we were underselling the thing.
On the other hand, a friend’s stock-in-trade for keeping a project from going irretrievably wrong was to demonstrate that a proposed solution required a number of discrete steps to completion equal to Avogadro’s constant. Pretty sure he would counter this conceptual threat with: “and where, sir, may I obtain such a quantity of monkeys? And is there a volume discount?” Or maybe he’d just use my dad’s counter to the supposed implication of Brownian motion that all the molecules in the room might end up in the corner: “no, they won’t.”
Laugh while you can, Monkeyboy.
Which folio?
You’re so welcome, it was a pleasure!
With those working conditions, those monkeys will unionize a long time before they finish Shakespeare.
Hold on, I just got confused. I’m not getting the part where the probability of the string repeating approaches 0 as L approaches infinity. Why does that happen? (Or wait–you must mean the probability of the string only repeating, which would make perfect sense. Is that right?)
If I’ve got that right, then Mark, yes, it’s what he said–as L approaches infinity, the quantity approaches 0, and P approaches one–and that’s why they don’t like to talk about “equalling infinity”–it screws up the idea of probability and leaves you with “theoretically possible” without showing just how unlikely it is even if possible. (I mean, I guess physicists spend do spend a lot of time wondering what really happens out there in asymptotically-approaching-zeroland, but come on, how is that as practical as coming up with an elegant little formula that tells us how many monkeys we actually need to hire here. Really. Head-in-the-clouds physicists.)
At which point you would get Marx and Engells and Gorky?