Let's imagine a very simple typewriter that has only the 26 upper-case letters, a space bar and five punctuation characters (a total of 32 buttons). It doesn't even have a carriage return -- it does an automatic return when the required number of letters have been typed, and it has an infinite roll of paper being fed through it. We have a monkey that knows how to press the keys and will do so in a totally random manner indefinitely. All in all, we have a little bit of machinery, but no real intelligence in the system. We want our monkey to type the following snippet: "TO BE OR NOT TO BE, THAT IS THE QUESTION."
The probability of this happening is quite simple to calculate, and this will in turn give us some idea of how many monkeys and typewriters we need for a reasonable chance of success. Place your bets now -- our monkeys are fast typists and can type the required number of characters in a single second (there are 41 keystrokes)! On average, how long will it be before one of our monkeys produces a line matching the above sentence?
Well, there are 32 keys, so starting at any moment, the chances of our monkey getting the first keypress right are one in 32. Not good, but we have fast monkeys and lots of time. However, once it has got the first keystroke right, we also need the second keystroke to be right, otherwise we are back to square one. The chances of it getting the first
and second keystrokes right are only one in (32*32 = 1024). Only one chance in 1024, but still lots of time to get it right. To get the first
three characters right will be a one in (32*32*32 = 3276
chance. Each time it presses a key, there is a one in 32 chance that it will be correct. To get our little snippet of Hamlet, it will need a total of 41 consecutive "correct" keystrokes. This means that the chances are one in 32 to the power of 41. Let's look at a table of values.
Keys Chances (one in...) ------------------------------------ 1 32 2 32*32 = 1024 3 32*32*32 = 32768 4 32*32*32*32 = 1048576 5 32^5 = 33554432 6 32^6 = 1073741824 7 32^7 = 34359738368 8 32^8 = 1099511627776 9 32^9 = 3.518437208883e+013 10 32^10 = 1.125899906843e+015 ... 20 32^20 = 1.267650600228e+030 ... 30 32^30 = 1.427247692706e+045 ... 41 32^41 = 5.142201741629e+061 ... 204 32^204 = 1.123558209289e+307 The last figure is included only because it is the largest value that the MS Windows calculator can handle -- it's doing better than my hand-held Casio (old faithful!) which only goes up to 1e+99. Okay, so these figures are pretty vast, but we have a lot of monkeys and they can type fast. So how long will it take, on average, for one of my monkeys to type a line matching that sentence? Hard question. Let's get an idea of how long we are talking here. How many lines can my monkey type in a year, given that it types at a rate of one line per second?
1 line per second * 60 seconds per minute = 60 lines per minute * 60 minutes per hour = 3600 lines per hour * 24 hours per day = 86400 lines per day * 365.24 days per year = 31556736 lines per year Okay, now for the moment of truth. We know how many possible different lines can be produced, hence how likely it is for us to get the right one at random (because only one is right). We can calculate the chances of getting the quote in a year most easily by calculating the chances of missing on every attempt: the chances of getting the quote will be 100% minus the chances of missing on every attempt. I need a really amazingly precise calculator to do this because the chances of missing are so close to 100% that most calculators will round it off to 100%. The calculation is as follows.
probability of missing on one attempt = 1 - 1/(32^41) ...of missing for a minute straight = (1 - 1/(32^41)) ^ 60 ...of missing for an hour straight = ((1 - 1/(32^41)) ^ 60) ^ 60 ...of missing for a day straight = (((1 - 1/(32^41)) ^ 60) ^ 60) ^ 24 ...for a year straight = ((((1 - 1/(32^41)) ^ 60) ^ 60) ^ 24) ^ 365 If you have access to Unix, you can calculate this with the dc command, but be warned that it may take quite a while to calculate and annoy other users because the computer is so slow. Use of the nice command is suggested. The syntax, should you care to try, is as follows. Type the dc command, then type the following lines.
99k 1 1 32 41 ^ / - 60 ^ 60 ^ 24 ^ 365 ^ p The figure that is eventually printed will be the probability (expressed as a value between zero and one) of our monkey
not typing our little phrase from Hamlet in the space of one year's worth of continuous attempts. The answer that it prints looks like this:
0.999999999999999999999999999999999999999999999999999999386721844366784484760952487499968756116464000
Notice all the nines? Even to fifty or more significant figures, this reads 100%. Okay, so realistically, there is no way that our monkey can do its job in a year. Maybe we should start talking centuries? Millenia? As I understand it, common scientific wisdom suggests that the universe is about 15 billion years old (although they may have revised their dating since I last heard about it). We can easily extend our current figure of one year to count many years. Our calculator will be much faster if we break the calculation down to powers of two and just use the "square" operation, so let's choose a nice even power of two like 2^34, which is about 17 billion (17,179,869,184 to be precise). The new figure is:
0.999999999999999999999999999999999999999999989463961512816564762914005246488858434168051444149065728
The chances of failure are still essentially 100%, even after 2^34 years. Hmmm. It doesn't look like were are going to get very far with this, but just for the heck of it, let's see if we are any better off with a lot of monkeys. Let's not hold back here -- I hypothesize 17 billion galaxies, each containing 17 billion habitable planets, each planet with 17 billion monkeys each typing away and producing one line per second for 17 billion years. What are the chances of the phrase "TO BE OR NOT TO BE, THAT IS THE QUESTION."
not being included in the output?
0.999999999999946575937950778196079485682838665648264132188104299326596142975867879656916416973433628
I'd bet money on that. It's about 99.999999999995% sure that they would fail to produce the sentence. Are you astounded? It's such a trivial requirement, right? Just one puny sentence. And yet the figures keep coming up "impossible". Where have we made a mistake? We have fallen into the same trap as the politician who was the subject of my joke, way back up there. We have failed to appreciate the sheer magnitude of the problem. Let's look at it one more time.
The number of 41-character strings that are possible with a 32-character alphabet is 32^41. According to dc, this value is as follows.
51422017416287688817342786954917203280710495801049370729644032
In case you don't feel like counting, this value is 62 digits long. In our hypothesising above, we imagined 17 billion galaxies, each with 17 billion planets, each with 17 billion monkeys, each of which was producing a line of text per second for 17 billion years. How many lines of text did we wind up producing in this experiment? The math is as follows:
2^34 * 2^34 * 2^34 * 2^34 * 365 * 24 * 60 * 60
And the answer is as follows:
2747173049143991138247931294711870033017962496000
Once again, in case you don't feel like counting, the answer is 49 digits long. Now, there is no guarantee that our monkeys are going to type something different every time, but even if we managed to rig up the experiment so that they never tried the same thing twice, they have still only produced 1/18,718,157,355,362 of the possible alternatives. The denominator in that fraction is 14 digits long, by the way. It's a figure that's vastly bigger than anything you would come across in the real world. Is it any wonder, in light of that, that it is so damn hard to get the right answer by accident? "
