A coin that lets the first player win

Two people play Penney’s game. The first names a pattern of three coin tosses, the second hears it and names a different one, and a coin is tossed until one of the two patterns turns up. On a fair coin the second player always has the better of it. Against HHH they name THH and win seven times in eight; against HTH they name HHT and win two times in three; and whatever the first player does, the second can hold them to a third or less. The waiting-time argument explains why: a pattern that overlaps itself arrives in clumps, and a well-chosen reply sits in front of the clump and collects it.

Every piece of that argument used the coin’s fairness somewhere, usually in the form of a power of two. A coin that lands heads six times in ten changes each of those powers into something that depends on which letters are involved. The question is what survives. The answer is: the method survives completely and the conclusions almost all move — the replies, the margins, which matchup is lopsided and which is close, and at the far end even the second player’s advantage itself.

Paying for an overlap in the letters it uses #

Start with the single-pattern wait, because every later number is built from it — the same way the collector’s wait was built from stages before any unequal chances entered. On a fair coin, Conway’s rule says the expected wait for a pattern is the sum of $2^k$ over every length $k$ at which the pattern’s first $k$ letters equal its last $k$. The $2^k$ was never really about the number two. It is one over the chance of the $k$ letters in question, and on a fair coin every string of length $k$ has chance $2^{-k}$.

On a coin with heads chance $p$ and tails chance $q = 1 - p$, the same rule holds with the correct chance in place of $2^{-k}$. For each overlap length $k$, add one over the probability of the pattern’s first $k$ letters. So HHH, which overlaps itself at lengths one, two and three, waits

$$\frac{1}{p} + \frac{1}{p^2} + \frac{1}{p^3}$$

tosses on average, and HTT, which overlaps itself only trivially, waits $1/(pq^2)$.

The gamblers’ proof carries over unchanged, which is the reason to trust it. A gambler arrives before each toss and bets a unit that the next toss is the pattern’s first letter, at fair odds — so a winning bet on heads returns $1/p$ and a winning bet on tails returns $1/q$ — and lets the winnings ride on the next letter. Each bet is fair, so the whole casino’s takings form a martingale: at the moment the pattern first appears, the expected total paid in equals the expected total held. What is paid in is one unit per toss. What is held is the winnings of the gamblers still in play, and those are exactly the gamblers sitting at an overlap position, each holding one over the chance of the letters they have correctly called. Nothing in that sentence mentions two.

The picture of the eight waits against the bias is where the reshuffling starts. On a fair coin the order is fixed by overlap alone: HHT, HTT, THH and TTH wait eight tosses, HTH and THT ten, HHH and TTT fourteen. Tilt the coin and letter frequency overwhelms overlap almost at once. At $p = 0.9$ the slowest pattern of the fair coin is the fastest by a factor of three, and its mirror image takes over a thousand tosses. The interesting region is the middle, where the two effects are comparable — between about $0.3$ and $0.7$ the curves cross one another repeatedly — and that is exactly where a game between two patterns will turn out to be delicate.

One coincidence in the picture is exact rather than approximate. HHT and THH overlap themselves nowhere and use the same three letters, so their waits are the same product $1/(p^2 q)$ at every bias, and their curves lie on top of each other. HTT and TTH do the same. The fair-coin lesson — that equal probability does not mean equal wait — has a converse here: equal letters and equal overlaps do mean equal wait, however unfair the coin.

Conway’s odds, reweighted #

Two patterns racing is a different question from one pattern arriving, and Conway’s answer to it is the part of the fair-coin story that looks most like a trick. Write $A \ast B$ for the sum, over every $k$ at which the last $k$ letters of $A$ equal the first $k$ letters of $B$, of $2^k$. Then $B$ beats $A$ with odds

$$(A \ast A - A \ast B) \; : \; (B \ast B - B \ast A).$$

On a biased coin the only change is in what is summed: one over the chance of the $k$ matching letters, which are the first $k$ letters of $B$. The argument is the gamblers’ again, now with two teams — one betting on $A$ and one on $B$ — and a pair of fairness equations that pin down both the chance of each winner and the expected length of the race. That system is due to Guibas and Odlyzko, and a closely related martingale treatment to Li; both appeared around 1980 and neither needed the coin to be fair.

The table works one matchup through by hand. On a coin showing heads six times in ten, HHT against THH has four overlap sums: HHT with itself only at full length, $1/(p^2q)$; THH with itself likewise; the end of HHT against the start of THH at one letter, the T, worth $1/q$; and the end of THH against the start of HHT at one and two letters, H and HH, worth $1/p + 1/p^2$. The odds come out at about $4.44 : 2.50$, a chance of $0.640$ for THH.

The second column of the answer does not trust the formula. It builds an absorbing Markov chain whose states are the prefixes of the two patterns — the same partial-match automaton used for waiting times, now with two absorbing ends — and solves the linear system for the chance of absorption at each. The chain knows nothing about overlaps, only about which prefix a new letter leads to, and the two answers agree to every printed digit. They agree, too, for all fifty-six ordered pairs of three-toss patterns at that bias; the figure checks each one before drawing.

It is worth saying why the check is not idle. The overlap formula looks as though it could fail on a biased coin in a subtle way: the gamblers who bet on the first letters of $B$ are paid at rates that depend on $B$’s letters, and it is not obvious that a pattern’s team and its rival’s team are accounting in the same currency. They are, because every bet is fair on its own terms and fairness adds. But the reason to believe a formula is that it has been checked against something built on different principles, and the chain is that something.

Matchups that change sides #

With a way to compute any matchup at any bias, the obvious thing is to follow a few classical matchups as the coin tilts.

The simplest one has a closed form that could be written down with no computation at all. THH against HHH: once a tail has appeared, THH must come first, because any run of heads long enough to make HHH is preceded by that tail and so makes THH one toss sooner. So HHH wins only if the first three tosses are all heads, and THH’s chance is exactly $1 - p^3$. On a fair coin that is seven in eight. On a coin with $p = 0.8$ it is $0.488$, and THH has become the underdog of a matchup it used to dominate.

That crossing happens at $p^3 = 1/2$, which is $p = 2^{-1/3} \approx 0.794$. The same argument, one letter shorter, settles THH against HHT. HHT needs HH followed by a tail; if any tail comes before the first HH, then that HH completes THH on the spot, a toss before HHT could finish. So HHT wins only when the first two tosses are heads, THH’s chance is $1 - p^2$, and the crossing is at $p = 2^{-1/2} \approx 0.707$. Three to one on a fair coin becomes even at a heads chance of seventy-one in a hundred.

The two arguments share a shape worth naming. In each, the reply is the first player’s pattern with its last letter removed and a tail put in front. Once a single tail has appeared, the reply is certain to win, because every later run of heads long enough to finish the first player’s pattern finishes the reply first. The first player’s only hope is that the coin never produces that tail in time — that the pattern appears at the very start. On a fair coin that hope is small, and on a coin that seldom lands tails it is most of the probability.

HHH against HHT is settled by a single toss. Both need HH first; the toss after the first HH decides, heads for HHH and tails for HHT. So HHH’s chance is exactly $p$, a straight line through the middle of the picture, and neither pattern has any positional advantage over the other — the letters are the whole contest. It is the same situation as a race between HT and TH, where the first toss decides.

The last matchup drawn is the one that does not cross. HHT against HTH is two to one on a fair coin and works out, from the gamblers’ equations, to $1/(1 + q)$ in general: above a half on every coin, approaching a half only as heads become impossible. HTH is a pattern that cannot exploit a bias, because it needs both letters, and HHT beats it by the positional trick alone. The trick never stops working here because there is no letter frequency that favours HTH over HHT.

The reply, bias by bias #

A first player who knows the bias will want to know what the second player is going to say. So the table below computes, for each of the eight possible first choices and nine biases, the best reply and the chance it wins.

The middle column is the classical recipe: to answer $abc$, flip the middle letter and put it in front, giving $\bar b a b$. Every cell of the fair-coin column is that pattern. Away from the middle the recipe survives for some rows and breaks for others, and the break has the same shape each time. Against HHT, the classical THH is best up to about $p = 0.62$; above that the best reply is HHH, which beats HHT simply by being the letter the coin prefers, one toss after the shared HH. Against HTT, the classical HHT gives way below about $p = 0.41$ to THT, which exploits the tails the coin now favours. Six of the eight rows change their reply somewhere in the chart.

Only HHH and TTT keep the classical answer at every bias, and for HHH there is a two-line proof. Any reply other than HHH can appear within the first three tosses only if it is those three tosses, so if the first three are heads, HHH wins against every reply: no reply can hold HHH below $p^3$. THH holds it to exactly $p^3$, as the matchup argument showed. So THH is the best reply to HHH on every coin, and by symmetry HTT is the best reply to TTT. The other six rows have no argument of that kind, and their replies move.

The chances in the cells are the second player’s, and they are more varied than the fair-coin figures suggest. On a fair coin the second player’s worst position — the first player’s best choice — is two in three. With the coin at $0.6$ the second player can still do no worse than $0.54$, but the first choice that holds them there has changed: it is now THH, answered by HTH.

When moving first becomes an advantage #

The hero curve at the top of the page is the first player’s value: the chance of winning if they choose as well as possible, knowing the second player will reply as well as possible. It is a minimax value in the plainest sense — the first player picks a row of the reply table, and the second player picks the best column entry against it — and it is not a mixed-strategy value, because the players move in sequence and the second sees the first’s choice before answering.

On a fair coin the value is exactly a third, and it is the minimum of the whole curve. That is the first surprise: the fair coin is the worst coin to move first on. It is the reverse of a leader who announces a mixture, for whom going first is never a cost; here going first is always a cost, and the size of the cost is what the bias controls. Any bias at all gives the first player something, because a bias breaks the symmetry between patterns and the first player can choose one on the right side of the break.

The curve’s shape between the fair coin and the extremes is jagged, and the jags are changes of first choice. Just off the fair coin the first player’s best choice is THH or its mirror HTT, and the value climbs to about $0.461$ at a heads chance of $0.41$ or $0.59$. Then it falls again — to about $0.376$ near $0.28$ and $0.72$ — because the second player’s best reply against those patterns has improved faster than the first player’s pattern has. Past that dip the first player switches to the pattern the coin favours outright, HHH or TTT, and against the best reply to HHH, which is THH, the first player wins precisely when the first three tosses are heads.

So in that region the value is $p^3$, exactly, and it passes a half at $p = 2^{-1/3}$. From there on the second player’s advantage, the thing Penney’s game is famous for, is gone: whatever they reply, the first player’s HHH is more likely than not to arrive first. The same happens on the tails side, below $1 - 2^{-1/3} \approx 0.206$, with TTT.

The number is worth a sentence of its own because it is so clean. A coin that shows heads four times in five is not an exotic object; nothing about it would look wrong in fifty tosses to someone expecting heads, and yet it is on the far side of a threshold that reverses who the game favours. The mechanism is not subtle either. It is the observation made earlier about THH and HHH, now used by the first player: the only way to beat HHH is to exploit a tail, and on such a coin there often isn’t one early enough.

Where the fair coin was hiding something #

The fair-coin story had a satisfying explanation of the second player’s edge — clumping, overlaps, the reply sitting in front of the clump — and it would be easy to believe that explanation was the whole truth. The biased coin shows what else was in play.

Overlap is one of two forces, and the coin’s fairness held the other at zero. On a fair coin, every pattern of a given length has the same chance, so the only thing that could distinguish patterns was their overlap structure. Once letters have different chances, patterns differ in their letters too, and the two forces pull in different directions — much as unequal chances rearranged the collector’s problem, where the average chance stopped being the quantity that mattered. The waiting-time chart shows them crossing; the matchup curves show the second-mover trick losing to letter frequency; the reply table shows the recipe breaking exactly where the letter effect dominates.

The gamblers’ method was more general than the fair-coin answer made it look. Every figure on this page is Conway’s accounting with $2^k$ replaced by one over a probability. That substitution is so small that it is tempting to call the biased case a trivial extension. It is trivial as mathematics and not at all trivial as a map: the replies, the margins and the value move non-monotonically and in ways that could not be guessed without computing them. A formula that extends effortlessly is still a formula whose consequences have to be worked out.

There is a family resemblance to a trick that turns a biased coin into a fair one. Von Neumann’s procedure reads tosses in pairs and keeps HT and TH, because those two have the same chance $pq$ whatever the bias. The same pair raced against each other in Penney’s game is the smallest example of the bias mattering: whichever letter comes first, the race is decided on the next change of letter, so HT wins exactly when the first toss is heads — chance $p$. The pair that is perfectly fair when read as a block is perfectly unfair when raced, and the difference is entirely whether the windows are allowed to overlap.

The accounting in that table is almost empty, and that is the point of drawing it. HT overlaps itself nowhere, nor does TH; the two cross-overlaps are one letter each, H from the end of TH into the start of HT and T the other way. Every term the formula needs is there, and the answer it produces — the chance of heads — is the one a moment’s thought gives. When a formula and a moment’s thought agree on the smallest case, the formula has earned some trust for the cases where a moment’s thought gives nothing.

What the pictures cannot show #

The curves are drawn on a grid of biases, and every threshold quoted from them is read off that grid. The one exact threshold is $2^{-1/3}$, which follows from the closed form for HHH against THH; so are $2^{-1/2}$ for THH against HHT and the straight line for HHH against HHT. The others — the reply changes near $0.38$, $0.41$, $0.48$, $0.52$, $0.59$ and $0.62$, the value’s peaks and dips — are located to about two decimal places and are stated that way.

Every number is for patterns of three tosses. With four tosses there are sixteen patterns and two hundred and forty ordered matchups, and nothing here says how the reply table or the value curve looks at that length. The HHH argument generalises — the all-heads pattern of any length is held to exactly $p^L$ by the reply that puts a tail in front — but where the rest of the curve sits at length four, and whether the first player’s worst coin is still the fair one, are not drawn.

The coin is assumed to be exactly what it claims. A real coin’s bias is estimated, and a test for whether a sequence is random, of the kind that ranks generators by how quickly they fail, compares statistics of this kind — counts, gaps, waits — against a stated model; the figures here take the model as given and never test it.

And the game is a single play. A first player who knows the bias approximately, or who plays repeatedly against an opponent who might be exploiting a slightly different bias, faces a different problem — one about estimation and robustness — and the value curve says nothing about it. Near the jags a small error in the bias changes the best choice, and a first player near $p = 0.72$ should not trust the curve to two decimal places.

Still open: a third player, and circles of patterns #

The two-player game on any coin is completely solved by this page’s method: one linear system per matchup, exactly checkable, and an eight-by-eight table for each bias. The picture changes when a third pattern enters.

With three patterns racing, the gamblers’ method extends — one team per pattern, one fairness equation per team — and it gives each pattern’s chance of arriving first. What it does not give is any simple relation between that three-way chance and the three two-way matchups. On a fair coin the three-toss patterns are well-behaved in that respect; a family of four-toss patterns is not. Whether three patterns can beat one another in a circle, each winning its own two-way race against the next, and what the three-way race makes of such a circle, is the natural continuation — with the gamblers doing the same accounting in a larger ledger.

The coin that was fair by accident #

The fair coin was chosen for Penney’s game because it is the natural default, and it happened to sit at the one point where the second player’s edge is largest and the reasons for it are purest. Almost every generalisation of the game — to biased coins, to more patterns, to longer patterns — dilutes one or other of those properties, and the result is a game in which the table has to be computed rather than remembered.

The explanation that survives is the method, not the recipe. “Flip the middle letter and put it in front” is a fact about a fair coin. “Weight each overlap by one over the chance of the letters it uses, and let fair bets do the accounting” is a fact about coin tossing, and every number on this page, and in the fair-coin essay, is a consequence of it.