Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A set of nontransitive dice is a set of dice whose face numbers are such that the relation "is more likely to roll a higher number than" is not transitive. (See wikipedia)

For some sets, the deviation from transitivity is small in the sense that A beats B beats C beats A with probabilities $p_{ij}$ only slightly greater than $0.5$ . Efron's dice (there are 4 of them) beat each other nontransitively with probability $2/3$.

Can we make a strictly better set of 4 six-sided dice? That is, a set of 4 six-sided dice such that they beat each other nontransitively with all probabilities $> 2/3$ ?

Can we make a strictly better set of 4 $n$-sided dice for some small $n$ which one can conveniently make a die out of, e.g. $n = 4, 8, 12, 20 $ ?

Can we make a strictly better set of 5 $n$-sided dice for some small $n$ which one can conveniently make a die out of, e.g. $n = 4, 6, 8, 12, 20 $ ?

Can we make a strictly better set of 3, 4 or 5 dice, each having potentially a different number of sides ($4, 6, 8, 12$ or $20$) ?

Ideally I would like to find a fairly small set of fairly easy-to-make, preferably platonic-solid dice which beat each other nontransitively with probabilities > 80%. They would make an excellent teaching aid and magic trick. There is another answer on math.stackexchange which claims that the best you can do with 3 dice is $p = 0.58$, which is disappointingly close to $0.5$; for a teaching aid you need to be able to beat students almost every time for them to spot the pattern quickly. Efron's dice are substantially better at $2/3$, but is that really the best we can do?

EDIT: I missed this answer which argues that the probability cannot be > than 0.75 irrespective of the details of the dice. Still, it would be nice to know what the "simplest"/smallest set of "simple" dice is that gets you above, say, 70%, 72%, etc.

Also, assuming that the other player doesn't yet understand what's going on, a uniform nontransitive probability of $75%$ - $\epsilon$ can still be improved by making some dice lose with probability > $75$%, so that if the other player chooses randomly from the dice, the will get beaten on average much more than $75$% of the time. The "worse" choices can be encouraged by making the highest number on them very high. As far as I understand the proof in this answer, this possibility is not excluded.

share|improve this question
    
With 4 dice, I suppose you would like to forbid A > B > C > A; D > A, D > B, D > C, and insist A > B > C > D > A? Or what, exactly? –  MJD Jan 24 '13 at 23:15
    
If there is a nontransitive 3-chain in a set of 4 dice, then the 4th dice is superfluous, and there is another answer here on math.stackexchange which claims that the best you can do with 3 dice is $p = 0.58$ –  Rationalist Jan 25 '13 at 17:33
    
You're not going to get $p > 80$% no matter what you do. As this question notes, there's a strict upper bound of $p<3/4$ for any intransitive set of random variables, and for 6-sided dice considerations of discreteness reduce that to $p<2/3$ (so Efron's dice are optimal for a set of 6-sided dice). –  Micah Jan 25 '13 at 18:03
    
Thanks, Micah, I just caught that. Presumably there might be a set of 3 20-sided dice which achieve the bound for n=20 sides, 72.5%. This would still be fairly impressive; although the constructed solution in the answer we linked to uses n n-sided dice, Efron shows that you can hit the bound with less than n dice. How good does it get? –  Rationalist Jan 25 '13 at 18:35
    
Note that the question for which I determined the optimum $p=21/36\approx0.58$ required the win probability to be independent of which die you pick. The code I posted there is easily modified not to impose that requirement, and then it finds this set of three dice: $(0,3,3,3,3,3)$, $(2,2,2,2,2,5)$, $(1,1,1,4,4,4)$, with win probabilities $25/36$, $21/36$, $21/36$, for which the expected win probability upon uniformly randomly choosing a die is $67/108\approx0.62$, and the worst choice has the highest number. I hope to be posting an answer with more results when I find the time. –  joriki Jan 26 '13 at 13:01
show 4 more comments

1 Answer

The set of 3 dice, each with six faces, as follows

A = 0 3 3 3 3 3 B = 1 1 1 3 4 4 C = 2 2 2 2 2 3

is nontransitive, with probabilities

A wins B ---> 16/31

B wins C ---> 18/35

C wins A ---> 25/31.

As 25/31 is bigger than 0.8, what does the absolute constraint of 3/4 mean?

share|improve this answer
1  
It means that you can't have all probabilities $\ge 3/4$. –  TonyK Aug 3 '13 at 9:59
    
You seem to get some ties, and most people might say 3 beats 2. –  Henry Dec 16 '13 at 8:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.