Pick Your Triple Second

  • Hard
  • Probability puzzles
  • Tests: Seeing that "first to appear" is not transitive

The puzzle

You pick a sequence of three coin tosses, such as HHH. I then pick a different one. We toss a coin repeatedly, and whoever's sequence appears first wins.

Each sequence has probability 1/8 of appearing in any particular three tosses, so the game looks fair. Show that the second player can always win more than half the time.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

If you pick HHH, consider THH. What has to happen for HHH to appear first?

Hint 2

HHH can only win if the very first three tosses are HHH - any earlier tail guarantees THH gets there first.

Show the answer Hide the answer

The second player wins every time by choosing well. Against HHH, THH wins 7 times in 8. The rule: take the opponent's first two symbols, and put in front of them the opposite of their second symbol.

How to get there

Take HHH against THH. For HHH to win, the first three tosses must be HHH - probability 1/8. If a tail appears anywhere before the run of three heads completes, then the next three heads are preceded by that tail, and THH has already occurred. So THH wins 7/8 of the time.

The general rule for the second player: if the first player picks ABC, choose (not B) A B. Against HTH choose HHT, which wins 2/3. Against HHT choose THH, which wins 3/4.

The relation "beats" runs in a cycle, like rock-paper-scissors - there is no best sequence, which is exactly why the second player always has a reply. The surprise is that every sequence is equally likely in isolation, and yet they are not equally likely to arrive FIRST: what matters is how a sequence can overlap with itself and with its rival.

The technique worth keeping

Equal probability in isolation does not mean equal probability of arriving first. Ask what must happen for one pattern to beat another, and look for overlaps - the pattern that can appear inside the tail of its rival has the advantage.