A little Markovian problem
Here it is:
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
![Input: digraph G {
graph [rankdir=LR]
{0 H HH HHT [shape=doublecircle]}
0 -> H [label=H]
0 -> 0 [label=T]
H -> HH [label=H]
H -> 0 [label=T]
HH -> HH [label=H]
HH -> HHT [label=T]
}](wp-content/cache/f151847dd4f5adb6d5a138ee4e318e12.png)
Player B
![Input: digraph G {
graph [rankdir=LR]
{0 H HT HTH [shape=doublecircle]}
0 -> H [label=H]
0 -> 0 [label=T]
H -> H [label=H]
H -> HT [label=T]
HT -> HTH [label=H]
HT -> 0 [label=T]
}](wp-content/cache/df43149372f6033610ee6b9ee0c87df5.png)
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
![Input: digraph G {
graph [rankdir=LR]
{0 H HH}
0 -> H [label=H]
0 -> 0 [label=T]
H -> HH [label=H]
H -> 0 [label=T]
HH -> HH [label=H]
HH -> 0 [label=T color=blue]
}](wp-content/cache/1f05e52fe69f93b1f3ca986f4916b9b8.png)
Player B
![Input: digraph G {
graph [rankdir=LR]
{0 H HT}
0 -> H [label=H]
0 -> 0 [label=T]
H -> H [label=H]
H -> HT [label=T]
HT -> H [label=H color=blue]
HT -> 0 [label=T]
}](wp-content/cache/2485278455bd040486cf9dd6cb8c2592.png)
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.
