Imagine tossing a coin repeatedly until you get a certain pattern, let’s say HTT (head, tail, tail).
For example, in this sequence of outcomes:
HHTHHTHHTT
the desired pattern was reached after the 10th toss (highlighted in red).
Now let’s imagine you repeat that same experiment and each time you record the number of tosses required to see the desired pattern. The first time you might see HTT after 10 tosses (as in the example above), the second time you might see HTT after 7 tosses, the third time after 15 tosses, etc. After many such experiments, you calculate the average number of tosses needed to see the HTT pattern.
At the same time, imagine your friend conducts the same number of experiments but she’s looking for a different pattern: HTH (head, tail, head).
Here’s the question: on average, will it take more flips to see HTT than HTH, or vice versa, or about the same number of flips to see both patterns?
If you’re impatient, try this software simulation (which I’ve written for today’s puzzle) and the answer will reveal itself. Each test runs 1,000 trials.
| Pattern | Trials | End of Last Sequence | Average Flips per Trial |
|---|---|---|---|
| HTT | |||
| HTH |
Solution
If you didn’t figure this one out, you’re in good company. Most people think it should take the same number of tosses to see both patterns, however, as the software simulation above shows, on average, it takes more tosses to see HTH (10) than HTT (8). Here’s why...
Imagine you’re waiting for HTH and you see a head followed by a tail. You’re two thirds of the way there! On the next toss one of two things will happen:
- It’s a head, in which case you’re done.
- It’s a tail, in which case you have to start all over again.
Now imagine the same scenario when you’re looking for HTT. You see a head followed by a tail, at which point you are, again, one toss away from success. Again, there two possibilities on the next toss:
- It’s a tail, in which case you’re done.
- It’s a head, in which case you don’t have to start all over again, because you’re already one-third of the way toward a new HTT sequence.
A failed HTT sequence overlaps with the next potentially valid sequence. This fact gives HTT a small built-in advantage over HTH.