example of a probabilistic proof

Our example is the existence of k-paradoxical tournaments. The proof hinges upon the following basic probabilistic inequality, for any events A and B,

Theorem 1.

For every k, there exists a k-paradoxical tournament.


We will construct a tournament T on n vertices. We will show that for n large enough, a k-paradoxical tournament must exist. The probability spaceMathworldPlanetmath in question is all possible directions of the arrows of T, where each arrow can point in either direction with probability 1/2, independently of any other arrow.

We say that a set K of k vertices is arrowed by a vertex v0 outside the set if every arrow between v0 to wiK points from v0 to wi, for i=1,,k. Consider a fixed set K of k vertices and a fixed vertex v0 outside K. Thus, there are k arrows from v0 to K, and only one arrangement of these arrows permits K to be arrowed by v0, thus

P(K is arrowed by v0)=12k.

The complementary event, is therefore,

P(K is not arrowed by v0)=1-12k.

By independence, and because there are n-k vertices outside of K,

P(K is not arrowed by any vertex)=(1-12k)n-k. (1)

Lastly, since there are (nk) sets of cardinality k in T, we employ the inequality mentioned above to obtain that for the union of all events of the form in equation (1)

P(Some set of k vertices is not arrowed by any vertex)(nk)(1-12k)n-k.

If the probability of this last event is less than 1 for some n, then there must exist a k-paradoxical tournament of n vertices. Indeed there is such an n, since

(nk)(1-12k)n-k = 1k!n(n-1)(n-k+1)(1-12k)n-k
< 1k!nk(1-12k)n-k

Therefore, regarding k as fixed while n tends to infinity, the right-hand-side above tends to zero. In particular, for some n it is less than 1, and the result follows. ∎

Title example of a probabilistic proof
Canonical name ExampleOfAProbabilisticProof
Date of creation 2013-03-22 13:06:18
Last modified on 2013-03-22 13:06:18
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 13
Author bbukh (348)
Entry type Example
Classification msc 05C80