# 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$,

 $P\left(A\cup B\right)\leq P(A)+P(B)$
###### Theorem 1.

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

###### Proof.

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 space  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 $v_{0}$ outside the set if every arrow between $v_{0}$ to $w_{i}\in K$ points from $v_{0}$ to $w_{i}$, for $i=1,~{}\ldots,k$. Consider a fixed set $K$ of $k$ vertices and a fixed vertex $v_{0}$ outside $K$. Thus, there are $k$ arrows from $v_{0}$ to $K$, and only one arrangement of these arrows permits $K$ to be arrowed by $v_{0}$, thus

 $P(K~{}\mbox{ is arrowed by }~{}v_{0})=\frac{1}{2^{k}}.$

The complementary event, is therefore,

 $P(K~{}\mbox{ is \emph{not} arrowed by }~{}v_{0})=1-\frac{1}{2^{k}}.$

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

 $P(K~{}\mbox{ is not arrowed by \emph{any} vertex})=\left(1-\frac{1}{2^{k}}% \right)^{n-k}.$ (1)

Lastly, since there are $\binom{n}{k}$ 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(\text{Some set of k vertices is not arrowed by any vertex})\leq\binom{n}{k% }\left(1-\frac{1}{2^{k}}\right)^{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

 $\displaystyle\binom{n}{k}\left(1-\frac{1}{2^{k}}\right)^{n-k}$ $\displaystyle=$ $\displaystyle\frac{1}{k!}n(n-1)\cdots(n-k+1)\left(1-\frac{1}{2^{k}}\right)^{n-k}$ $\displaystyle<$ $\displaystyle\frac{1}{k!}n^{k}\left(1-\frac{1}{2^{k}}\right)^{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 ExampleOfAProbabilisticProof 2013-03-22 13:06:18 2013-03-22 13:06:18 bbukh (348) bbukh (348) 13 bbukh (348) Example msc 05C80