A has a fair coin and B has a fair coin. They flip coins together, but only keep track of their own sequences of heads and tails. A stops if the sequence “HHT” appears. B stops if the sequence “HTH” appears. Which player is more likely to stop first?

While it would first appear that any 3-flip sequence is equally likely and so neither A nor B is more likely to stop before the other, this is wrong. The eight 3-flip sequences are only equally likely when taken independently of the remaining sequence context. By context, I mean there is a time origin in this problem and there is memory from the stopping 3-flip sequence that leads all the way back to it.

The answer is found if we draw the state diagram of the game for each player.

Player A

Player B

They are pretty much the same, except A’s diagram has a transition that backtracks by one state where the analogous transition on B’s diagram backtracks by two. So indeed, A is more likely to stop first.

An interesting thing happens if we let A and B continue flipping even after they are supposed to stop. This changes the destination of one transition in each state diagram. Now the two diagrams look more similar.

Player A

Player B

In fact, they are equivalent (after a rotational shift of the states). So asymptotically, the sequence “HTH” occurs just as frequently as “HHT”.

If we look at this a little more carefully, we find that it takes on average 8 flips to see the first “HHT” while it takes an average of 10 flips to see the first “HTH”. After that, however, both subsequences occur at a rate of every 8 flips (overlapping frames allowed), which of course makes perfect sense, since there are 8 such 3-flip sequences.