1
$\begingroup$

I have read this question in the forum:

"In a tennis tournement of $128$ players, elimination system, what is the probability that two twins will meet at some point (assuming all players have equal ability)?

I assume there are only $1$ pair of twins out of the $128$ players. While I am convinced that the answer is $\frac{1}{2^{n-1}}$, as posted by a member of the forum, I have a thought whether the answer will be different in case in every round, all the winners in the previous round are drawn randomly again to decide the opponent. For example, consider the quarter-final, if $A$ vs $B$, $C$ vs $D$, $E$ vs $F$ and $G$ vs $H$, $A$ (a winner in the quarter-final) may play any other except $B$ in the semi-final, while in the traditional system, $A$ knows he/she may only play either $C$ or $D$ depending on who wins the quarter-final.

Here is my work:

  • In any round with $p$ players, if we allow all players to play that round without considering he/she has won or lost before, then the probability that any given player will meet another specific player at round $i$ will be $$\frac{1}{p-1}$$

    In Round $i$ ($i = 1, 2, \dots, \log_2 n$) of the tournament, there will be $n/2^{i-1}$ players, paired for $n/2^i$ games.

    In reality, to enter Round $i$, both players must have won $i-1$ games before. Hence the probability that any given player will meet another specific player at round $i$ will be $$\frac{1}{2^{i-1}} \times \frac{1}{2^{i-1}} \times \frac{1}{\frac{n}{2^{i-1}}-1}$$

    Hence the probability that any given player will meet his/her twin (if he/she does have a twin entering the tournament) is:

    $$\sum\limits_{i=1}^{\log_2 n} [(\frac{1}{2^{i-1}})^2 \times \frac{1}{\frac{n}{2^{i-1}}-1}]$$

So assuming $n = 128$, $\log_2 n = 7$. I get the answer as $0.0160 = \frac{1}{62.3917}$, which is different from the $\frac{1}{2^{n-1}} = \frac{1}{64}$, the probability for the twin to meet in a traditional elimination system.

On the other hand, it seems that by appealing to symmetry (i.e. an answer provided for the original question), the argument still holds. So the answer should still be $\frac{1}{64}$, regardless of whether the players are drawn again in every round. Here is the answer as quoted in the original question:

Assuming everyone's of equal skill and there's uniformly random initial seeding, we can appeal to symmetry:

Suppose there are $2^n$ players.

There are $2^n(2^{n−1})/2$ pairs of players.

There are $2^n-1$ matches.

Therefore the probability they meet is $\frac{1}{2^{n−1}}$

I get really confused. Which answer is correct?

$\endgroup$
2
+50
$\begingroup$

An alternate perspective will identify which one is right.

Let's consider it recursively. Let $R_n$ be the probability that they both make it to round $n$, and $P_n$ be the probability that they play each other in round $n$. Now, we have $$ P_1 = \frac1{2^m-1}\qquad R_1 = 1 $$ where $m$ is the total number of rounds (and thus, $2^m$ is the number of competitors). Now if they play each other in round $n$, they can't both make it into round $n+1$. If they don't play each other, their chance of both making it into round $n+1$ is $1/4$. And if they both make it into round $n$, their chance of playing each other is $1/(p-1)$ where $p$ is the number of people remaining. As such, we have $$ R_{n+1}=\frac{R_n-P_n}4\\ P_{n+1}=\frac{R_{n+1}}{2^{m-n}-1} $$ We care about $\sum P_n$. Noting that $R_n=(2^{m-n+1}-1)P_n$, we can write $$ (2^{m-n}-1)P_{n+1}=\frac{(2^{m-n}-1)P_n}2 $$ Now, dividing out by $2^{m-n}-1$, we have $$ P_{n+1}=\frac{P_n}2 $$ which has the solution $$ P_n=2^{1-n}P_1 $$ Now, $$ \sum_{n=1}^m P_n = 2P_1\sum_{n=1}^m 2^{-n} = 2P_1\frac{1-2^{-m}}{2^{-m}} = P_1\frac{2^m-1}{2^m} $$ Substituting in our value for $P_1$, we have $$ \sum_{n=1}^m P_n =\frac{2}{2^m} = \frac1{2^{m-1}} $$ And thus, the "appeal to symmetry" approach is the correct one.

The flaw, as it turns out, lies in repeated counting. Using your approach, you are failing to account for what would otherwise be repeated matches - that is, you only require that they win the first $i$ rounds, and that they then get matched with each other. But if they already played each other in a previous round, then their new match shouldn't be counted... but it is, by your approach. Let's demonstrate with a simpler version - 4 players, two rounds.

In round 1, each player could play any one of the other three. This gives the chance of playing each other as $1/3$. In round 2, using your reasoning, there's a $1/4$ chance that each of the two were knocked out, and with only two players left, if both make it there, they must play each other. This gives a total probability of $1/3+1/4=7/12$.

But that's wrong, because if they played each other in the first round, they can't play each other in the second round. Removing the repeated counting means removing the case of them playing each other in the first round and "both winning". That is, $1/3\times1/4$, which is $1/12$. Subtracting this from our answer gives $6/12=1/2$, which is exactly what we get from the other approaches.

Note that you can't just handle double-counting, because they could be matched up 3 or more times if there are more than two rounds.

The other way to think of it is that you aren't accounting for the non-independence of probabilities. The probability that they both make it through to the next round isn't $1/4$, because if they play each other, they can't both make it through. As such, if we call the probability that $A$ makes it through $1/2$, and the probability that $B$ makes it through $1/2$, the probability that they both make it through isn't actually $1/2\times1/2$, as the two events aren't completely independent.

$\endgroup$
  • $\begingroup$ Very thorough explanation, thank you. My way of tackling the question was flawed, as I thought "players met at round $n$" automatically eliminated the possibility of "they met at round $\gt n$" (and hence made the wrong conclusion that these events are mutually exclusive), so I did not account for the double-counting problem. $\endgroup$ – LaBird Mar 20 '15 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.