The Coin Bet You Can Always Beat

This is a game for two players, and the first thing to be clear about is that nobody flips a coin of their own. Each player makes a bet on a pattern of three flips, such as HHT for heads, heads, tails. The first player chooses a pattern, and then the second player chooses a different one. After that, one fair coin is flipped over and over, and both players watch the same flips. The first time either pattern appears in the run, in exactly that order and on consecutive flips, that player wins.

The ribbon in the laboratory is the run of flips so far. A blue bar under a flip means it belongs to the end of the run that already matches the start of the first player’s pattern, and a red bar means the same for the second player’s pattern. A flip can carry both. When three flips in a row match one pattern, that game is over.

The surprise is about the second player. Whatever the first player bets, the second can reply with a pattern that wins at least 2 games in 3. The rule is to take the opposite of the first player’s middle call, and then the first player’s first two calls. Against HHT the middle call is H, its opposite is T, and the first two calls are H H, so the reply is T H H.

The tempting thought is that every pattern of three flips is as likely as every other. That is true of any three flips you choose to look at: HHT and THH each turn up there with chance one in eight. It does not follow that they are equally likely to turn up first, because a race is not a look at three chosen flips. It is a long run of flips in which the patterns can overlap and borrow from each other.

Watch what the ribbon does. After a flip of H, a player betting on HHT has made one step and a player betting on THH has made none. After a T, it is the other way round. A run of two heads that comes after a tail finishes THH on the spot, while the same two heads still need a tail after them to finish HHT. Nearly every pair of heads in a run has a tail in front of it, and that is the whole difference.

Now look at the table of replies. The average number of flips each pattern takes to turn up when it is alone is the same for HHT and THH, 8 flips. An average wait and a race are different questions. Two runners with the same average finish time can still have one of them win almost every time they race, if one tends to be steady and the other tends to be slow or fast by turns. Here the similar waiting times hide a lopsided race.

The reply THH is made from the first player’s HHT by sliding it along one place: the first two calls of HHT, H H, become the last two calls of the reply. That is the point. The first player needs those two flips in a row to get started, and the reply is only one flip, a tail in front of them, away from being complete.

Here is the argument for HHT and THH in one line. The first time two heads appear in a row, unless they are flips 1 and 2, the flip before them must be a tail, because otherwise two heads would have appeared one flip earlier. A tail followed by two heads is THH, so the reply has already won. The only way HHT can win is for the game to open with two heads, which has probability 1/4, and then HHT wins as soon as the first tail arrives. So the reply wins 3 games in 4.

The same idea explains the most lopsided case. A first bet of HHH can only win if the game opens HHH, so the reply THH wins 7 games in 8. Other first bets give the reply a smaller edge, down to 2 games in 3, and the table below lists them all. The rule picks the best possible reply in every case, and no first bet escapes.

Write a pattern as a word of three flips. For two patterns $X$ and $Y$, count how far the end of $X$ is also the start of $Y$:

where the sum runs over every length $k$ from 1 to 3 for which the last $k$ flips of $X$ are the same as the first $k$ flips of $Y$. This number, one of John Conway’s leading numbers as Martin Gardner described them, depends only on the two patterns. For a first bet $A$ and a second bet $B$ the chance that $B$ turns up before $A$ is

The average number of flips before a single pattern first turns up is $2\times AA$. For HHT this is $2\times 4=8$, for HTH it is $2\times 5=10$, and for HHH it is $2\times 7=14$.

A pattern $B$ beats $A$ when this chance is more than one half. The game is not transitive: if $B$ beats $A$ and $C$ beats $B$, it does not follow that $C$ beats $A$. Four patterns form a ring: THH beats HHT with chance 3/4, HHT beats HTT with 2/3, HTT beats TTH with 3/4, and TTH beats THH with 2/3.

The case of HHT against THH can be proved completely in a few lines. Suppose the game does not open with two heads. Then the first pair of consecutive heads, wherever it is, is preceded by a flip, and that flip is a tail, since a head there would have given an earlier pair. So the run already contains T followed by H H, which is THH, and the second player has won. Suppose instead the game opens with two heads. The run is then all heads until the first tail, and nothing can have completed THH before that tail arrives, so that tail completes HHT and the first player wins. The first player therefore wins exactly when the first two flips are heads, which has probability $\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$, and the second wins with probability $\frac{3}{4}$. The tests also check this over every one of the 16,384 runs of 14 flips.

For all eight bets, the page uses the overlap formula above, and the tests recompute every pair a second way. That second way follows the coin flip by flip, remembering only the last two flips, with exact fractions, up to 160 flips. After that many flips the part of the game still undecided is smaller than one in a trillion, and the exact chance always lies between the part decided for the reply and that part plus the undecided part. This is an exhaustive check of 56 ordered pairs of three-flip patterns, and it is not a claim about patterns of other lengths.

The best reply to each first bet, with its exact chance of winning, is:

• HHH is answered by THH, which wins 7 games in 8.
• HHT is answered by THH, which wins 3 games in 4.
• HTH is answered by HHT, which wins 2 games in 3.
• HTT is answered by HHT, which wins 2 games in 3.
• THH is answered by TTH, which wins 2 games in 3.
• THT is answered by TTH, which wins 2 games in 3.
• TTH is answered by HTT, which wins 3 games in 4.
• TTT is answered by HTT, which wins 7 games in 8.

If the first player picked one of the eight patterns at random and the second always used the rule, the second would win 71 games in 96 on average, a little under 3 in 4. The weakest case for the reply is still 2 in 3.

Everything on this page concerns patterns of exactly three flips on a fair coin. The method of overlaps is described for patterns of any length in Gardner’s column and in the paper by Guibas and Odlyzko, but this page does not use or check any longer pattern, so it claims nothing about them.

The odds are a statement about many games. In a single game a first bet of HHT wins a quarter of the time against THH, and a seeded tally of a thousand games is a record of one seed. It wanders about the exact chance and does not establish it. The exact value comes from the overlaps, and the tally only illustrates it.

The game can also be played with cards: deal a shuffled deck one card at a time, with red for heads and black for tails, and watch for each pattern. A reply chosen by the same rule should still do well, but the odds are not exactly the coin’s. Cards are dealt without replacement, so each card dealt changes the chance of the next, and a game can run out of cards before either pattern has turned up. This page computes no card odds and quotes none.

Read this next to Three Dice, Each Beaten by the Next. The two pages are the same idea in different materials. There, three dice each beat the next, so no die is best. Here, four patterns each beat the next, so no pattern is best. In both, beating is a statement about a pair, not a number carried by one thing, and so a ranking by beating does not have to exist.