In a tournament of $2^n$ people, what is the probability of player $i$ and player $j$ meet at $k$-th round In a knock-out tournament of $2^n$ people, where if $i < j$, player $i$ is better than player $j$  and will beat her in any parts of the tournament. What is the probability of player $i$ and player $j$ will meet at $k$-th round for any $1 \leq i \leq j \leq 2^n$, $1 \leq k \leq n$ (assuming the positions of player at the start of tournament are all random)?
This problem is inspired by the case $i=1,j=2,k=n$, where the probability is $\frac{2^{n-1}}{2^n-1}$, determined by the probability that player $2$ is at the different half of the player $1$ during the start. Similarly, player 3 will meet with player $1$ at the final tournament by probability  $\frac{2^{n-1}-1}{2^n-1}\frac{2^{n-1}}{2^n-2}$ (player $2$ meet player $1$ first). And similarly for all other players by applying same logic.
I'm curious about the general case that player $i$ and player $j$ will meet at $k$-th round and am wondering if my rationale below is correct. We know that the situation happens only when player $i$ is the best player among the $2^k$ nearest player and player $j$ is the best in her $2^{k-1}$ nearest player. By combinatorics, it's equivalent to that fixed $i, j$, among the $2^k-2$ numbers that are nearest to player $i$ during the contest, the random $2^{k-1}-1$ numbers are all greater than $j$ and the remaining $2^{k-1}-1$ are both greater than $i$. So it's $$P(i,j,k) = \frac{\binom{2^n-j}{2^{k-1}-1}\binom{2^n-i - 2^{k-1}-1}{2^{k-1}-1}}{\binom{2^n}{2^{k}-2}} \frac{1}{2^{n-k+1}}$$
Where the $\frac{1}{2^{n-k+1}}$ is the additional probability that $i, j$ are in the two nearest $2^{k-1}$ groups. Is this correct?
 A: You are mostly correct. I believe the correct probability is
$$
\frac{\binom{2^n-j}{2^{k-1}-1}\binom{2^n-2^{k-1}-i}{2^{k-1}-1}}
{\binom{2^n-2}{2^{k}-2}\binom{2^k-2}{2^{k-1}-1}}
\cdot \frac{2^{k-1}}{2^n-1}
$$
Note that my answer agrees with the known $2^{n-1}/(2^n-1)$ when $i=1,j=2,k=n,$ while your answer does not.
Your mistakes:

*

*You had $\binom{2^n-2^{k-1}-i-1}{2^{k-1}-1}$ for the number of ways to choose the $2^{k-1}$ people that $i$ plays against before facing $j$. The only people that need to be excluded are the $i-1$ people below $i$, $i$ themself, and the $2^{k-1}$ people in the bracket with $j$ (including $j$). Therefore, the pool being chosen from has size $2^n-2^{k-1}-i$; you were off by one.


*You had $\binom{2^n-2}{2^{k}-2}$ in the denominator, but this treats all the $2^{k}-2$ people who play against $i$ or $j$ as the same. We need to distinguish whether they play against $i$ or $j$, which is accounted by the $\binom{2^k-2}{2^{k-1}-1}$ in my answer.


*You had $1/2^{n-k+1}$ for the probability $j$ is in the seed that would play $i$ at the $k^\text{th}$ level, which does not agree with the $k=n$ case you already saw the solution for. There are $2^{k-1}$ spots where $j$ could go, and $2^n-1$ spots total (everything except for where $i$ is), so $2^{k-1}/(2^n-1)$ is correct.
