18.5. Linearity of Expectation 779
H T
H T
H T
D
D
D
D
C
B
Figure 18.9 Outcome Tree for Flipping Until HHHhx!yiiffxbeatyin their game. Arankingof the players is a path that includes
all the players. A tournament digraph may in general have one or more rankings.^7
Suppose we construct a random tournament digraph by letting each of the players
in a match be equally likely to win and having results of all the matches be mutually
independent. Find a formula for the expected number of rankings in a random 10-
player tournament. Conclude that there is a 10-vertex tournament digraph with
more than 7000 rankings.
This problem is an instance of theprobabilistic method. It uses probability to
prove the existence of an object without constructing it.
Problem 18.15.
A coin with probabilitypof flipping Heads and probabilityqWWD 1 pof flipping
tails is repeatedly flipped until three consecutive Heads occur. The outcome tree,
D, for this setup is illustrated in Figure 18.9.
Lete.S/be the expected number of flips starting at the root of subtreeSofD.
So we’re interested in findinge.D/.
Write a small system of equations involvinge.D/;e.B/, ande.C/that could be
solved to finde.D/.You donotneed to solve the equations.
(^7) It has a unique ranking iff it is a DAG, see Problem 9.4.