Penney's Game

Two players each choose a triplet of coin tosses. Player 1 names a triplet first and announces it; player 2 then names a different triplet. A fair coin is tossed until one of the two triplets appears, and its owner wins. If both play perfectly, would you rather be player 1 or player 2, and what is the winner's probability?

Reveal solutionHide solution

#Going second is the advantage

The game is non-transitive, with no single best triplet, and whatever triplet player 1 names, player 2 can always name one that beats it. So you want to be player 2.

#The beating rule

Given player 1's triplet $b_1 b_2 b_3$ , player 2 answers with $\overline{b_2}\,b_1\,b_2$ , the opposite of player 1's second symbol followed by player 1's first two. Player 2's last two symbols are exactly player 1's first two, so to finish their own pattern player 1 must first lay down the very prefix that lets player 2 complete one step earlier.

#The worst case is two in three

Conway's leading-number rule, or a short Markov chain on the overlap states, gives player 2 at least $\tfrac{2}{3}$ against every choice. Player 1's strongest defenses, like HTH or THH, hold player 2 down to exactly $\tfrac{2}{3}$ , while a careless HHH or TTT loses $\tfrac{7}{8}$ .

Player 2 answers any triplet with the opposite of its second symbol, then its first two. A weak choice like HHH loses seven eighths of the time, and even the strongest player 1 defence is beaten two times in three.

#Read it off

Be player 2. With best play you win with probability at least $\tfrac{2}{3}$ , and exactly $\tfrac{2}{3}$ against a perfect opponent. The intuition that picking first lets you grab the best pattern is exactly backwards, since every pattern has a predator.