Chapter 16 Events and Probability Spaces696
Problem 16.11.
The results of a round robin tournament in which every two people play each other
and one of them wins can be modelled atournament digraph—a digraph with ex-
actly one edge between each pair of distinct vertices, but we’ll continue to use the
language of players beating each other.
Ann-player tournament isk-neutralfor somek 2 Œ0;n/, when, for every set of
kplayers, there is another player who beats them all. For example, being 1-neutral
is the same as not having a “best” player who beats everyone else.
This problem shows that for any fixedk, ifnis large enough, there will be a
k-neutral tournament ofnplayers. We will do this by reformulating the question in
terms of probabilities. In particular, for any fixedn, we assign probabilities to each
n-vertex tournament digraph by choosing a direction for the edge between any two
vertices, independently and with equal probability for each edge.
(a)For any setSofkplayers, letBSbe the event that no contestant beats every-
one inS. Express PrŒBSçin terms ofnandk.
(b)LetQkbe the event equal to the set ofn-vertex tournament digraphs that are
notk-neutral. Prove that
PrŒQkç
n
k!
̨n k;where ̨WWD 1 .1=2/k.
Hint:LetSrange over the size-ksubsets of players, so
QkD[
SBS:
Use Boole’s inequality.
(c)Conclude that ifnis enough larger thank, then PrŒQkç < 1.(d)Explain why the previous result implies that for every integerk, there is a
k-neutral tournament.
Homework Problems
Problem 16.12.
Suppose you repeatedly flip a fair coin until three consecutive flips match the pat-
ternHHTor the patternTTHoccurs. What is the probability you will seeHHT
first? Define a suitable probability space that models the coin flipping and use it to
explain your answer.
Hint:Symmetry between Heads and Tails.