# How far can probability intransitivity be stretched?

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.)

-
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. – joriki Aug 14 '11 at 8:00
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... – joriki Aug 14 '11 at 8:25

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

-