June 25, 2013

Since I have just reviewed ‘Probability with Martingales’ I thought it would be nice to add one of the most famous puzzles in the book to the puzzles page.

If at each of times  1,2,3,.. a monkey types a capital letter at random. What is the expected time for the monkey to first produce the letters ABRACADABRA. On the face of it this is a hard question but martingale theory makes it easy. We can turn this question into a stopping time question about a  fair game.

Let $$T$$ be the stopping time when the monkey first produces the letters ABRACADABRA.  Just before each time n = 1,2,3,… a new gambler arrives on the scene. He bets £1 on the nth letter being an ‘A’. If he loses he leaves, if he wins he receives £26 all of which he bets on the (n+1)th letter being a ‘B’. If he loses he leaves, If he wins he receives £26 * £26 and bets the entire amount on the (n+2)th letter being an ‘R’ and so on going through the letters of ABRACADABRA and then finally leaving if he gets that far. The key observation is that this is a fair game and that at each time, n, the total amount gambled (by all the gamblers) is n. The expected value of this game to the gamblers must be zero since it is a fair game.

At the stopping time $$T$$

the payout to the gambler who has guessed ABRACADABRA is $$26^{11}$$

the payout to the gambler who has guessed ABRA  is $$26^4$$

and the payout to the gambler who has guessed A is $$26$$

The house has received $$T$$ and since it is a fair game

$$\mathbb E [T] = 26^{11}+ 26^4 + 26$$

in ABRACADABRA: Part 2 we will re-do this question with a bit more rigour.

Tags:

Category: Probability, Quant Puzzles