The probability of meeting in a tournament, version 2: fixed ranking

This is a variation on this question

$$2^n, n\in\mathbf N$$ tennis players compete in a tournament. In the first round, they partition into a set of $$2^{n-1}$$ disjoint pairs. The two players in each pair compete against each other. The $$2^{n-1}$$ winners form a set of $$2^{n-2}$$ disjoint pairs and compete in the next round, and so on. This competition lasts for $$n$$ rounds. The partition in each round is uniformly random. The players are strictly ranked and the higher ranked player always beats the lower one. Given a particular ranking, for two chosen players of $$i$$'th and $$j$$'th ranking, what is the probability that they will compete against each other in a pair?

• Presumably, you meant the $2^{n - 1}$ winners form a set of $2^{n - 2}$ disjoint pairs. – N. F. Taussig May 21 at 1:01
• @N.F.Taussig: Yes, you are right. I have corrected it. Thank you. – Hans May 21 at 1:05
• So no two players have the same rank? – Arief Anbiya May 21 at 10:22
• @AriefAnbiya: Yes. They "are strictly ranked" as stated in the question. – Hans May 23 at 2:35

Let $$i\lt j$$, and lower numbers are better players.
They meet in round $$k$$ if $$j$$ is the top of his branch of $$2^{k-1}$$ players, $$i$$ is top of the neighbouring branch of $$2^{k-1}$$ players, so they get paired up . The odds of this happening is

$${2^n-j\choose 2^{k-1}-1}{2^n-i-2^{k-1}\choose 2^{k-1}-1}\over{ {2^n-1\choose 2^{k-1}-1}{2^n-2^{k-1}\choose 2^{k-1}}}$$

Then sum that from $$k=1$$ to $$n$$.

As a sanity check, here are the probabilities for a tournament with eight players.

$$\frac{1}{105}\left[\begin{array}{cccccccc} 0 & 105 & 70 & 47 & 33 & 25 & 20 & 15\\ 105 & 0 & 35 & 31 & 27 & 23 & 19 & 15\\ 70 & 35 & 0 & 27 & 24 & 21 & 18 & 15\\ 47 & 31 & 27 & 0 & 21 & 19 & 17 & 15\\ 33 & 27 & 24 & 21 & 0 & 17 & 16 & 15\\ 25 & 23 & 21 & 19 & 17 & 0 & 15 & 15\\ 20 & 19 & 18 & 17 & 16 & 15 & 0 & 15\\ 15 & 15 & 15 & 15 & 15 & 15 & 15 & 0 \end{array}\right]$$

• Insightful. The answer merits more detailed explication though. I understand that the numerator equals to the number of combinations of two disjoint branches both of $2^{k-1}$ players the top player of one of which is $i$ and the other is $j$. I do not fathom the denominator. The first factor seems to be the number of sets of players of the branch containing either $i$ or $j$. The second factor seems to be the number of set of players of its neighboring branch, no matter it contains player $i$ or $j$. But I do not see what purpose the denominator serves. – Hans May 22 at 9:41
• Yes. Both numerator and denominator concern $j$'s group $A$ and its neighbouring group $B$. For the numerator, $A$ is filled with $j$ and players below $j$, then $B$ is filled with $i$ and other players below $i$. For the denominator, $A$ is filled with $j$ and anyone, then $B$ is filled with anyone else. – Empy2 May 22 at 10:21
• I understood the numerator immediately but had doubts about the denominator. I am now convinced. However, it has many intricacies, particularly for the denominator, questions like why we only need to focus on the branch of either one of $j$ or $i$ but not both and ensure there are no over or under counting, why the fractions can be added up, etc., etc.. It would be great and appreciated for comprehension and posterity if you could write a detailed proof of your answer. I will upvote and accept it afterwards. Thank you, Empy27. – Hans May 22 at 19:05

Interesting problem. Just for a warm up first:

Let $$n = 4$$, then the players are ranked from lowest to highest as $$\{x_{1}, x_{2}, x_{3}, x_{4}\}$$. For the 1st round, there will be 2 disjoint pairs. Pattern: $$p_{1}, p_{2}$$ with $$p_{i}$$ is pair $$i$$. So the number of disjoint pairs are: $$\frac{\binom{4}{2} \binom{2}{2}}{2} = 3$$ Division by 2 because for example: $$(x_{1}, x_{2}), (x_{3},x_{4})$$ is same as $$(x_{3}, x_{4}), (x_{1},x_{2})$$. These are: $$(x_{1}, x_{2}), (x_{3}, x_{4}) \rightarrow (x_{2}, x_{4})$$ $$(x_{1}, x_{3}), (x_{2}, x_{4}) \rightarrow (x_{3}, x_{4})$$ $$(x_{1}, x_{4}), (x_{2}, x_{3}) \rightarrow (x_{3}, x_{4})$$

Righthand side is the final round.

Now, what is the probability that $$(x_{1}, x_{2})$$ will appear in the draw? it is $$1/3$$, probability of $$(x_{1},x_{i>1})$$ will always be $$1/3$$.

Probability $$(x_{2}, x_{3})$$ is 1/3. Probability $$(x_{2},x_{4})$$ is 2/3.

Probability $$(x_{3}, x_{4})$$ is 1..!