Which pattern comes before? - Tossing fair coins

Question

Suppose you are tossing a fair coin again and again.

The problem is: If you choose one pattern among following 8 patterns of$$HHH, HHT, HTH, THH, HTT,THT,TTH,TTT$$ where H denotes head and T denotes tail, then I can always find another pattern such that my pattern comes before your pattern with probability strictly greater than 1/2.

I could do it for $HHH$; if you choose $HHH$, then I choose $THH$. The probability of $THH$ coming before $HHH$ is greater than 1/2; unless the first three results are all $H$, which is of probability 1/8, $THH$ comes before $HHH$.

By a similar argument, I could solve it for $TTT$. However, I find it puzzling when it comes to other cases. Any good idea? Thanks and regards.

By the way, this problem is from Weighing the odds by David Williams.

Answer 1

You can do the same thing for $HHT$ (and likewise for $TTH$) as you did for $HHH$. If I choose $HHT$, choose $THH$; unless the first two results are both $H$, with probability $\frac14$, $THH$ comes before $HHT$.

More generally, you want the longest prefix of mine to be a suffix of yours and the shortest possible suffix of mine to be a prefix of yours.

So if I choose $HTT$, you want $HT$ as a suffix and neither $TT$ nor $T$ as a prefix, so you choose $HHT$. If I choose $HTH$, you want $HT$ as a suffix and ideally neither $TH$ nor $H$ as a prefix; since you can't avoid both, you avoid the longer one, $TH$, and again choose $HHT$.

To calculate the winning probabilities in these cases, label the possible non-terminal states according to the two most recent results, and note that since both our patterns start with $H$, the initial state is equivalent to $TT$. From this state, we get back to the same state as long as we get $T$, so at some point we end up in the state $TH$. Now consider the next two results:

• With probability $\frac14$ we immediately get my pattern.
• With probability $\frac14$ we immediately get your pattern.
• With probability $\frac14$ we get $HH$ and then eventually get your pattern.
• With probability $\frac14$ we get the remaining possibility ($TH$ in the first case, $TT$ in the second case) and either immediately or eventually return to the state $TH$.

Thus, every time we reach the state $TH$, you have twice my chance of winning, so you win with probability $\frac23$ and I win with probability $\frac13$.

By the way, note that this shows that not only the winning probability but also the expected duration of the game depends on the patterns. The only difference between the two cases was that if I choose $HTT$ and you choose $HHT$, we immediately return to $TH$ in the fourth option, whereas if I choose $HTH$ and you choose $HHT$, we eventually return to $TH$ after first reaching $TT$, so the expected duration of the game is longer in the second case.

Answer 2

From here:

An easy way to remember the sequence for using as a bar trick is for the second player to start with the opposite of the middle choice of the first player, then follow it with the first player's first two choices.

So for the first player's choice of 1-2-3 the second player must choose (not-2)-1-2 where (not-2) is the opposite of the second choice of the first player.1

An intuitive explanation for this result, is that in any case that the sequence is not immediately the first player's choice, the chances for the first player getting their sequence-beginning, the opening two choices, are usually the chance that the second player will be getting their full sequence. So the second player will most likely "finish before" the first player.1