# 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)\le 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,\mathrm{\dots},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\text{is arrowed by}{v}_{0})=\frac{1}{{2}^{k}}.$$ |

The complementary event, is therefore,

$$P(K\text{is}\text{not}\text{arrowed by}{v}_{0})=1-\frac{1}{{2}^{k}}.$$ |

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

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

Lastly, since there are $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ 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\text{vertices is not arrowed by any vertex})\le \left(\genfrac{}{}{0pt}{}{n}{k}\right){\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

$\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\left(1-{\displaystyle \frac{1}{{2}^{k}}}\right)}^{n-k}$ | $=$ | $\frac{1}{k!}}n(n-1)\mathrm{\cdots}(n-k+1){\left(1-{\displaystyle \frac{1}{{2}^{k}}}\right)}^{n-k$ | ||

$$ | $\frac{1}{k!}}{n}^{k}{\left(1-{\displaystyle \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 |
---|---|

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 |