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{<em class="ltx\_emph ltx\_font\_italic">not</em>}\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{<em class="ltx\_emph ltx\_font\_italic">any</em>}\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}$ $=$ ${\displaystyle \frac{1}{k!}}n(n-1)\mathrm{\cdots }(n-k+1){\left(1-{\displaystyle \frac{1}{2^k}}\right)}^{n-k}$

${\displaystyle \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