Problem 95, "Penney-Ante"
Walter Penney published the game as problem 95 in volume 2 of the Journal of Recreational Mathematics, on page 241.
Each player picks a pattern of three coin flips, say heads, heads, heads. The coin is flipped until one of the patterns shows up in a row. You choose first, and your opponent sees your choice. If you pick HHH and they pick THH, what is their chance of winning? Lock in your answer, then test it against the computer and on a million simulated games.
Each player picks a pattern of three coin flips. The coin is flipped until one of the patterns shows up in a row. All patterns look equal, since each has a 1/8 chance. Yet THH beats HHH in 7 games out of 8, and whatever pattern you pick, your opponent has a reply that wins at least 2 times out of 3.
Walter Penney described this game in 1969 in the Journal of Recreational Mathematics. The rules fit in three lines, and you can play it with a friend in five minutes.
The coin is fair: heads (H) and tails (T) each come up with chance 1/2, and the flips are independent.
A pattern is three results in a row, in a fixed order. There are eight of them: HHH, HHT, HTH, HTT, THH, THT, TTH, TTT. Any given three flips form each of them with chance 1/8.
You pick a pattern first. Your opponent sees your choice and picks a different one.
The coin is flipped again and again. The player whose pattern first shows up as the last three flips wins. Say you picked HHH, your opponent picked THH, and the flips went like this:
After the fifth flip the last three read THH, and your opponent won.
You picked HHH, your opponent picked THH. What is the chance your opponent wins?
"Every pattern has a 1/8 chance, so it's 50/50"
In fact THH wins 7 games out of 8. An equal chance for a pattern in three fixed flips says nothing about which pattern appears first. What's more, this game has no best pattern: each one has a stronger rival.
You picked HHH, your opponent picked THH. Lock in the chance you think your opponent has of winning.
A breakdown of your answer will appear here.
Pick a pattern and the computer answers with its own. Make one flip at a time, play the game out, or play 100 games at once. Then swap roles: let the computer choose first and try to beat it.
Each row is the first player's pattern, each column the second player's. A cell shows the chance that the column's pattern comes first: the exact fraction and the simulated share. The darker the cell, the higher the chance. The outline marks the second player's best reply.
Cells where a pattern meets itself are empty. The first player's chance is 1 minus the number in the cell.
Now without an opponent: the coin is flipped until the pattern appears. Bars show the exact average, dots show the average of 20,000 simulated waits per pattern.
The patterns are equal if you look at three fixed flips. What matters in the game is different: how patterns overlap with each other and with themselves. Here are five ways to see it.
If any of the first three flips is T, then the first HHH must come right after a T. That T plus the two heads after it already form THH, one flip earlier. So once the first T has appeared, HHH has lost for good.
1,000 flips contain 998 windows of three, and each pattern appears 998/8 ≈ 124.75 times on average. But HHH comes in clumps: HHHH contains it twice, HHHHH three times. When appearances stick together, the gaps between clumps get longer, and the first appearance takes longer to come.
Say HH has just come up. For HHT a third H spoils nothing: you still have HH and wait for a T. For HHH a T at that point wipes out your progress, and you start from scratch. Patterns that overlap with themselves take longer to arrive.
Yet waiting time does not settle a duel. HHH and HHT play 50/50, despite average waits of 14 and 8: both start with HH, and after the first HH the next flip decides everything.
Each arrow points from the winner to the loser, and the number is the winner's chance. THH beats HHT, HHT beats HTT, HTT beats TTH, and TTH beats THH. The loop closes, as in rock, paper, scissors. Such a relation is called nontransitive: "A beats B" and "B beats C" do not imply "A beats C".
The reply ends with the two flips that start the opponent's pattern. So it almost always lies in wait for that pattern: before the opponent can finish, their first two flips have to come up, and they are often preceded by the symbol you need. The first symbol is the opposite of the middle one, so the reply does not overlap itself and does not wait longer than it must.
John Conway found this formula and called it the leading-number algorithm, but he did not publish a proof. Proofs came later, among them a martingale argument by Shuo-Yen Robert Li (1980) and the work of Guibas and Odlyzko (1981). The formula works for patterns of any length, as long as neither contains the other. The page uses it for every exact number in the round 3 table, and the simulation checks them.
What happens with patterns of two or four flips? How do you work out a duel between any two patterns? And does the trick survive when a deck of cards replaces the coin?
| First | Best reply | Exact | Simulated |
|---|
Type patterns with H and T, up to 12 symbols. Lengths may differ, but one pattern must not contain the other.
For every k at which the first k symbols of the pattern equal the last k, add 2k. The sum is the average number of flips until the first appearance. A length-n pattern with no self-overlap takes 2n flips on average, and n identical symbols in a row take the longest: 2n+1 − 2.
For fours, the first player's best defence is HTHH (or THTT): the opponent gets at most 9/14. J. A. Csirik proved in 1992 that for length k ≥ 4 the first player's best choice is H, then T repeated k−3 times, then HH, and then the second player's odds are (2k−1 + 1) : (2k−2 + 1).
In 2010 Steve Humble and Yutaka Nishiyama suggested playing with a 52-card deck: 26 red (♥) and 26 black (♠). Cards are turned over one at a time. As soon as someone's pattern appears, that player takes all the turned cards, and the search starts again. Whoever collects more of these tricks wins.
| First | Second | 1st wins | 2nd wins | Draw |
|---|
These numbers are exact: we computed them by going through every state of the deck. They agree with the simulation quoted on Wikipedia. The deck amplifies the second player's edge, because there are many tricks and the winner is whoever comes first more often.
Walter Penney published the game as problem 95 in volume 2 of the Journal of Recreational Mathematics, on page 241.
In the October 1974 issue of Scientific American, Martin Gardner devoted his "Mathematical Games" column to the paradoxes of nontransitive relations. That is where a wide audience learned about Penney's game and Conway's leading numbers.
John Conway came up with a way to get the odds for any pair of patterns from binary "leading numbers", but did not prove it. Rigorous proofs appeared in the early 1980s.
The statistician Bradley Efron devised four dice with these faces: 4, 4, 4, 4, 0, 0; six 3s; 6, 6, 2, 2, 2, 2; 5, 5, 5, 1, 1, 1. Each die loses to the one before it with chance 2/3, and the first loses to the last. Same principle: whoever chooses second can always take a stronger die.
HHH takes 14 flips on average, HHT only 8. Yet in a duel they are even, 50/50. Among fours it can even go the other way: HTTH, which takes 18 flips on average, beats TTHH (16 flips) with chance 7/12. Overlaps decide who comes first, not average waits.
In Humble and Nishiyama's card version, the second player with ♥♠♠ against ♠♠♠ wins 99.49% of games and loses just 0.11%. With a coin the chance was 7/8. The deck turns an edge into a near-certain win.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.