12

$16$ players $P_1,P_2,....,P_{16}$ play a knockout tournament. It is known that whenever the players $P_i$ and $P_j$ play, the player $P_i$ will win if $i<j$. Assuming the players are paired at random in each round, what is the probability that the player $P_4$ reaches the semi final?

I know that $P_1$ will anyhow reach final and $P_{16}$ will not clear the first round. I dont know how to solve further.

The Phenotype
  • 5,199
learner_avid
  • 1,691
  • With so many branches to consider, my first thought would be to simply simulate it. Of course there may be some better way to visualize the process which leads to a convenient closed form but I'm not seeing it at the moment. – lulu Jul 03 '18 at 12:50
  • 1
    Also: the posted solutions all appear to imagine that you are randomizing the initial matches but thereafter abide by the standard bracket rules. My reading of the question is different...I assume you intend that the teams are "paired at random in each round" as you say. Still might be worth stressing the point in your post. – lulu Jul 03 '18 at 12:53
  • 1
    @lulu: I don't understand this distinction. What difference does it make when the pairings for the upper branches are drawn? There are no "standard bracket rules" beyond random pairings. You take one of these and randomly fill in the teams. What changes if you defer the decisions about the higher pairings? – joriki Jul 03 '18 at 13:14
  • 1
    @joriki (to repeat comments made in the chat room) I may well be missing a key insight here. I'll think it through over the course of the day. – lulu Jul 03 '18 at 13:28
  • 3
    I think I muddied the waters unhelpfully here. The answers based on symmetry are fine (and match the detailed working, and the simulation). – lulu Jul 03 '18 at 15:20
  • 1
    Possible duplicate of Probability of eighth best reaching the semifinals – Dan Uznanski Jul 03 '18 at 19:44

5 Answers5

11

Player $P_4$ shares their semi-final group with three other players out of the remaining 15; they advance to the semi-final if and only if none of those three players are $P_1, P_2, P_3$. This means the probability of them advancing is $$ \frac{\binom{12}{3}}{\binom{15}{3}} = \frac{44}{91} \approx 0.48. $$

Mees de Vries
  • 26,947
  • 1
    The problem specifies that the teams are re-randomized after each round. Your calculation appears to assume that they randomized initially but thereafter follow the usual elimination rules. – lulu Jul 03 '18 at 12:47
  • 3
    @lulu, why? We can name the different groups how we want. What I refer to as $P_4$'s semi-final group is: the team $P_a$ that $P_4$ plays initially, the team $P_b$ that the winner of $P_a, P_4$ plays (whichever it is) and the team $P_c$ that lost to $P_b$. Even if it is not known in advance who $a, b, c$ are, the set ${a, b, c}$ is still uniformly distributed over all 3-element subsets of the remaining 15 players because of all the available symmetry. – Mees de Vries Jul 03 '18 at 12:59
  • @lulu, maybe I misunderstand what your comment means, given that quasi deleted their answer... I interpret OP's "paired at random" to mean that it is not fixed in advance who the winner of $P_a, P_4$ plays out of the 7 other remaining teams. However, because of symmetry it does not matter whether or not we fix this in advance. – Mees de Vries Jul 03 '18 at 13:05
  • There is no notion of a "semi-final group" here. Every survivor is in it together and might get paired with any other. To do it along the lines you favor (which may well be optimal) you need to analyze the outcome given every possible surviving group of $8$. Perfectly possible, but it looks tedious. – lulu Jul 03 '18 at 13:12
  • @lulu, Well, yes, but you get paired with one of them, and because the remaining 7 have no distinguishing features it doesn't matter which one it is, so you might as well "fix it in advance". If you draw the bracket after the contest is done, there will be a semi-final group for $P_4$ -- just because you didn't know what the drawing was in advance doesn't matter. – Mees de Vries Jul 03 '18 at 13:16
  • The distinguishing feature of the remaining $7$ is "how many teams better than $4$ are there?" Obviously $1$ survives. But it's possible that zero, one or both of $2,3$ also survives. – lulu Jul 03 '18 at 13:17
  • Let us continue this discussion in chat. – Mees de Vries Jul 03 '18 at 13:18
6

$P_4$ will reach the semifinal if and only if none of $P_1,P_2,P_3$ is in the same quarter of the final draw as $P_4$.

It follows that the probability that $P_4$ reaches the semifinal is $${\small{\frac{\binom{12}{3}}{\binom{15}{3}}}}={\small{\frac{44}{91}}}$$ $$ \overline{ \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\;\;\; }$$ The above solution assumes the distribution of the final draw, assuming random repairings, is the same as the distribution of a random draw, with no repairings. That seemed intuitively clear (by symmetry), but based on lulu's comment, I began to worry about whether the random repairings were perhaps relevant, hence I tried a different approach, as shown below, which explicitly assumes random repairings.

With some corrections applied, based as on comments by Henry and Mees de Vries, here is a revised version of that approach . . .

The probability that $P_4$ gets to round two is ${\large{\frac{12}{15}}}={\large{\frac{4}{5}}}$, since in round one, $P_4$ has to avoid playing any of $P_1,P_2,P_3$.

Consider two cases . . .

Case $(1)$:$\;$In the first round, none of $P_1,P_2,P_3$ plays $P_4$, and two of $P_1,P_2,P_3$ play each other.

The probability that this case occurs is $$ \left({\small{\frac{4}{5}}}\right)\left({\small{\frac{3}{13}}}\right) = {\small{\frac{12}{65}}} $$ Given that this case occurs, the probability that $P_4$ wins the next match is ${\large{\frac{5}{7}}}$, since in round two, $P_4$ needs to avoid playing any of the two remaining stronger players.

Case $(2)$:$\;$In the first round, none of $P_1,P_2,P_3$ plays $P_4$, and no two of $P_1,P_2,P_3$ play each other.

The probability that this case occurs is $$ \left({\small{\frac{4}{5}}}\right)\left({\small{\frac{10}{13}}}\right) = {\small{\frac{8}{13}}} $$ Given that this case occurs, the probability that $P_4$ wins the next match is ${\large{\frac{4}{7}}}$, since in round two, $P_4$ needs to avoid playing any of $P_1,P_2,P_3$.

Summing the results for the two cases, it follows that the probability that $P_4$ reaches the semifinal is $$ \left({\small{\frac{12}{65}}}\right)\left({\small{\frac{5}{7}}}\right) + \left({\small{\frac{8}{13}}}\right)\left({\small{\frac{4}{7}}}\right) = {\small{\frac{44}{91}}} $$ Note:$\;$The two approaches yield the same result, as I initially expected, but wasn't sure of.

quasi
  • 58,772
  • Is this correct? It would be correct if the initial groups were established randomly, but thereafter follow the usual elimination rules. But if the initial rounds were random, and thereafter were scrambled again, it feels wrong. No? – lulu Jul 03 '18 at 12:46
  • Ah, I didn't see that. – quasi Jul 03 '18 at 12:46
  • Thanks @lulu for alerting me to the key issue! I think my revised answer correctly deals with it. – quasi Jul 03 '18 at 13:41
  • 1
    I think your original answer was correct – Henry Jul 03 '18 at 13:55
  • It is unclear to me where your 3/14 and 11/14 came from. – Mees de Vries Jul 03 '18 at 13:58
  • Nor why you use $\frac{6}{7}$ in the first case rather than $\frac57$ – Henry Jul 03 '18 at 14:02
  • Should have been $5/7$, now corrected. – quasi Jul 03 '18 at 14:08
  • @Mees de Vries: $3/14$ is the probability that two of $P_1,P_2,P_3$ play each other, given that none of them plays $P_4$. – quasi Jul 03 '18 at 14:09
  • I understand what the number stands for, but not how you arrive at its value. – Mees de Vries Jul 03 '18 at 14:10
  • Given that none of $P_1,P_2,P_3$ play $P_4$, the probability that $P_1$ plays $P_2$ is $1/14$, no? – quasi Jul 03 '18 at 14:12
  • No, it is 1/13; with your givens, there are three players who cannot be playing $P_1$, namely $P_1$ themselves, $P_4$, and whoever is playing $P_4$. – Mees de Vries Jul 03 '18 at 14:13
  • In particular, making the substitution of 13 for 14 gets you the same analysis as Christian Blatter below, and in particular the same answer as both your previous answer and my current one, which I stand by. – Mees de Vries Jul 03 '18 at 14:21
  • Yes, of course, my mistake. It should be $3/13$ and $10/13$, not $3/14$ and $11/14$. – quasi Jul 03 '18 at 14:47
  • Sorry, I think I confused matters. Your original answer (and method) were correct. – lulu Jul 03 '18 at 15:19
  • @lulu: Nevertheless, it was a reasonable worry, and as you can see, I took it seriously! By working through an approach which explicitly assumes random repairings, it confirms that random repairings don't matter. – quasi Jul 03 '18 at 15:27
  • 1
    full disclosure: my intuition is still unhappy about it. I wrote a simulator which (unsurprisingly) confirmed the results. After all these years, it's good (or at least necessary) to know that intuition isn't always on your side. – lulu Jul 03 '18 at 15:32
  • @quasi: Do you mind if I insert a horizontal separator line below your original answer? :-) I upvoted it because it was nice and concise and elegant, and now it's turned into a page of casework. I appreciate that you invested the time to dispel the worries that you felt were reasonable, but I think there'd be value in making it more graphically visible that the first few lines are enough to solve the problem. – joriki Jul 03 '18 at 16:29
  • 1
    @joriki: Sure, no problem. – quasi Jul 03 '18 at 16:38
6

In the first round $P_4$ plays with equal probability against any other team. The probability that $P_4$ wins this round is therefore given by ${12\over15}$. We now condition on this event, i.e., that in the first round $P_4$ has played against a $P_k$ with $k>4$.

In the second round there are $7$ adversaries left for $P_4$, all of them equiprobable. We have now have to see how many of them are better than $P_4$. This depends on whether in the first round there was a match among $1$–$3$. Denote the probability for this to have happened by $p$. Given that $P_4$ in the first round has not played against one of $1$–$3$ we obtain $$p={2\over13}+{11\over13}\cdot{1\over11}={3\over13}\ .\tag{*}$$ In the case covered by $p$ two of the adversaries of $P_4$ are better than $P_4$, in the case covered by $1-p$ there are three of them. It follows that the overall probability $p_*$ that $P_4$ wins in both rounds is given by $$p_*={4\over5}\bigl(p\cdot{5\over7}+(1-p){4\over7}\bigr)={44\over91}=0.484\ .$$ $$$$ $(^*)$ The probability that $1$ plays against $2$ or $3$ is ${2\over13}$. If $1$ plays against a $P_k$ with $k>4$ the probability that $2$ plays against $3$ is ${1\over11}$.

Christian Blatter
  • 226,825
2

Pr (Player $P_4$ wins the Round of 16)= Pr (Player $P_4$ is not tied with players 1,2, or 3 in the first round)= $$\frac{\binom{12}{1}}{\binom{15}{1}}=\frac{12}{15}$$ Player $P_4$ will win the quarter finals only if he is not tied with players 1,2 or 3 in the quarters. The possible cases for Players $P_1$,$P_2$,$P_3$ are:

  1. $W$: Players $P_1$ and $P_3$ proceed to the quarterfinals. $P_2$ gets tied with $P_1$ in the round of 16 and is eliminated.

  2. $X$: Players $P_1$ and $P_2$ proceed to the quarterfinals. $P_3$ gets tied with $P_1$ in the round of 16 and is eliminated.

  3. $Y$: Players $P_1$ and $P_2$ proceed to the quarterfinals. $P_3$ gets tied with $P_2$ in the round of 16 and is eliminated.

  4. $Z$: All three players proceed to the quarterfinals.

Player $P_1$ will always proceed to the quarterfinals.

Let $A$ denote the event that player $P_4$ wins the quarterfinal.

Using the law of total (conditional) probability, $$Pr (A)= Pr(A/W).Pr(W)+Pr(A/X).Pr(X)+Pr(A/Y).Pr(Y)+Pr(A/Y)+Pr(A/Z).Pr(Z)$$

$$=\frac{5}{7}\frac{1}{15}+\frac{5}{7}\frac{1}{15}+\frac{5}{7}\frac{1}{15}+\frac{4}{7}\left(1-\frac{3}{15}\right)$$

$$=\frac{1}{7}+\frac{48}{105}=\frac{63}{105}$$

Pr (Player $P_4$ plays semi final)= Pr (Player $P_4$ wins the Round of 16)Pr ($A$)

$$=\frac{12}{15}\frac{63}{105}=\frac{12}{25}=0.48$$

Saurav Goyal
  • 125
1

First Round = 16 men. Second Round = $\frac{16}{2} = 8 $ men. 3rd Round or Semi Final = $\frac{8}{2} = 4 $ men. Therefore, $P{_{4}}$ must defeat $3$ men to reach the Semi Final. Those 3 men must be from $P{_{5}}P{_{6}}P{_{7}}P{_{8}}P{_{9}}P{_{10}}P{_{11}}P{_{12}}P{_{13}}P{_{14}}P{_{15}}P{_{16}} $ = 12 men in total. This can be done in $\binom{12}{3}$ ways.Let us call this a Narrow view. In Broad view, 3 opponents can be selected in $\binom{15}{3}$ ways.Then $\frac{Narrow View}{Broad View}$ = $\frac{\binom{12}{3}}{\binom{15}{3}}$ = $\frac{220}{455}$ = $0.48$

Soudipta Dutta
  • 201