421 probability/transitivity.p
Description
This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.
421 probability/transitivity.p
Can you number dice so that die A beats die B beats die C beats die A?
What is the largest probability p with which each event can occur?
probability/transitivity.s
Yes. The actual values on the dice faces don't matter, only their
ordering. WLOG we may assume that no two faces of the same or
different dice are equal. We can assume "generalised dice", where the
faces need not be equally probable. These can be approximated by dice
with equi-probable faces by having enough faces and marking some of
them the same.
Take the case of three dice, called A, B, and C. Picture the different
values on the faces of the A die. Suppose there are three:
A A A
The values on the B die must lie in between those of the A die:
B A B A B A B
With three different A values, we need only four different B values.
Similarly, the C values must lie in between these:
C B C A C B C A C B C A C B C
Assume we want A to beat B, B to beat C, and C to beat A. Then the above
scheme for the ordering of values can be simplified to:
B C A B C A B C A B C
since for example, the first C in the previous arrangement can be moved
to the second with the effect that the probability that B beats C is
increased, and the probabilities that C beats A or A beats B are
unchanged. Similarly for the other omitted faces.
In general we obtain for n dice A...Z the arrangement
B ... Z A B ... Z ...... A B ... Z
where there are k complete cycles of B..ZA followed by B...Z. k must be
at least 1.
CONJECTURE: The optimum can be obtained for k=1.
So the arrangement of face values is B ... Z A B ... Z. For three dice
it is BCABC. Thus one die has just one face, all the other dice have two
(with in general different probabilities).
CONJECTURE: At the optimum, the probabilities that each die beats the
next can be equal.
Now put probabilities into the BCABC arrangement:
B C A B C
x y 1 x' y'
Clearly x+x' = y+y' = 1.
Prob. that A beats B = x'
B beats C = x + x'y'
C beats A = y
Therefore x' = y = x + x'y'
Solving for these gives x = y' = 1-y, x' = y = (-1 + sqrt(5))/2 = prob.
of each die beating the next = 0.618...
For four dice one obtains the probabilities:
B C D A B C D
x y z 1 x' y' z'
A beats B: x'
B beats C: x + x'y'
C beats D: y + y'z'
D beats A: z
CONJECTURE: for any number of dice, at the optimum, the sequence of
probabilities abc...z1a'b'c...z' is palindromic.
We thus have the equalities:
x+x' = 1
y+y' = 1
z+z' = 1
x' = z = x + x'y' = x + x'y'
y = y' (hence both = 1/2)
Solving this gives x = 1/3, z = 2/3 = prob. of each die beating the next.
Since all the numbers are rational, the limit is attainable with
finitely many equiprobable faces. E.g. A has one face, marked 0. C has
two faces, marked 2 and -2. B has three faces, marked 3, -1, -1. D has
three faces, marked 1, 1, -3. Or all four dice can be given six faces,
marked with numbers in the range 0 to 6.
Finding the solution for 5, 6, or n dice is left as an exercise.
-- ____ Richard Kennaway __\_ / School of Information Systems Internet: jrk@sys.uea.ac.uk \ X/ University of East Anglia uucp: ...mcsun!ukc!uea-sys!jrk \/ Norwich NR4 7TJ, U.K.
Martin Gardner (of course!) wrote about notransitive dice, see the Oct '74
issue of Scientific American, or his book "Wheels, Life and Other Mathematical
Amusements", ISBN 0-7167-1588-0 or ISBN 0-7167-1589-9 (paperback).
In the book, Gardner cites Bradley Efron of Stanford U. as stating that
the maximum number for three dice is approx .618, requiring dice with more
than six sides. He also mentions that .75 is the limit approached as the
number of dice increases. The book shows three sets of 6-sided dice, where
each set has 2/3 as the advantage probability.
Continue to:
My Books
