Question

This exercise employs the probabilistic method to prove a result about round-robin tournaments. In a round-robin tournament with m players, every two players play one game in which one player wins and the other loses. We want to find conditions on positive integers \(m\)and \(k\) with \(k < m\)such that it is possible for the outcomes of the tournament to have the property that for every set of \(k\)players, there is a player who beats every member in this set. So that we can use probabilistic reasoning to draw conclusions about round-robin tournaments, we assume that when two players compete it is equally likely that either player wins the game and we assume that the outcomes of different games are independent. Let \(E\)be the event that for every set \(S\) with \(k\)players, where \(k\) is a positive integer less than \(m\), there is a player who has beaten all \(k\) players in \(S\).

a) Show that\(p\left( {\bar E} \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \) , where \({F_j}\)is the event that there is no player who beats all k players from the set in a\(jth\) list of the \(\left( \begin{array}{l}m\\k\end{array} \right)\)sets of \(k\) players.

b) Show that the probability of\({F_j}\) is\({(1 - {2^{ - k}})^{m - k}}\).

c) Conclude from parts (a) and (b) that\(p\left( {\bar E} \right) \le \left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}}\)and, therefore, that there must be a tournament with the described property if\(\left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}} < 1\).

d) Use part (c) to find values of\(m\)such that there is a tournament with\(m\)players such that for every set Sof two players, there is a player who has beaten both players in\(S\). Repeat for sets of three players.

Short answer

Answer

a) The required result is\(p\left( {\bar E} \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \).

b) The probability of\({F_j}\)is\({(1 - {2^{ - k}})^{m - k}}\).

c) There is a tournament that satisfy the conditions of the event\(\left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}} < 1\)and It is concluded that\(p\left( {\bar E} \right) \le \left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}}\).

d) For the set S of two players,\(k = 2\)

That is,\(m \ge 21\).

For the set\(S\)of three players,\(k = 3\)

That is,\(m \ge 91\).

Step-by-step solution

Given Information  

In the given event \){F_j}\] no player can beat all the \(k\) players in the \(\left( \begin{array}{l}m\\k\end{array} \right)\)list of \(k\) players in the\(jth\)set, while in the event \(E\) there is a player who has beaten all \(k\) players for every set \(S\), where \(k\)is a positive integer and \(k < m\).

Definition and Formula to be used

Boole’s inequality states that for countable set of events , the probability of occurring of at least one of the events is less than or equal to sum of probabilities of the events individually that is \(p\left( {\bigcup\limits_{j = 1}^\infty {{A_j}} } \right) \le \sum\limits_{j = 1}^\infty {p\left( {{A_j}} \right)} \) where \({A_j}\) are the events occurring.

Show that \(p\left( {\bar E} \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \)

The complementary of given event\(E\)is\(\bar E\).

Also, in the event\({F_j}\)no player can beat all the\(k\)players in the list of\(\left( \begin{array}{l}m\\k\end{array} \right)\)set of\(k\)players in the\(jth\)set.

The Union of all\({F_j}\)sets will be equal to\(\bar E\)which is mentioned below.

\(\bar E = \bigcup\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {{F_j}} \)

Use Boole’s inequality\(p\left( {\bigcup\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {{F_j}} } \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \)

Substitute the value of\(\bar E\)in above inequality as,

\(p\left( {\bar E} \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \).

Thus, \(p\left( {\bar E} \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \) \(...\left( 1 \right)\)

Show that probability of\({F_j}\) is\({\left( {1 - {2^{ - k}}} \right)^{m - k}}\)

The probability that a particular player which is not in the\(jth\)set beat all the\(k\)players in\(jth\)set is,\(\frac{1}{{{2^k}}}\)

So, the probability that this player is unable to do as predicted is,\(1 - \frac{1}{{{2^k}}}\)

Then, the probability that\(\left( {m - k} \right)\)players which are not included in\(jth\)set are not being able to beat each player in\(jth\)set is,\({(1 - \frac{1}{{{2^k}}})^{m - k}}\)

Thus, probability of \({F_j}\)is \({(1 - {2^{ - k}})^{m - k}}\). \(........\left( 2 \right)\)

Use equation \(\left( 1 \right),\left( 2 \right)\)to conclude that \(p\left( {\bar E} \right) \le \left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}}\)and then show that \(\left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}} < 1\).

All the players in the list\(\left( \begin{array}{l}m\\k\end{array} \right)\)are same.

Thus, the inequality\(p\left( {\bar E} \right) \le \left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}}\)is true for each player.

If the above probability comes out to be less than\(1\)then the only possibility is that\(\bar E\)fails which implies event\(E\)to happen.

So, as long as the inequality holds, there exists a tournament which satisfy the conditions of the event

Thus \(\left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}} < 1\)\(......\left( 3 \right)\)

Use equation \(\left( 3 \right)\)and find\(m\)

The tournament of\(m\)players which happens is in a way that for every set\(S\)of two and three players, there is a player who has beaten both the players in\(S\).

From the equation\(\left( 3 \right)\), there exists a tournament satisfying the condition\(\left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}} < 1\)as long as the inequality remains.

For the set\(S\)of two players,\(k = 2\)

That is,\(m \ge 21\).

For the set\(S\)of three players,\(k = 3\)

That is,\(m \ge 91\).

a) The required result is\(p\left( {\bar E} \right) \le \sum\limits_{j = 1}^{\left( {\scriptstylem\atop\scriptstylek} \right)} {p\left( {{F_j}} \right)} \).

b) The probability of \({F_j}\) is\({(1 - {2^{ - k}})^{m - k}}\).

c) There is a tournament that satisfy the conditions of the event \(\left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}} < 1\) and It is concluded that \(p\left( {\bar E} \right) \le \left( \begin{array}{l}m\\k\end{array} \right){\left( {1 - {2^{ - k}}} \right)^{m - k}}\) .

d) For the set S of two players,\(k = 2\)

That is,\(m \ge 21\).

For the set\(S\)of three players,\(k = 3\)

That is,\(m \ge 91\).