Did you solve it? The infinite monkey theorem

Earlier today I set you the following puzzle, based on the idea that a monkey sat at a typewriter bashing random keys will eventually type out the complete works of Shakespeare. Here it is again with the solution.

The magic word

A monkey is sitting at a typewriter that has only 26 keys, one per letter of the alphabet. The monkey types at random, with a constant speed of one letter per second. It favours no letters: all letters at any second have a 1/26 probability of being typed.

Which of the following is greater?

a) the average time it will take the monkey to type “abracadabra”

b) the average time it will take the monkey to type “abracadabrx”

Before I get to the answer, some clarifications. When I say ‘the average time it will take the monkey to type abracadabra’, I do not mean how long it takes to type out the word ‘abracadabra’ on its own, which is always 11 seconds (or 10 seconds since the first letter is typed on zero seconds and the 11th letter is typed on the 10th second.) I mean the average of the time it takes to get to an ‘abracadabra’, either from the beginning of the experiment or from a previous appearance of ‘abracadabra’. Another way of phrasing the question would be: over the long run, which of ‘abracadabra’ or ‘abracadabrx’ appears more frequently? The one that is more frequent is the one it takes, on average, less time to get to.

Second, if the monkey types ‘abracadabracadabra’ this only counts as one ‘abracadabra’. Likewise, ‘abracadabrabracadabra’ is only one ‘abracadabra’. In other words, the monkey needs to type the word ‘abracadabra’ completely, and that counts as one appearance, and then the monkey needs to type it completely again for the next appearance.

Answer: a) is greater. On average we will have to wait longer for the monkey to to type ‘abracadabra’ than ‘abracadabrx’

Workings: A good way to approach this problem is to consider what happens when the monkey has typed ‘abracadabr’.

Case 1: we’re looking at the average time it takes the monkey to type ‘abracadabra’.

If the monkey types an ‘a’, it has typed ‘abracadabra’. We’re done. If it doesn’t type an ‘a’, it fails and must start over. Either way, the monkey starts from scratch.

Case 2: we’re looking at the average time it takes the monkey to type ‘abracadabrx’.

If the monkey types an ‘x’, it has typed ‘abracadabrx’. We’re done. If it doesn’t type an ‘x’, it fails. But it does not start from scratch! There is a 1/26 chance the monkey will type an ‘a’, and if the monkey types an ‘a’, it will start from ‘abra’, in other words, with four letters in place already.

This reasoning explains why ‘abracadabra’s happen less often on average than ‘abracadabrx’s.

In fact, on average, you will get an ‘abracadabrx’ about five days sooner than an ‘abracadabra’ – even though the average time it takes to get either of them is around 100 million years.

How do I know? The calculation appears in a new puzzle book The Price of Cake: And 99 Other Classic Mathematical Riddles, by Clément Deslandes and Guillaume Deslandes. Their explanation of the solution goes into more detail than I have done here, and if you are interested in knowing more, I recommend it.

I hope you enjoyed today’s puzzle. I’ll be back in two weeks.

I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.

I give school talks about maths and puzzles (online and in person). If your school is interested please get in touch.