1
$\begingroup$

In a knockout format tournament of $2^n$ players, assume that the bracketing is chosen randomly. That is, the bottom row of the usual binary tree pairing diagram is selected as a permutation of the player numbers $1\ldots 2^n$ and every permutation has probability $\frac1{n!}$.

Assume that the player ranking is absolutely perfect, that is, if players numbered $a$ and $b$ where $a<b$ play, then $a$ will always win.

For a knockout tournament of $2^n$ players, what is the probability $P_n(a,b)$ that players $a$ and $b$ will play each other at some point?

For example, when $n=2$, $$ P_2(a,b) = \begin {array}{cc|cccc} &b&1&2&3&4\\a& & \\ \hline 1&&-&1&\frac23&\frac13\\ 2&&1&-&\frac13&\frac13\\ 3&&\frac23&\frac13&-&\frac13\\ 4&&\frac13&\frac13&\frac13&-\\ \end{array} $$

Preferably, the answer would be a closed form expression for $P_n(a,b)$ but it is likely the best one can do is some asymptotic formula when $n$ is large.

It is easy to see that for all $n$, $$ P_n(1,2) = 1\\ a < n \implies P_n(a,n) = \frac1{2^n-1} $$

Very similar questions include

Probability :Knock Out Tournament Of Ranked Players

which asks for the probability that players $1$ and $2$ will meet in the final match, and

The probability of meeting in a tournament

which could have been interpreted as asking what the present question is asking, but was interpreted by both answerers as the much simpler question of finding the probability that any two players will meet iven that their rankings are chosen randomly.


An answer to The probability of meeting in a tournament, version 2: fixed ranking gives a correct expression for $P_n(i,j)$ in the form of a sum over fractions involving binomial coefficients. That is not a closed form, and it seems very unlikely that a closed form will be found in general.

The present question is looking for either closed forms for some special cases, asymptotic growth rates for large $n$, or relationships that start to hold for large $n$.

As one example: For $2^{n-1} \leq j \leq 2^n$, the fractional difference between the chances of meeting player 1 and player 2 scales as follows $$ \frac{P_n(1,j)-P_n(2,j)}{P_n(1,j)} \approx 2 \frac{P_{n+1}(1,2j)-P_{n+1}(2,2j-1)}{P_{n+1}(1,2j)} $$ and this relationship holds to one part in 30,000 or better already for $n=8$.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.