26
$\begingroup$

Once upon a time I read about nontransitive dice - sets of dice where "is more likely to roll a higher number than" is not a transitive relation. After the surprise wore off, I wondered - just how far can this phenomenon be pushed? The linked Wikipedia page has a section called "Freivald's investigation" which states that if $n$ dice are arranged in a circle each with probability $p$ of being greater than the next in line, then $p<3/4$ (with $p$ otherwise allowed arbitrarily close). However, it has the infamous tag of [citation needed] and I haven't been able to find any references. But a much more general question is possible.

If we have $n$ random variables, all independent, labelled $1,2,\dots, n$, and we denote by $p_k$ the probability $P(X_k > X_{k+1})$ (with the index $n+1$ cycled around to $1$), then we can speak of the vector $\vec{p}=(p_1,\dots,p_n)\in(0,1)^n$. This raises the question: what is the shape of the space $V \subset (0,1)^n$ of all possible $\vec{p}$'s? In particular, I think there might be a symmetric function such that $V$ is the region bounded by the level sets of $f(\vec{x})$ and $f(\vec{1}-\vec{x})$ for some $f:\mathbb{R}^n\to\mathbb{R}$, but I'm not certain, and of course it seems like it would be impossible to find such an $f$ explicitly. (Also, I'm not sure if the answer would be different for continuous and for discrete situations, or in mixed cases, but all combinations sound interesting.)

  • 1
    Nice question! The Wikipedia article says that the $p<3/4$ result holds "when $n$ goes to infinity". I presume that means that there's a tighter bound for smaller $n$ and the bound goes to $3/4$ as $n$ goes to infinity. Also it doesn't say what kind of dice it's talking about, but the entire article seems to be presuming six-sided dice.2011-08-14
  • 4
    Actually, the "$p$ arbitrarily close to $3/4$" thing doesn't make sense for six-sided dice -- the probability for one six-sided die being greater than another is always a multiple of $1/36$, so if it's not $3/4$, it can be at most $26/36$. So perhaps the number of sides is intended to be taken to infinity, too -- which would allow us to approximate continuous distributions arbitrarily closely, so in that case this would presumably already imply part of the more general result you're looking for...2011-08-14

1 Answers 1

11

We can assume without loss of generality that all numbers are different, since otherwise we could make them slightly different without decreasing the probability for any die to be greater than any other die (since equal results don't contribute to that probability).

Roughly speaking, if the median on the losing die is greater than the median on the winning die, then the lower half of the winning die can't beat the upper half of the losing die, so for the median to increase, we must have $p<3/4$. There are some details to fill in for even and odd numbers of sides; the result is that $p\le3/4-(n/2+\alpha)/n^2$, where $n$ is the number of sides and $\alpha=0$ for even $n$ and $\alpha=1/4$ for odd $n$. This goes to $3/4$ as $n$ goes to infinity.

The number at any rank other than the median can be more easily increased, since you can let all the numbers below it on the winning die beat all the numbers below it on the losing die, and the same for the numbers above it, and the restriction this imposes is tightest at the median. Thus, for each rank, there is an admissible combination to increase the number at that rank.

Now put $n$ dice with $n$ sides in a cycle, and impose a partial order on the as yet unknown numbers by requiring that in each pair of consecutive dice the numbers form one of the order patterns constructed above, with the number at rank $k$ being increased in step $k$ (beginning at the highest rank). To see that this partial order is a total order, note that there is no restriction requiring any number in the shrinking lower parts below the ranks being increased to be greater than any number in the growing upper parts above the ranks being increased. Thus there are no cycles in this order (this is easy to see if you draw out its graph for $n=3$ or $4$), so we can find suitable numbers by topological sorting. Thus we can always construct a cycle with $n$ dice with $n$ sides for $p$ as above; in fact this construction makes it rather straightforward to derive suitable numbers.

Here are examples for $n=3$ and $n=4$ (the latter in hexadecimal), with an attempt to visualize the acyclicity of the order graph:

1 2 8
|/ /|
0 6 7
 /|/|
3 4 5
|/|/
1 2 8
|/ /|
0 6 7

3 4 5 F
|/|/ /|
1 2 D E
|/ /|/|
0 A B C
 /|/|/|
6 7 8 9
|/|/|/
3 4 5 F
|/|/ /|
1 2 D E
|/ /|/|
0 A B C
  • 0
    I'm not entirely sure I fully agree with the answer, as not all cases are actually admissible with any number Z of N-faced dice. Could you please elaborate on how the upper limit is $p\leq 3/4 +f(n)$? It seems that you have taken the maximum of all instances whenever the median of the losing die is higher than the winning die - but this doesn't necessarily happen for *all dice* in the set. There can be dice presenting contributions "from the lower" half that sum up to the rest increasing the value of the $P$ for those dice.2016-09-13
  • 0
    Also, one would expect the result to also depend on the number Z of dice, as not all N allow non-transitive sets chosen any Z (just imagine to have Z $\gg$ N), would one not?2016-09-13
  • 0
    @gented: We seem to have different understandings of what was to be proved. Here's the state of the Wikipedia page at the time the question was asked: https://en.wikipedia.org/w/index.php?title=Nontransitive_dice&oldid=444773302#Freivalds's_investigation. It says "if there is a set of $n$ dice, and each die beats the next with probability $p$, then $p$ can be arbitrary close (but not equal) to $3/4 = 0.75$ when $n$ goes to infinity."2018-07-31
  • 0
    The question omitted the part about $n$ going to infinity, and in a comment under the question I pointed out that the statement is also wrong for a fixed number of sides, so the number of sides must also be taken to infinity. Thus, what I wanted to prove here was a) no set of intransitive dice can have $p\ge3/4$ and b) if we can use arbitrarily many sides and dice, we can get arbitrarily close to $p=3/4$. Do you agree that I did indeed prove this (except for the details to fill in on the inequality $p\le3/4-(n/2+\alpha)/n^2$)?2018-07-31
  • 0
    I do not understand how you derive the above conclusions (especially second and fourth paragraph) without loss of generatily - they do not hold true for any number Z of N-faced dice. I am asking because I have been working on a similar problem and I could not fill in those gaps in the proof. If we assume this is the case (and in particular that $p\leq 3/4 - ()^2$) then of course the result holds true.2018-07-31
  • 0
    @gented: If the number of sides is $n=2k+1$, each die has a median. Since the numbers are assumed to be all different, these medians are all different, so there's at least one pair where the losing die has the greater median. Then the $k+1$ highest numbers on the losing die beat the $k+1$ lowest numbers on the winning die, so the winning probability is at most $1-(k+1)^2/(2k+1)^2=\frac34-(n/2+\frac14)/n^2$. Do you agree that this establishes the inequality for odd $n$? The case of even $n$ can be treated similarly. I don't understand how the number of dice enters into it at this point.2018-07-31
  • 0
    *"Since the numbers are assumed to be all different, these medians are all different"* what numbers are you referring to? If you are referring to the labels on the faces then yes, the rest follows trivially; if not, can one still prove the same equality (I wouldn't know how to)?2018-07-31
  • 0
    @gented: I do mean the labels on the faces -- both in the answer and in my comments "the numbers" always refers to the labels on the faces. I'm not sure whether I understand the rest of your comment -- which case are you referring to by "if not"? If the numbers are not assumed to be all different? I justified that assumption in the first sentence of the answer.2018-07-31
  • 0
    That's exactly my point: *"We can assume without loss of generality that all numbers are different"* - this is *not* without loss of generality (or at least it must be proven). One can construct counter-examples (by repeating the same label many times on the same die) such that the assumptions on the medians being different and the partial orderings are not fulfilled: would the final result still hold the same in that case?2018-07-31
  • 0
    @gented: We want to prove an upper bound for $p$, which is defined in the question as the probability of "being greater" than the next die and in the Wikipedia article as the probability of "beating" the next die. If the dice show the same number, that doesn't count towards "being greater" / "beating". So if some numbers coincide and we shift them slightly to make them different, we can't decrease $p$. So any upper bound on $p$ we derive under the assumption of different numbers also applies to cases with coinciding numbers. Or am I missing something?2018-07-31
  • 0
    I agree completely with you, my only point was that apparently the value 3/4 is "trivially" the upper bound (as seemingly it is a matter of filling in some details) and I do not see this triviality. Imagine you have a set of dice with an extremely large number of faces, also allowing the same label to be repeated as many times as possible: I could not find a way to prove that the equality that you show above easily holds (and therefore 3/4 is trivially the upper bound). I will give it another try, however :).2018-07-31
  • 0
    @gented: Somehow we seem to be talking past each other. I just filled in the details. The calculation above involving $1-(k+1)^2/(2k+1)^2$ was all the detail there is to the case of odd $n$. I don't see where else you see details to be filled in. I never wrote that it was "trivially" true -- I wrote that some details were left to be filled in, and now I've filled them in. Where's the gap in the proof?2018-07-31