Friday, April 4, 2008

Non-transitice dice

Transitivity is a nice property and people like it when it occurs. Relationships that are transitive have the general property that A~B and B~C implies A~C. For example, if A is greater than B, and B is greater than C, then A is greater than B.

First, a definition: consider fair dice with some number of sides but the numbers are not necessarily the numbers one normally has on a die. So for example a die with sides( 1,2,3,4,5,6) on the sides would be ok, but so would one with (2,2,3,4) or even for our purposes (1,2) or even just (1) (this hypothetical dice just always lands on 1). For our purposes we will describe a die solely by what numbers it has on its sides. Now, a definition: we define die A to beat die B if when A and B are rolled more than half the time die A yields a higher number than die B. So for example die A (0,5,5,5,5) beats die B (1,2,3,4) since 4/5ths of the time A yields a higher result than B.

Now, one might think that if I have three dice, A, B and C and if A is beaten by B and B is beaten by C then A is beaten by C. However, as you likely guessed from the subject of this post, that is not always the case. And what’s more, we don’t need fancy die with many sides or anything. We can do a simple example with three six sided die. Consider the die A= (3,3,3,3,3,9) , die B=(1,4,7,7,7,7) and die C=(2,2,2,8,8,8). I claim that die A is beaten by die B, die B is beaten by die C but in fact die C is beaten by die A. Now, we could verify this by enumerating all the possible examples for each pair of dice rolls, but this isn’t tedious, so instead we’ll just think a little bit. First, consider the cases of A and B. 5/6th of the time, A rolls a 3. 5/6th of the time B rolls a 4 or a 7, both of which are greater than a 3. Thus, B has a higher number than A at least (5/6)^2=25/36>1/2 the time. Now, consider B and C. Half the time C rolls an 8 and so has a higher number than B automatically. Furthermore, when C rolls a 2 B sometimes rolls a 1. So more than half the time C yields a higher number than B. So C beats B. Now, the logic for the third set is almost identical to the previous one. Whenever C rolls a 2, A wins. But whenever A rolls a 9, A wins no matter what. So more than half the time A wins. Thus, A does in fact beat C.


Erick P. said...

You told me at one point to find the minimal number of faces for non-transitivity. I cliam that the answer is seven, with three "dice".

A = (1,1,4)
B = (2)
C = (0,3,3)
is non-transitive (A < B < C < A). You showed that you can't have non-transitive coins (= 2-sided dice). Since a one-sided dice can be viewed as a coin, the only case with less than 7 faces is
A = (a)
B = (b1,b2)
C = (c1,c2,c3)
If this is non-transitive, either A < B < C < A or A < C < B < A. If A < C < B < A, -A < -B < -C < -A, so we may assume that A < B < C < A. Then b1 >= a and b2 >= a. Since C > B, C > B', where B'=(a,a), as every winning combination in C vs. B is also a winning combination in C vs. B'. Thus C > A and C < A, which is a contradiction.

Erick Knight

Joshua said...

Erick, that looks correct to me. I haven't seen the technique of taking the negatives of the dice before to eliminate a case which is a nice touch.