Probability Puzzler 8 - Which comes first?

Posted Friday, December 2 (solutions by evening of Thursday, December 8)

The puzzle: Fr. Jenkins and Dean Crawford are playing with coins. Fr. Jenkins has a fair coin, and keeps tossing it until he sees the pattern Tails, Heads, Tails in consecutive order. Dean Crawford also has a fair coin, and he keeps tossing it until he sees the pattern Tails, Heads, Heads in consecutive order.

Which of the follow statements in correct?

  1. On average, Fr. Jenkins sees his pattern before Dean Crawford sees his. (Formally: if J is the number of tosses until Fr. Jenkins sees his pattern, and C is the number of tosses until Dean Crawford sees his, then E(J) < E(C).)
  2. On average, Dean Crawford sees his pattern before Fr. Jenkins sees his. (E(C) < E(J).)
  3. There is no difference between the average times until they each see their respective patterns. (E(J)=E(C).)

A solution: It might seem at first glance that there should be no difference in expected times, since each party is looking for a string of length 3 involving a 2-1 split between the two sides of a coin. But it turns out that Dean Crawford expects to see his pattern before Fr. Jenkins sees his.

Here is one way to see it. Both players need to see the string TH to begin their run of three, and since it's the same initial string for both, they both expect to see it at the same time. So we might as well assume that both of them *start* by throwing TH. The question is then, which of the two expects to reach their goal more quickly, given this start?

Starting from TH, Fr. Jenkins has a .5 chance of finishing up on the very next toss, by tossing T. Dean Crawford also has a .5 chance of finishing up on the very next toss, by tossing H. So to seperate the two, we need to look at what happens in the case when they each fail to finish on the very next toss.

In the case of Fr. Jenkins, he fails by tossing H. So now, his expected wait time is the time it takes him to toss his full sequence of THT (the H he has just tossed doesn't help him any, since it was immediately preceded by another H).

The situation for Dean Crawford is rather different. He fails by tossing T. This helps him, because his desired string starts with T. So now, to finish up, he is just waiting to see the lenght two string HH (note that he does not need to see this immediately - whatever he tosses from here on, it is true that the first time he sees HH must coincide with the first time that he sees THH; his first occurence of HH must have a T in front of it, since if it didn't, there would have been an earlier occurence of HH).

So the question of who finishes first has now reduced to the question of which string we expect to see first: THT (for Fr. Jenkins) or HH (for Dean Crawford). It should be clear that HH is likely to occur before THT, but lets make it formal.

By symmetry, the expected time to HH is the same as the expected time to TT. Both THT and TT begin with T, so, as before, we may as well assume that the new game begins with a T, and we are asking which comes first (on average): T or HT. By symmetry, HT is the same as TH. But now its clear which comes first: it's T.

So, working back through all of these reductions, we find that Dean Crawford expects to see his string before Fr. Jenkins sees his (option 2).

One can do this calculation quite explicitly, to discover that E(J) = 10 while E(C) = 8.

The phenomenon of different strings of the same length taking different times (on average) to appear was first noticed by the mathematician Walter Penney in 1969; see this Wikipedia page. It featured in a wonderful TED talk by Peter Donnelly, on how statistics can sometimes be used to fool us.

Solvers: