Mathematics for Computer Science

Chapter 16 Events and Probability Spaces532

D 1

D 3 D 2

D 1

D 3 D 2

D 1

D 3 D 2

D 1

D 3 D 2

D 1

D 3 D 2

D 1

D 3 D 2

D 1

D 3 D 2

D 1

D 3 D 2

.a/ .b/ .c/ .d/

.e/ .f / .g/ .h/

Figure 16.10 All possible relative strengths for three diceD 1 ,D 2 , andD 3. The
edge

̋

Di!Dj

̨

denotes that the sum of rolls forDiis likely to be greater than the
sum of rolls forDj.

Even Stranger Dice

The weird behavior of the three strange dice above generalizes in a remarkable
way.^2 The idea is that you can find arbitrarily large sets of dice which will beat
each other in any desired pattern according to how many times the dice are rolled.
The precise statement of this result involves several alternations of universal and
existential quantifiers, so it may take a few readings to understand what it is saying:

Theorem 16.3.1.For anyn 2 , there is a set ofndice with the following property:
foranyn-node digraph with exactly one directed edge between every two distinct
nodes,^3 there is a number of rollsksuch that the sum ofkrolls of theith die is
bigger than the sum for thejth die with probability greater than1=2iff there is an
edge from theith to thejth node in the graph.

For example, the eight possible relative strengths fornD 3 dice are shown in
Figure 16.10.
Our analysis for the dice in Figure 16.6 showed that for 1 roll, we have the
relative strengths shown in Figure 16.10(a), and for two rolls, we have the (reverse)
relative strengths shown in Figure 16.10(b). If you are prone to gambling with

(^2) Reference Ron Graham paper.
(^3) In other words, for every pair of nodesu¤v, eitherhu!viorhv!ui, but not both, are edges
of the graph. Such graphs are calledtournament graphs, see Problem 9.4.