example of a probabilistic proof
For every , there exists a -paradoxical tournament.
We will construct a tournament on vertices. We will show that for large enough, a -paradoxical tournament must exist. The probability space in question is all possible directions of the arrows of , where each arrow can point in either direction with probability , independently of any other arrow.
We say that a set of vertices is arrowed by a vertex outside the set if every arrow between to points from to , for . Consider a fixed set of vertices and a fixed vertex outside . Thus, there are arrows from to , and only one arrangement of these arrows permits to be arrowed by , thus
The complementary event, is therefore,
By independence, and because there are vertices outside of ,
Lastly, since there are sets of cardinality in , we employ the inequality mentioned above to obtain that for the union of all events of the form in equation (1)
If the probability of this last event is less than for some , then there must exist a -paradoxical tournament of vertices. Indeed there is such an , since
Therefore, regarding as fixed while tends to infinity, the right-hand-side above tends to zero. In particular, for some it is less than , and the result follows. ∎