The Probability of Two Contestants Meeting (Ross)

Question

This problem from Ross has been giving me grief, and none of the resources I’ve found have been helpful in elucidating where I’ve gone astray.

$2^n$ players are paired off at random in a contest where each contestant is $50\%$ likely to win. The $2^{n-1}$ winners are paired off again randomly, and so on, until a single winner remains. Consider two contestants A and B, and events $A_i, i = 1, 2, …, n$, and $E$, defined by

$A_i$ : A plays in exactly i contests.

$E$ : A and B ever play each other during the course of the contest. (Not never!)

What is $P(A_i)$? And what is $P(E)$?

$P(A_i)$ is straightforward; $P(A_i) = (1/2)^i$ for $i=1,2,…,n-1$ and $P(A_n) = (1/2)^{n-1}$.

As for $P(E)$, we can condition on the $A_i$ as they partition the space, but the trouble comes with calculating $P(E|A_i)$. $P(E|A_1) = \frac{1}{2^n -1}$. $P(E | A_2)$ to me seems to be $\frac{1}{2^n -1} + \frac{1}{2^n -2} \frac{1}{2}$, as A can either meet B in round 1, or in round 2, if B wins in round 1. The formula for $P(E)$ gets messy in this case, and I’m further dissuaded from this answer by the hint that Ross provides, which is the formula

$\sum_{i=1}^{n-1}ix^{i-1} = \frac{1-nx^{n-1} + (n-1)x^n}{(1-x)^2}$

Which suggests to me the possibility that $P(E|A_i) = \frac{i}{2^n -1}$, which I could reason as A plays $i$ opponents, all of which are equally likely. But this does not arrive at the proper solution of $ P(E) = \frac{1}{2^{n-1}}$ either. What am I missing in my understanding of $P(E | A_i)$?

Answer 1

It seems easier to compute $\Pr[E]$ unconditionally. There are $2^n-1$ total games played, out of $\binom{2^n}{2} = 2^{n-1}(2^n-1)$ possible games; by symmetry, each possible game has a $\frac1{2^{n-1}}$ chance of occurring.

For what it's worth, though, $\Pr[E \mid A_i] = \frac{i}{2^n-1}$ is correct, by exactly the argument mentioned (each of the $i$ opponents of A has a $\frac1{2^n-1}$ chance of being B, and these are disjoint events). When we combine these events, we get \begin{align} \Pr[E] &= \sum_{i=1}^n \Pr[E\mid A_i] \Pr[A_i] \\ &= \frac{n}{2^n-1} \cdot \frac1{2^{n-1}} + \sum_{i=1}^{n-1} \frac{i}{2^n-1} \cdot \frac1{2^i} \\ &= \frac1{2^n-1} \left(\frac{n}{2^{n-1}} + \sum_{i=1}^{n-1} \frac{i}{2^i}\right) \\ &= \frac1{2^n-1} \left(\frac{n}{2^{n-1}} + \frac{2^n-n-1}{2^{n-1}}\right) \\ &= \frac1{2^n-1} \left(\frac{2^n-1}{2^{n-1}}\right) \\ &= \frac1{2^{n-1}}. \end{align}