Four dice that beat each other in a circle
Worth reading first: A coin that lets the first player win · The best average is the worst bet.
Two players each choose a die and roll; the higher number wins. With ordinary dice the game is fair, but nothing requires the dice to be ordinary, and a player allowed to choose from a set of specially numbered dice might expect to pick the best one. Bradley Efron, the statistician, designed four dice in the 1960s that make that impossible. Die has faces 4, 4, 4, 4, 0, 0; die has six 3s; die has 6, 6, 2, 2, 2, 2; and die has 5, 5, 5, 1, 1, 1. Then beats , beats , beats , and beats , each with probability exactly . Whatever die the first player picks, the second can pick one that wins two games in three.
The relation “is more likely to roll higher” goes round in a circle. A coin that lets the first player win found the same kind of circle in Penney’s game, where every three-toss pattern of heads and tails is beaten by another, and the majority that goes in a circle found it in voting, where every candidate can lose to another by majority. The dice make the circle physical: four objects on a table, any one of which can be beaten, and none of which is best.
The circle, and the averages that do not see it
Each probability is a count over the 36 equally likely pairs of faces. against : wins whenever it shows a 4, which is two thirds of the time, since always shows 3. against : ’s 3 beats ’s 2s, four faces of six. against : wins with a 6 (one third of the time, beating anything) or with a 2 against ’s 1 (two thirds times one half), total . against : wins with a 5 (half the time) or with a 1 against ’s 0 (half times one third), total .
The averages tell a different story. averages 2.67, and average 3, and averages 3.33. Expectation is a number, and numbers are ordered: has the highest average, and the lowest. Yet beats , and loses to . The die with the higher average is not the die more likely to win, and no ordering of the four by any single number can predict the outcomes of the games, because those outcomes are not an ordering.
The point deserves care, because it is not that expectation is wrong. The expected value of a die is the right quantity for a gambler who is paid the number rolled, and in that game is the best die. The game here pays one unit to whoever rolls higher, and the expected payoff of that game is the probability of winning, which depends on how the two dice’s faces interleave rather than on their totals. The best average is the worst bet found a similar gap between the quantity that is easy to compute and the quantity that decides the outcome; here the gap is that a comparison of two random quantities is not a comparison of two numbers.
Thirty-six pairs of faces
The grids show where the probabilities come from. against is a block: every 4 beats every 3, every 0 loses, and the 24 winning pairs form a rectangle. against — two steps round the circle — is closer: ’s 6s beat everything, its 2s beat only ’s 0s, and wins 20 of 36, more than half but less than two thirds. The dice opposite each other in the circle are much closer to even than the dice beside each other. against , the other opposite pair, is exactly even: ’s 3 beats ’s 1s and loses to its 5s, 18 pairs each.
The construction of such dice is a matter of interleaving. Each die’s faces are concentrated at two levels, and the levels are arranged so that each die’s high faces sit just above the next die’s main level and its low faces just below. Efron’s dice have the same structure as the winning patterns in Penney’s game: in both, the winner is built from the loser by shifting where its weight sits, and in both the shift can be repeated round a cycle.
Roll two of each
Change the game so that each player rolls two copies of the chosen die and compares totals. With ordinary reasoning, a die that beats another two times in three should do so even more reliably with two rolls, as averages of more rolls separate more cleanly. Half of Efron’s circle obeys that intuition and half reverses it. Counting all pairs of pairs: still beats , now with probability , and still beats with . But now loses to , winning only , and loses to the same way.
The reversal is the averages reasserting themselves. Rolling more dice makes each player’s total more concentrated around twice the die’s average, and when two dice have quite different averages, enough rolls will make the higher average win almost always. averages 2.67 and averages 3; with one roll each, ’s chance of a 4 wins two times in three, but with two rolls totals 8 only when both dice show 4, which happens of the time, and otherwise totals at most 4 against ’s 6. With many rolls each, the circle collapses into the ordering by averages: beats everything, loses to everything, and and , with equal averages, come out even.
Other sets have been designed — by James Grime among others — in which rolling two dice turns a whole circle round, so that every die that won now loses. Efron’s four do something in between, and the figure shows that nontransitivity is not a stable property of a set of dice but of a particular game played with them.
The strongest circle of three
How strongly can dice beat each other in a circle? With three dice, an exhaustive search answers the question for small dice. Take three dice with faces each and number them with the whole numbers 1 to , each used once, so that there are no ties. Every way of dividing the numbers among the dice is searched — 5,717,712 divisions for six faces — and for each the weakest of the three winning probabilities in the circle is computed. The figure shows the best division at each size.
With two faces the best is exactly , which is no circle at all. With three faces the best is , achieved by 1, 5, 9 against 3, 4, 8 against 2, 6, 7, a classic set. With four faces it is , with five , and with six — slightly less than with five, because a different number of faces changes which interleavings are available. The five-face winner is 1, 2, 11, 12, 13 against 6, 7, 8, 9, 10 against 3, 4, 5, 14, 15, and it has the structure of Efron’s dice: one die concentrated in the middle, the others split between a high and a low level.
All of these fall below a line at , the reciprocal of the golden ratio. That line is a theorem: for any three random quantities whatever, the smallest of the three probabilities , , is at most , a result of the Polish mathematician Stanisław Trybuła from the early 1960s. With dice of more faces the bound can be approached arbitrarily closely but never passed. The best searched here, , comes within 0.018 of it.
The golden ratio arrives through a quadratic. The bound is the positive root of , the defining equation of the golden ratio’s reciprocal, and in the optimal arrangements the probability with which each quantity beats the next and the probability with which it loses to the one after are tied together by exactly that equation. The golden ratio stops the fifth soldier found the same equation weighting a peg-jumping puzzle; here it is the price of a circle of three.
The magic square hiding in the best three
The best three-face dice in the search are 1, 5, 9 against 3, 4, 8 against 2, 6, 7. Rearranged, they are the three rows of the oldest magic square there is, the Lo Shu:
The rows are , and , and as dice each beats the next with probability , the strongest possible with three faces. Every row adds up to 15, so the three dice have the same average, 5: they are a nontransitive circle with no difference in expectation at all. The columns, , and , are a second set of three dice, also with average 5, and they too form a circle at — running the other way, each column losing to the next.
That is not a coincidence of the numbers but a consequence of the square’s structure. In a magic square every line has the same total, so the dice made from its lines have equal means, and a circle among them has to come from the way their faces interleave, which the square arranges as evenly as possible. The three-by-three magic squares using the numbers 1 to 9 are all rotations and reflections of the Lo Shu, so every one of them gives the same two circles of dice, and the magic squares are a space showed how the whole family of magic squares, with any entries, forms a vector space in which the Lo Shu is one point. The Lo Shu dice also show the averages failing in the purest form: Efron’s beat a die with a higher average, but here no die has any edge in average over any other, and still each beats the next five times in nine.
The same evenness is what makes the circle a cousin of the voting cycle. Read each die as a candidate and each column position as a voter giving the candidates scores; then the rows of the Lo Shu say that each voter’s three scores are a different arrangement of low, middle and high, and that is precisely the profile which how often the majority goes in a circle counted as the cycle — three voters, three candidates, each candidate first for one voter, second for another and last for the third. Nontransitive dice and the Condorcet paradox are two faces of one combinatorial object: a Latin square of preferences.
The ceiling for any number of dice
The general answer was found by Zalman Usiskin in 1964: for a circle of random quantities, each beating the next, the largest possible common winning probability is
For this is , the golden-ratio bound again. For it is — exactly what Efron’s dice achieve. His four dice are not merely a clever example; they are optimal, as strongly nontransitive as four random quantities of any kind can be. For larger the ceiling rises, 0.692 for five, 0.707 for six, and it approaches as grows, never reaching it.
So no circle of dice, however long, can have each die beat the next three times in four. As grows, approaches 1 and the bound approaches ; the long circle can make each step very nearly a three-to-one favourite, but closing the circle always costs something. The cosine itself is the one that appears in the eigenvalues of a path of points, a sign that the optimal distributions are arranged along a chain, each sitting just above the next.
The advantage of choosing second
The practical consequence of a circle is that the player who chooses second always wins more often. Against Efron’s dice, whatever the first player picks, the second picks the die just before it in the circle and wins with probability . The first player cannot do better by choosing cleverly, since every die has a predecessor; the advantage belongs to the order of choosing, not to any die. In two patterns, one chance, different waits and the Penney’s-game essays, the second player’s edge came from overlaps between coin patterns; here it comes from the circle directly, and it is as large as four dice allow.
If both players must choose at the same moment, the game becomes symmetric, with ties counted as half a win each: whatever one player can guarantee, so can the other, so neither can guarantee more than half, and the theory of zero-sum games says each has a way of mixing over the dice — choosing each with some fixed probability — that guarantees exactly half. Picking uniformly at random is not such a mixture here, since against it wins less than half the time. Only knowledge of the other’s choice breaks the symmetry. That is why nontransitive dice are a favourite of people who like to win bets: the trick is not the dice, which are fair as a set, but letting the opponent choose first.
What the counts cannot show
The probabilities in the figures are exact, but the game they describe is a single comparison of two rolls. Real dice games involve repeated play, betting and choice of game, and as the two-dice figure shows, the circle depends on the game. A player who knows that the opponent will choose second can only be protected by choosing a game in which the second choice has no advantage, and the figures say nothing about which games those are.
The search figure also shows only dice numbered with distinct whole numbers to . Allowing repeated numbers, ties, or faces of different sizes changes the best values for small dice, though not the ceiling, which holds for every kind of random quantity. And the ceiling theorems are proved for continuous distributions, where the bound can be approached; for dice with a fixed number of faces, the best achievable value is a separate, finite question that the search answers only up to six faces.
What the figures cannot show at all is why nontransitivity feels so wrong. Transitivity is a property of numbers, and probabilities of winning are numbers, so the mind wants the dice to be ordered by them. But “the probability that beats ” is a number attached to a pair of dice, not to one die, and nothing forces numbers attached to pairs to be consistent with any ranking of the individuals. Three patterns in a circle raced three coin patterns at once and found that even a three-way race of nontransitive patterns produces a definite winner — a fact about the triple that none of the pairs predicts.
Still open: the best dice of each size
For dice with faces and dice in the circle, what is the strongest circle possible, exactly? The ceiling formula bounds it, and the search here finds the exact answer for three dice with up to six faces, but no formula is known for the exact finite values, and for larger exhaustive search becomes impossible quickly: seven faces would need 133 million divisions, and each further face multiplies the count by about twenty-three. Constructions approaching the golden-ratio bound are known for three dice, and approaching is trivial for four, but how fast the best finite dice approach the ceilings as the number of faces grows has not been settled. How long until every one turns up began this collection’s look at expectation with a die whose average was all that mattered; Efron’s dice end it, for now, with dice whose averages say almost nothing about how they behave.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- A random tree is one part in e leaves — both name exhaustive search, expectation
- Agendas that cannot contradict themselves — both name condorcet cycle, exhaustive search
- An average that never settles — both name expectation, independence
- Every function is a tree with two marks — both name exhaustive search, expectation
- Fair bits from an unfair coin — both name expectation, independence
- How high an orbit climbs — both name exhaustive search, expectation
Named objects
A dashed tag is an object no other essay names yet.
Condorcet cycleExhaustive searchExpectationGolden ratioIndependence