Detour: The Overlapping Words Paradox

We illustrate the overlapping words paradox with a two-player game called “Best Bet for Simpletons.” Player 1 selects a binary k-mer A, and Player 2, knowing what A is, selects a different binary k-mer B. The two players then flip a coin multiple times, with coin flips represented by strings of “1” (“heads”) and “0” (“tails”); the game ends when A or B appears as a block of k consecutive coin flips.

STOP and Think: Do the two players always have the same chance of winning?

Chances of winning

At first glance, you might guess that every k-mer has an equal chance of winning. Yet suppose that Player 1 chooses “00” and Player 2 chooses “10.” After two flips, either Player 1 wins (“00”), Player 2 wins (“10”), or the game continues (“01” or “11”). If the game continues, then Player 1 should surrender, since Player 2 will win as soon as “tails” (“0”) is next flipped. Player 2 is therefore three times more likely to win!