Knockout Chess: Will the Two Best Players Meet in the Final?
A single-elimination chess tournament has $2^n$ players, ranked $1, 2, \ldots, 2^n$ by strength with no two equal. Whenever two players meet, the stronger one always wins. The bracket is filled uniformly at random: in every round the surviving players are paired at random (equivalently, players are assigned to the $2^n$ bracket slots by a uniformly random permutation), the losers leave, and the tournament continues until one champion remains after $n$ rounds.
What is the probability that player 1 and player 2 (the two strongest) meet in the final?
Hints
- Player 1 reaches the final no matter what. So the question is entirely about player 2: what has to be true for player 2 to reach the final?
- Player 2 loses only to player 1. Player 2 reaches the final if and only if player 1 and player 2 are never paired before the final, i.e. they sit in opposite halves of the bracket.
- Given player 1's slot, player 2 is equally likely to be in any of the other $2^n - 1$ slots, of which $2^{n-1}$ are in the opposite half.
Worked Solution
How to Think About It: Because the stronger player always wins, player 1 is guaranteed to reach the final. Player 2 beats everyone except player 1, so player 2 reaches the final if and only if it does not run into player 1 in rounds $1$ through $n-1$. In bracket language: the two must start in opposite halves.
Quick Estimate: Roughly half the bracket is on the opposite side from player 1, so the answer should be about $1/2$, slightly larger because player 2 cannot occupy player 1's own slot. For 8 players: $4/7 \approx 0.571$.
Formal Solution:
*Step 1 -- Reduce to a seeding question.* Fix player 1's slot. The final is between the winners of the two halves of the bracket, and player 1 wins its half. Player 2 wins the other half if it is in the other half (nobody there can beat it), and is eliminated by player 1 before the final if it is in the same half. So
$$P(1 \text{ and } 2 \text{ meet in the final}) = P(2 \text{ is in the opposite half from } 1).$$
*Step 2 -- Count slots.* Given player 1's slot, player 2 is uniformly distributed over the remaining $2^n - 1$ slots, and $2^{n-1}$ of them lie in the opposite half:
$$P = \frac{2^{n-1}}{2^n - 1}.$$
*Step 3 -- Round-by-round check (random re-pairing each round).* If instead the survivors are re-paired at random in every round, condition on both players surviving to round $k$, where $2^{n-k+1}$ players remain. The chance they are not paired with each other is $1 - \frac{1}{2^{n-k+1} - 1}$. Multiplying over rounds $k = 1, \ldots, n-1$:
$$\prod_{j=2}^{n} \frac{2^{j} - 2}{2^{j} - 1} = 2^{n-1} \prod_{j=2}^{n} \frac{2^{j-1} - 1}{2^{j} - 1} = 2^{n-1} \cdot \frac{2^1 - 1}{2^n - 1} = \frac{2^{n-1}}{2^n - 1},$$
the product telescoping. Both tournament formats give the same answer.
*Sanity check.* $n = 1$: the two players are the only ones, $P = 1$. $n = 2$: $2/3$. $n = 3$: $4/7$. As $n \to \infty$, $P \to 1/2$.
Answer: $P = \dfrac{2^{\,n-1}}{2^{\,n} - 1}$ (for example $4/7$ with 8 players, $8/15$ with 16).
Intuition
With deterministic outcomes the whole tournament is decided by the seeding: player 2 can only be eliminated by player 1, so the two best meet in the final exactly when the random draw keeps them apart until then. Half the bracket is "the other side," and the answer $2^{n-1}/(2^n - 1)$ is just a hair above $1/2$ because player 2 cannot occupy player 1's own slot. The same "who can eliminate whom" reasoning shows up in reasoning about single-elimination formats, order statistics of noisy signals, and any pairwise-comparison process where one item dominates.