What is the probability of 2 players meeting during a random knockout tennis tournament? A tennis tournament has $n$ players. $n$ is an even number. Each round, we randomly pair two players and all players have the same ability and the winner is random. All winners go to the next round and are paired up again randomly. We repeat this process until one player left as the champion.
Say we have two players $A$ and $B$, what's the probability that $A$ meet $B$ during the entire tournament?
For the answer, I get that 1) we need $n-1$ games in total to eliminate $n-1$ players 2) there is $C^{n}_{2}$ way to match $2$ players.
What I don't understand is why the answer is $\frac{(n-1)}{C^{n}_{2}}$.
Isn't that $C^{n}_{2}$ is only for the first round when we still have $n$ players? For the second round, if $A$ and $B$ still stay in the game, but the number of the plays in the game has been reduced to $0.5n$, so $C^{0.5n}_{2}$ is probability for $A$ to meet $B$? And if any of $A$ or $B$ got knocked out, they will never meet? What I don't get is, the denominator only holds before any matches start right? once the game started and getting the n-1 games, in each round, the probability for A meet B is different, correct?
 A: (1) Since there are $n$ players, and exactly $1$ player is eliminated from each match, there need to be a total of $n-1$ matches played.
(2) Before playing any matches, there is an $1/{n\choose 2}$ chance that any two random players will meet in any one match.
Thus there is $(n-1)\frac{1}{{n\choose 2}}$ chance that any two players will meet in the tournament (since there are $n-1$ matches for them to meet in, with a probability $1/C^n_2$ in each match).
It can also be thought of as you have a $1/C^n_2$ chance of satisfying the criterion (players $A$ and $B$ meet) and you get $n-1$ chances (before any matches are played).
A: The only thing we need to remember is that there are $n-1$ matches, each one between a different pair of opponents, and the possible sequences of events are completely symmetrical: for any possible history of the tournament (who played whom in each pairing of each round), any permutation of the player's roles in that history is equally likely to have occurred. In particular, no two players are more likely to meet than any other two players.
Give the players identifying numbers from $1$ to $n$ inclusive.
For $1 \leq j < k \leq n,$ let $X_{j,k}$ be $1$ if player number $j$ ever plays player $k$ during the tournament, $0$ otherwise.
Then $X_{j,k}$ is a Bernoulli random variable.
Since each $X_{j,k}$ is a Bernoulli variable, $E(X_{j,k}) = P(X_{j,k} = 1)$.
Since no two players are more likely to meet than any other two players,
no probability $P(X_{j,k} = 1)$ is greater than any other, so no expected value is greater than any other, and therefore
$$ E(X_{1,2}) = E(X_{1,3}) = E(X_{2,3}) = \cdots = E(X_{n-1,n}). $$
There are $C_2^n$ such variables $X_{j,k}$. Their sum is
$$ Y = X_{1,2} + X_{1,3} + X_{2,3} + \cdots + X_{n-1,n} = n - 1 $$
because exactly $n - 1$ pairs must play, $X_{j,k} = 1$ for each of those pairs, and
$X_{j,k} = 0$ for every other pair.
By linearity of expectation,
\begin{multline}
E(X_{1,2}) + E(X_{1,3}) + E(X_{2,3}) + \cdots + E(X_{n-1,n}) \\
= E(X_{1,2} + X_{1,3} + X_{2,3} + \cdots + X_{n-1,n}) = n - 1
\end{multline}
since the expectation of a constant is just the constant.
But since the expected values of $E(X_{j,k})$ for each pair of players are all equal,
$$ E(X_{1,2}) + E(X_{1,3}) + E(X_{2,3}) + \cdots + E(X_{n-1,n}) = C_2^n E(X_{A,B}) $$
where $A$ and $B$ are the numbers assigned to the two players in the question.
That is,
$$ C_2^n E(X_{A,B}) = n - 1, $$
therefore
$$ P(X_{A,B} = 1) = E(X_{A,B}) = \frac{n - 1}{C_2^n} $$
And of course $P(X_{A,B} = 1)$ is the probability that $A$ and $B$ meet.
