Do not get involved in a bar bet with Brad Efron and his dice until you have read this.

Contents

Brad Efron

Bradley Efron is the Max H. Stein Professor of Humanities and Sciences, Professor of Statistics, and Professor of Biostatistics at Stanford. He is best known for his invention of the bootstrap resampling technique, which is a fundamental tool in computational statistics. In 2005, he received the National Medal of Science. But I think of him for something much less esoteric -- his nontransitive dice. And I also remember him as one of my roommates when we were both students at Caltech.

Brad's wager

If you come across Brad in a bar some night, he might offer you the following wager. He would show you four individual dice, like these.

Photo credit:http://www.grand-illusions.com

You would get to pick one of the dice. He would then pick one for himself. You would then roll the dice a number of times, with the player rolling the highest number each time winning a dollar. (Rolling the same number is apush. No money changes hands.) Do you want to play? I'll reveal the zinger -- no matter which of the four dice you choose, Brad can pick one that will win money from you in the long run.

Transitivity

A binary mathematical relationship, $\rho$, is said to be传递if $x \ \rho \ y$ and $y \ \rho \ z$ implies $x \ \rho \ z$.Equalityis the obvious example. If $x = y$ and $y = z$ then $x = z$. Other examples includegreater than,divides, andsubset.

On the other hand, a relationship isnontransitiveif the implication does not necessarily hold. Despite their efforts to make it transitive,Facebook friendis still nontransitive.

Ordinarily, the termdominates, orbeatsis transitive. And, ordinarily, you might think this applies to dice games. But, no, such thinking could cost you money. Brad's dice arenontransitive.

Brad's dice

Here are the six values on the faces of Brad's four dice.

A = [4 4 4 4 0 0]; B = [3 3 3 3 3 3]; C = [6 6 2 2 2 2]; D = [5 5 5 1 1 1];

How do these compare when paired up against each other? It is obvious thatA赢了钱fromBbecauseBrolls a 3 all of the time, whileArolls a winning 4 two-thirds of the time. The odds are 2:1 inA's favor. SimilarlyB's constant 3's dominateC's 2's two-thirds of the time. The odds are 2:1 inB's favor.

ComparingCwithDis more complicated because neither rolls a constant value.. We have to compare each possible roll of one die with all the possible rolls of the other. That's 36 comparisons. The comparison is facilitated by constructing the following matrix. The comparison of a row vector with a column vector is allowed under MATLAB's new rules ofsingleton expansion.

Z = (C > D') - (C < D')

Z = 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

The result is a matrixZwith +1 whereCbeatsDand a -1 whereDbeatsC. There is a submatrix of -1s in the upper right, but no solid column or row. All that remains is to count the number of +1's and -1's to get the odds.

odds = [nnz(Z == +1) nnz(Z == -1)]

odds = 24 12

There are twice as many +1s as -1s, so, again, the odds are 2:1 thatCbeatsD.

But now how doesDfair againstA?

Z = (D > A') - (D < A') odds = [nnz(Z == +1) nnz(Z == -1)]

Z = 1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 odds = 24 12

Again, there are twice as many +1s as -1s. The odds are 2:1 inD's favor.

To summarize,AbeatsB,BbeatsC,CbeatsD, andDbeatsA. No matter which die you choose, Brad can pick one that will beat it -- and by a substantial margin. It's like "Rock, Paper, Scissors" with a fourth option, but you have to make the first move.

Compare

Let's capture that comparison in a function. The function can print and label the matrixZ, as well as provide for pushes, which we'll need later.

typecompare

function odds = compare(X,Y) Z = (X > Y') - (X < Y'); odds = [nnz(Z==1) nnz(Z==0) nnz(Z==-1)]; fprintf('\n X %3d %5d %5d %5d %5d %5d\n',X) fprintf(' Y\n') fprintf(' %5d %5d %5d %5d %5d %5d %5d\n',[Y' Z]') end

Use the function to compareAwithC.

AvC = compare(A,C)

X 4 4 4 4 0 0 Y 6 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 2 1 1 1 1 -1 -1 2 1 1 1 1 -1 -1 2 1 1 1 1 -1 -1 2 1 1 1 1 -1 -1 AvC = 16 0 20

Dividing out a common factor, that is odds of 4:5 againstA.

The final possible comparison isBversusD.B's unimaginative play results in complete rows of +1 or -1.

BvD = compare(B,D)

X 3 3 3 3 3 3 Y 5 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 BvD = 18 0 18

SoBandDare an even match. Here is the complete summary of all possible pairings among Efron's Dice,

A B C D A 2:1 4:5 1:2 B 1:2 2:1 1:1 C 5:4 1:2 2:1 D 2:1 1:1 1:2

Simulate

In case we don't believe these comparisons, or because we'd like to see the shape of the distribution, or just because it's fun, let's do some Monte Carlo simulations. Because 108 is divisible by 36, I'll make 108 rolls one game and simulate 10000 games. Here is the code.

type模拟

function simulate(X,Y) m = 108; % Number of rolls in a single game. n = 10000; % Number of games in a simulation. s = zeros(1,n); for k = 1:n for l = 1:m i = randi(6); j = randi(6); if X(i) > Y(j) s(k) = s(k) + 1; elseif X(i) < Y(j) s(k) = s(k) - 1; % else X(i) == Y(j) % push counts as a roll end end end clf shg histogram(s) line([0 0],get(gca,'ylim'),'color','k','linewidth',2) title(sprintf('mean = %6.2f',mean(s))) end

I'll initialize the random number generator so that I get the same results every time Ipublishthis post.

rng(1)

Now verify thatAbeatsB.

模拟(A,B);

Sure enough, the 2:1 odds imply thatAcan be expected to be ahead by 108/3 dollars after 108 flips. There is a vertical black line at zero to emphasize that this isn't a fair game.

How about those 4:5 odds forAversusC?Acan be expected to lose 108/9 dollars with 108 flips.

模拟(A,C)

Three dice nontransitive set

Efron's dice were introduced in aScientific Americanarticle by Martin Gardner in 1970. Since then a number of people have found other sets of nontransitive dice with interesting properties. TheWikipedia article on nontransitive dicehas an abundance of information, including the following set.

A = [1 1 3 5 5 6]; B = [2 3 3 4 4 5]; C = [1 2 2 4 6 6];

This set is very close to a conventional set. The sum of the numbers on each die is 21, the same as a conventional die. And each die differs from a standard1:6die in only two places. Nevertheless, the set is nontransitive.

Since this is so close to a conventional set, we expect the odds to be closer to even. Let's see.

AvB = compare(A,B)

X 1 1 3 5 5 6 Y 2 -1 -1 1 1 1 1 3 -1 -1 0 1 1 1 3 -1 -1 0 1 1 1 4 -1 -1 -1 1 1 1 4 -1 -1 -1 1 1 1 5 -1 -1 -1 0 0 1 AvB = 17 4 15

Since the dice have matching values, we have some zeros in the matrix.Ahas only 17 winning values compared toB's 15.

模拟(A,B)

Here is the result all three pairwise comparisons.

A B C A 17:15 15:17 B 15:17 17:15 C 17:15 15:17

Get the MATLAB code

Published with MATLAB® R2017a