Three patterns in a circle

Penney’s game has a famous circle in it. On a fair coin THH beats HHT three times in four, HHT beats HTT two times in three, HTT beats TTH three times in four, and TTH beats THH two times in three. Four patterns, each beaten by the next, and no best one. It is the reason the second player always has a good reply: the first player’s choice is a position on a circle, and there is always somewhere further round.

A circle of four raises two questions that a circle of four cannot answer. The first is whether three patterns can do it — each beating the next, with the third beating the first. The second is what happens when three patterns race at once rather than in pairs: whether the three-way result is decided by the two-way ones, the way a ranking would be, or whether a third pattern changes the contest between the other two. Both have exact answers for short patterns, and both answers are the kind that could not be guessed.

The accounting with three teams #

Nothing new is needed to compute a three-way race. The gamblers’ argument that gave the waiting time for one pattern, and the odds between two, extends without change. Before every toss a gambler arrives for each of the three patterns and bets a unit, at fair odds, that the next toss is that pattern’s first letter; winners let the stake ride on the next letter, losers leave. Every bet is fair, so the house’s position is a martingale, and at the moment the race ends the expected amount paid in equals the expected amount held.

What is held depends on which pattern ended the race. If pattern $A_j$ finished it, the gamblers still in play on team $i$ are those whose calls so far match the start of $A_i$ and end at the last toss — exactly those sitting at an overlap of the end of $A_j$ with the start of $A_i$. Their holdings total $A_j \ast A_i$, the overlap sum from the earlier essays: two to the power $k$ for each such overlap of length $k$ on a fair coin. Team $i$’s expected holdings are therefore a weighted average over which pattern won,

$$\sum_j \pi_j \, (A_j \ast A_i) = E,$$

where $\pi_j$ is the chance that $A_j$ wins and $E$ is the expected length of the race, which is what each team paid in. There is one such equation for each team, and one more saying the $\pi_j$ add to one. Four equations, four unknowns.

The diagonal of the matrix is each pattern’s overlap with itself, the waiting-time numbers of the fair-coin essay: HHHT and TTHH overlap themselves only at full length and score sixteen, HTTH overlaps at one letter and at four, for eighteen. The off-diagonal entries are the cross-overlaps, and they are what makes the race a race rather than three separate waits. TTHH’s team, for instance, collects eight when HTTH ends the race, because the last three letters of HTTH, TTH, are the first three of TTHH: a gambler on TTHH who arrived three tosses before the end has called T, T, H correctly and holds $2^3$. When HHHT ends the race the same team holds two, from the single T. When TTHH itself ends it, the team holds sixteen, from the gambler who called all four letters, and nothing else — TTHH’s end, HH, never matches its own start, TT.

Every entry is found the same way, by sliding the end of one pattern along the start of another, and the whole three-way race is determined by these nine numbers. The system is small enough to solve by hand, and its answers are exact fractions.

The same numbers from a different machine #

The linear system above never mentions a coin toss after it is written down. So it is checked against a construction that does nothing but toss.

The race is also an absorbing Markov chain. Its states are the prefixes of the three patterns — the partial matches the tosses so far could be in the middle of — and each toss moves to the longest suffix of the new text that is a prefix of one of them, or ends the race if it completes a pattern. This is the pattern-matching automaton again, built for three patterns at once. The chance of ending at each pattern, and the expected number of tosses, come from solving the chain’s own linear system, which has one equation per prefix and knows nothing about overlaps or gamblers.

The two agree to every digit for every race drawn on this page, and the figures check it before drawing. That is the only reason to believe either: they share no step, so a mistake in one would have to be matched by a coincidental mistake in the other.

Three that go round #

Here is a circle of three. Each of HHHT, TTHH and HTTH beats one of the other two and loses to the other, so there is no pattern a first player can choose that the second cannot beat, even with only two others to choose from. A game with a circle like that has no pure choice worth defending, which is the situation in which a cautious player’s guarantee has to be computed rather than read off.

The two-way margins come out of the same nine numbers. Conway’s rule gives $B$ against $A$ the odds $(A \ast A - A \ast B) : (B \ast B - B \ast A)$, and each pair needs only its own corner of the matrix. HTTH against TTHH: TTHH’s self-overlap sixteen, less the two it scores into HTTH, against HTTH’s eighteen, less the eight it scores into TTHH — fourteen to ten, a chance of 7/12 for HTTH. TTHH against HHHT is fourteen to ten again, from sixteen less two and sixteen less six. HHHT against HTTH is sixteen to twelve, 4/7 for HHHT, because the end of HHHT runs two letters, HT, into the start of HTTH, and the end of HTTH runs one letter, H, into HHHT.

So the circle is not mysterious once the cross-overlaps are written out. Each pattern scores more into the start of the next one round than that pattern scores back, and nothing forces those advantages to line up into an order.

The three-way race does not fall into any of those orders. HHHT wins it with chance $23/64 \approx 0.359$, HTTH with $11/32 \approx 0.344$, TTHH with $19/64 \approx 0.297$. The winner of the three-way race is the pattern whose two-way win was the narrowest of the three. Neither reading of the circle — “the one that beats the strongest” or “the one with the biggest margin” — predicts it.

It is not that the three-way race is close to even and the ordering is noise. The chances are exact fractions, and the gap between first and last is four chances in sixty-four. The race has a definite winner. It simply is not a function of who beats whom.

How often circles happen, counted #

Is the circle a curiosity or a common thing? With patterns of three and four tosses the question has a finite answer, and the answer is below.

Three results come out of the count, and they are of different strengths.

No three three-toss patterns go round a circle. The four-cycle THH, HHT, HTT, TTH exists, but any three of its members include a pair that is tied at exactly a half or one that breaks the circle. THH against HTT, for example, is a dead heat: each wins with chance a half. So on three tosses a circle needs four patterns, and a triple is either ordered — one beats both, one loses to both — or contains a tie. The census confirms that every three-toss triple without an outright winner holds such a tie.

With four tosses, fourteen triples out of 560 go round. That is seven circles and their mirror images under swapping heads for tails. They are rare — one triple in forty, rarer than majority cycles among three voters, which are twelve profiles in 216 when counted the same exhaustive way. They are not all alike. Two of the fourteen have a tie for first place in the three-way race: HHTT, HTHH and THTH, for instance, finish with chances $3/8$, $1/4$ and $3/8$, a circle two-way and a dead heat for the lead three-way.

Where a pattern beats both others two-way, it wins the three-way race — in every one of the 20 three-toss and 268 four-toss triples where there is such a pattern. That is an observation over a finite list, not a theorem, and the census is the whole of the evidence for it. It is the only link between the two kinds of result that the count supports.

The link does not run the other way, and that is the most interesting line of the table.

A pattern that loses both races and is not last #

HHH loses to HTT, six to four, and loses to TTH, seven to three. Race all three and HHH comes second. TTH, which beat HHH comfortably head to head, comes last.

The reason is visible once it is looked for. TTH wins its two-way race against HHH whenever TT appears before HHH, because TT followed by any run of tails ends with an H eventually and completes TTH. In the three-way race, though, most of those TT’s are not TTH’s to keep. Any TT preceded by an H has already completed HTT. So TTH wins the three-way race only if TT comes at the very start of the sequence, before any H has been tossed — chance one in four, exactly. HHH’s chances, by contrast, are not touched at all. Head to head, HHH beats TTH exactly when HHH arrives before the first TT; in the three-way race HHH wins exactly when it arrives before the first TT too, since both HTT and TTH need one. It is the same event, and three in ten both times. The third pattern steals everything it can from one of the two and nothing from the other.

That is precisely the structure voting theory calls a spoiler. An option that loses to both rivals in head-to-head comparison should not, one would think, decide which of them wins; yet adding HTT to the contest between HHH and TTH reverses it. The majority rule that goes in a circle and the conditions no voting rule can meet together are about the same failure — a contest between two options that depends on which third option is present. Here there are no voters and no preferences, only a coin, and the dependence is produced entirely by the way the patterns share letters.

Across the full census the spoiler effect is not rare. Of 22 three-toss triples with a pattern losing both head-to-head races, six see that pattern avoid last place; of 284 such four-toss triples, sixty do. The two-way winner is safe; the two-way loser is not reliably last.

When the coin tilts #

A three-way race on a biased coin needs only the substitution the biased two-way game used: each overlap weighted by one over the chance of the letters it matches, in place of the power of two. The chain changes only in the probabilities on its arrows.

The circle on the fair coin is a balance point. Tilt the coin toward heads and HHHT, which needs three heads in a row, pulls away; tilt it toward tails and TTHH, whose two tails are its opening, takes over. HTTH, made of two of each, leads only in a band around the middle. Each of the three is the most likely winner on some coin, which is one way to say that none of them is better than the others in any sense that survives a change of coin.

The spoiler triple shows the same kind of exchange with sharper edges. TTH’s three-way chance is $q^2$ on every coin, for exactly the reason it was a quarter on the fair one: it wins only if the first two tosses are tails. HHH’s chance climbs fast with $p$. HTT sits in between and leads in the middle. The fair coin happens to sit in HTT’s band, which is why the spoiler story reads as it does there; move the coin and the story changes cast.

Why the pairwise results cannot decide it #

The spoiler example says what the two-way results leave out. A two-way race between $A$ and $B$ is settled by where the sequence’s letters happen to complete $A$ or $B$ first; everything else about the sequence is irrelevant to it. A three-way race makes a third set of completions relevant, and some of those completions interrupt one of the first two patterns’ chances and not the other’s. In the spoiler triple the interruption is total on one side and absent on the other. Every sequence in which TTH beats HHH head to head has a TT before any HHH, and HTT claims all of those except the ones that open with TT. And HHH’s three-way chance is not merely close to its head-to-head chance against TTH: it is equal to it, on every coin, because both events are “HHH before the first TT”.

The three pairwise chances are three numbers. The gamblers’ matrix is nine, and the three chances are ratios built from them, one pair’s corner at a time. A ratio forgets the sizes it was made from: fourteen to ten and seven to five are the same odds and come from quite different overlaps. The three-way system uses the sizes, all nine at once, so nothing obliges the three-way result to follow the order the ratios suggest. The census says how often that happens at these lengths — sixty-six times among the triples with a two-way loser — and the matrix says why it can.

The two-way winner survived in every triple counted. A pattern that beats both others two-way is first to finish against each of them; what the census shows is that no third pattern, at these lengths, interrupts it enough to reverse that. Whether that stays true for longer patterns is a question the census cannot reach, and nothing here settles it.

What the pictures cannot show #

The census is complete for three and four tosses and says nothing beyond. Five tosses have thirty-two patterns and 4,960 triples; the same count is mechanical there and is not drawn. Whether circles become more common, and whether a two-way winner can ever lose a three-way race at longer lengths, are left where the count stops.

The circle drawing uses the winner’s two-way chance and hides how the races were won. A 7/12 win for TTHH over HHHT and a 7/12 win for HTTH over TTHH look identical on the triangle, and the reasons for them — one about repeated heads, one about positional overlap — are different. The chain encodes those reasons; the triangle does not.

The expected length of the race is computed and not drawn. It is 263/32 tosses for the circle of four-toss patterns and 4.7 for the spoiler triple, and it plays no part in who wins. A race can be short and lopsided or long and even, and the chances alone do not distinguish those.

Still open: more patterns, and a tournament #

Three patterns can go round a circle once they have four tosses, and a third pattern can spoil a two-way result at any length counted here. Both are facts about the list of triples. What is missing is a structural account: some property of a triple of patterns, read off their overlaps, that says in advance whether they form a circle, or whether the two-way loser will come last. The three-by-three matrix of overlap sums contains the answer for any given triple, but nothing on this page reduces “is there a circle” to a condition on it.

The other direction is to let every pattern race at once — all sixteen of length four in one contest — and ask which comes first most often, and whether that pattern has anything to do with the ones that do best in pairs. The gamblers’ system for that race is sixteen equations in sixteen chances, and it is the same accounting as every figure here.

The ranking that is not there #

The instinct that a contest between three should be settled by the three contests between pairs is strong, and it is correct for anything with a single underlying strength — a runner with a time, a candidate with a score. Coin patterns do not have one. Each has a set of overlaps with itself and with each of the others, and which of those matter depends on which others are present.

A ranking needs a quantity to rank by, and there is no such quantity for patterns. The waiting time for each pattern alone, which looks like a candidate, is irrelevant to who wins: HHHT and TTHH both wait sixteen tosses on average and one of them beats the other seven times in twelve. The circle, the spoiler and the coin that reorders them are three views of the same fact — that “beats” between patterns is a relation, not a comparison of numbers, and a relation need not be transitive or stable under the addition of a third party.