## You are here

Homeexample of a probabilistic proof

## Primary tabs

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

## Mathematics Subject Classification

05C80*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections