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)$?

  • $\begingroup$ A real life example is the very popular game Splatoon, which has millions (perhaps 10s of millions) of players, and you are assigned randomly against other players in each round. $\endgroup$
    – Fattie
    Oct 1 at 13:45

1 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}


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .