Q. 3.24 - A First Course in Probability

Question

A round-robin tournament of $n$ contestants is a tournament in which each of the $\left(\frac{n}{2}\right)$ pairs of contestants play each other exactly once, with the outcome of any play being that one of the contestants wins and the other loses. For a fixed integer $k,k<n$, a question of interest is whether it is possible that the tournament outcome is such that for every set of $k$ players, there is a player who beat each member of that set. Show that if

                                                  $\left(\begin{array}{l}n\\ k\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}<1$

then such an outcome is possible.

Hint: Suppose that the results of the games are independent and that each game is equally likely to be won by either contestant. Number the $\left(\begin{array}{l}n\\ k\end{array}\right)$ sets of $k$ contestants, and let $B_i$ denote the event that no contestant beat all of the $k$ players in the $i^{th}$  set. Then use Boole's inequality to bound $P\left(\underset{i}{\cup } B_i\right)$.

Step-by-Step Solution

Answer

Demonstrate that following inequality imply, $P\left(A_k^c\right)<1$

Step 1: Given data

For $\left(\frac{n}{2}\right)$ individual matches, $n$ similarly competent players compete against one another.

$A_k$ - for every $k$ individuals chosen, at most the another player outperformed it all.

$B_l$ - There is no mutual winner among the $k$ participants inside the $l-\text{ th }$ set,  $l=1,2,\dots ,\left(\begin{array}{l}n\\ k\end{array}\right)$

$\frac{1}{2}$ is the possibility of particular player succeeding in such a specific game.

Show if 

                               $\left(\begin{array}{l}n\\ 2\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}<1$

then 

                                   $P\left(A_k\right)>0$

Step 2: Boole's inequality

At minimum single $B_i$ existed when $A_k$ didn't take place, and inversely, it is:

                                                   $A_k^c=\underset{l=1}{\overset{\left(\begin{array}{l}n\\ k\end{array}\right)}{\cup }} B_l$

Boole's inequalities, which is established from the formula combining inclusion as well as exclusion conditions for whichever series of incidents, in this case $B_1,B_2,\dots B_l$.

                                                 $P\left(\underset{l=1}{\overset{\left(\begin{array}{l}n\\ k\end{array}\right)}{\cup }} B_l\right)\le \sum _{l=1}^{\left(\begin{array}{l}n\\ k\end{array}\right)} P\left(B_l\right)$

The probability of outcomes $i=1,2,3,\dots ,\left(\begin{array}{l}n\\ k\end{array}\right)$ were same since they're balanced.

                                      

                                          $P\left(A_k^c\right)=P\left(\begin{array}{l}\left(\begin{array}{c}n\\ k\end{array}\right)\\ \cup \\ l=1\end{array}\right)\le \left(\begin{array}{l}n\\ k\end{array}\right)P\left(B_1\right)$                     $\left(1\right)$

Its possibility that particular player wins every match against $k$ competitors watched was

                                                                    ${\left(\frac{1}{2}\right)}^k$

Step 3: Prove P A k c &#60; 1

Because the activities are self-contained. 

It should occur for each one of remaining $n-k$ participants. These events were self-contained since they were determined by outcomes of assorted games and so the people participating. Against by observed $k$, chance that neither of any $n-k$ competitors succeeded seems to be:

                                              $P\left(B_1\right)={\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}$

Put the equation $\left(1\right)$,

                                            $P\left(A_k^c\right)\le \left(\begin{array}{l}n\\ k\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^n$

 So, if

                                                  $\left(\begin{array}{l}n\\ 2\end{array}\right){\left[1-{\left(\frac{1}{2}\right)}^k\right]}^{n-k}<1$

Then $P\left(A_k^c\right)<1$ and which is equal to $P\left(A_k\right)>0$