A friend told me about an interesting problem that can be solved easily using martingales. I’ll start with the problem and solution, and then I’ll talk a bit about martingales in general. (That’s all I can do; I don’t know much about them.)
Problem: A monkey is sitting at a typewriter, typing a letter (A-Z) independently and with uniform distribution each minute. What is the expected amount of time that passes before ABRACADABRA is spelled?
Solution: Suppose that, before every keystroke is made, a new monkey enters and wagers $1 on the next keystroke being an A fairly (so that if the keystroke is indeed an A, then the payoff is $26). If the keystroke is an A, the monkey stays and wagers everything (in this case $26) on the next letter being B, and so on. If the monkey ever loses a wager, then it leaves. Now let’s analyze what happens when ABRACADABRA is finally spelled out. The monkey who kept making correct wagers all the way through won $ . But another monkey who got in on the second ABRA won $ , and a third monkey who got in on the final A got $26. Hence the total payoff is $ . But all the wagers are fair, and the house gets $1 on every turn from the new monkey, so the expected time before ABRACADABRA is spelled is .
I’m trying to figure out intuitively why the expected time should be longer than . Here’s my best understanding of it: if a lot of random letters are typed, then on average ABRACADABRA will be about as common as any other 11-letter string. However, they’ll be clumpier than some other strings, since we’ll see some instances of ABRACADABRACADABRA, which contain ABRACADABRA twice. But we can never clump, say, AAAAAAAAAAB more densely. Therefore, although the number of occurrences should be roughly equal in the limiting case, one can clump more easily than the other, so it should take more time to the first occurrence of ABRACADABRA than to the first occurrence of AAAAAAAAAAB.
In fact, we can make this clumping relationship even clearer with the following question: Suppose we have only two letters, A and B, and a monkey randomly types them. What is the probability that BA occurs before AA? The answer is for a rather simple reason: if the sequence does not begin with AA, then there will be a B before the first occurrence of A, so BA will occur before AA unless the sequence starts with AA, which happens only of the time.
Now on to martingales. A martingale is a sequence of random variables so that the expectation (and ). In this case, the random variables for each monkey are the payoffs after wagers by that particular monkey. If the wager is going to be made, then , and is going to be with probability and 0 with probability . Thus . Hence this chain is a martingale.
9 comments
Comments feed for this article
Wednesday, March 5, 2008 at 1:25 pm
Chocolatecoveredvegan
I’m with you on the croissants. I especially love chocolate ones! The chocolate-covered vegan likes chocolate croissants?! Shocking, I know ;o).
Monday, April 7, 2008 at 3:16 am
Anna
Well, I find it extraordinarily interesting
Monday, April 21, 2008 at 9:10 am
forum algerie
very interessting, thank you very much
Tuesday, June 17, 2008 at 10:55 am
ChocolateCoveredVegan
Thanks for the info on the coconut ice cream… I’ve never seen that brand in my Whole Foods, but if I ever chance upon it, I’ll buy it up for sure.
Thursday, June 19, 2008 at 12:26 am
Discourage
Somehow i missed the point. Probably lost in translation 🙂 Anyway … nice blog to visit.
cheers, Discourage.
Saturday, July 18, 2009 at 5:42 pm
Paul
Hey nice post. I have thought about this problem a few times over the years. Here’s another way to see why a redundant word has a longer expected time to appear. Suppose the monkey manages to type ABRACADABR, but makes a mistake on the A, typing some other letter L instead. Since L is not A, he has to wait till the next letter to get another chance at typing ABRACADABRA. If on the other hand the monkey is trying to type ABRACADABRQ, and he mistypes the Q at the end, there is a 1/25 chance that his mistake is the letter A, which will allow him to make another attempt immediately. Thus on average, the monkey gets to retry typing the phrase ABRACADABRQ more frequently than he does ABRACADABRA.
What bugs me about this problem is that I would not easily come up with the clever martingale solution. It is possible to solve this problem mechanically (i.e. brainlessly) via Markov chain modeling. However, you have to solve a structured but nontrivial 11×11 linear system to get it that way.
So there’s a brainless but somewhat difficult way, and an elegant way requiring more cleverness than I can routinely muster. It seems to me that this often happens in martingaley problems, and I wonder if there is a mechanical method to determine the martingale needed for the martingale solution.
Friday, July 9, 2010 at 6:15 am
Big numbers and failure of intuition | Quasi-Coherent
[…] we’d expect this to take. (The possible overlaps make the computation a bit tricky (but see my essay on Martingale Monkeys for a more detailed explanation), so we can assume that if the complete works of Shakespeare […]
Thursday, November 10, 2011 at 12:23 pm
beni22sof
This post might be related. http://mathproblems123.wordpress.com/2010/09/16/martingales-applications/
Friday, June 28, 2013 at 4:36 am
Dr S Singh
Here’s a rigorous solution to the problem
http://www.quanttraining.com/quant-puzzles/abracadabra-part-2/