27
$\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.)

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – joriki
    Aug 14, 2011 at 8:00
  • 5
    $\begingroup$ 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... $\endgroup$
    – joriki
    Aug 14, 2011 at 8:25

2 Answers 2

Reset to default
11
$\begingroup$

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
$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$
    – gented
    Sep 13, 2016 at 0:07
  • $\begingroup$ 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? $\endgroup$
    – gented
    Sep 13, 2016 at 9:59
  • $\begingroup$ @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: en.wikipedia.org/w/…. 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." $\endgroup$
    – joriki
    Jul 31, 2018 at 14:17
  • $\begingroup$ 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$)? $\endgroup$
    – joriki
    Jul 31, 2018 at 14:18
  • $\begingroup$ 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. $\endgroup$
    – gented
    Jul 31, 2018 at 14:34
0
$\begingroup$

This is a great question, and answered in essentially those terms in this paper from 1965:

Trybuła, S. On the paradox of $n$ random variables. Zastos. Mat. 8 (1965), 143–156.

Three he gets a sequence of inequalities on the probabilities you're asking for, but isn't able to solve them concretely.

The case of $n$ variables arranged cyclically is solved by Bogdanov in 2010, and again in a very recent paper:

Komisarski, Andrzej Nontransitive random variables and nontransitive dice. Amer. Math. Monthly 128 (2021), no. 5, 423–434. https://www.tandfonline.com/doi/abs/10.1080/00029890.2021.1889921?journalCode=uamm20

The answer is that with $n$ dice you cannot beat $1-\frac{1}{4 \cos^2 (\pi/(n+2))}$. Komisarksi gives a very nice geometric argument.

The $3/4$ bound you mention in general was found already by Trybuła.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .