What is the probability that player A and B play against each other?

Question

Players with same skill take part in a competition. The probability of winning each game is 0.5. At first, we divide a group of $2^n$ people to random pairs that play against each other. Then we will do the same for $2^{n-1}$ winners and this continues until there is only one winner. What is the probability that player A and B play against each other?

I know we should calculate the sum of probabilities that two players play against each other in the first round, then for second round and etc. So how can i calculate the probability that two players play at round K?

Answer 1

• It is a knockout competition with $m=2^n$ players so $m-1$ knockouts or matches or parings are needed to produce a winner

• There are ${m \choose 2}=\frac{m(m-1)}{2}$ equally-likely possible parings of the $m$ players, so the probability any particular match involves both players A and B is $\frac{2}{m(m-1)}$, and so the expected number of the $m-1$ matches which involve both players A and B is $(m-1) \times \dfrac{2}{m(m-1)}=\dfrac{2}{m}$

• Since players A and B can only meet $0$ or $1$ times, the probability they meet is $\dfrac{2}{m} = \dfrac{1}{2^{n-1}}$

Answer 2

• $P(A , B \text{ play at round } 1) = \frac{1}{2^{n-1}}$

---

When we have $2^{n}$ people, then we have at most $\log^{2^{n}}_{2}$ rounds. For example, assume we have only $2$ players, then $P(A , B \text{ play at round } 1) = \frac{1}{2^{\log^{2}_{2}-1}} = 1$

---

• $P(A , B \text{ play at round } 2) = P(A , B \text{ did not play at round } 1 \text{ and } A , B \text{ both win at the first round}) = (1-\frac{1}{2^{n-1}})(\frac{1}{2})^{2}$

• $P(A , B \text{ play at round } 3) = P(A , B \text{ did not play at round } 1,2 \text{ and } A , B \text{ both win at the first, second rounds}) = (1-\frac{1}{2^{n-1}})(1-\frac{1}{2^{n-2}})(\frac{1}{2})^{4}$

$$...$$

• $\forall k<n: \quad P(A , B \text{ play at round } k) = (\frac{1}{2})^{2(k-1)}\times \Pi_{i=1}^{k}(1-\frac{1}{2^{n-i}})$

$$...$$

• $\bbox[5px,border:2px solid #C0A000]{P(A , B \text{ play at round } n \text{ and } n>1) = (\frac{1}{2})^{2(n-1)}\times \Pi_{i=1}^{n-1}(1-\frac{1}{2^{n-i}})}$

Answer 3

Hmm...I don't see any real difference between this and an ordinary single-elimination tournament where the seeding is set from the start. Maybe I'm missing something.

Anyway, assuming that there isn't any difference, we observe that Player A has $2^n-1$ different possible opponents in the first round. Of those, $2^{n-1}$ are in the opposite half of the draw, and both they and Player A would have to win $n-1$ games to meet; this happens with probability $\frac{1}{4^{n-1}}$. $2^{n-2}$ are in the same half, but opposite quarters, and both they and Player A would have to win $n-2$ games to meet; this happens with probability $\frac{1}{4^{n-2}}$. And so on, until we get to the $2^{n-n} = 2^0 = 1$ single player who meets Player A in the first round. Altogether, the probability of Player A and a given Player B meeting eventually is

\begin{align} \frac{1}{2^n-1} \sum_{k=1}^n 2^{n-k}\frac{1}{4^{n-k}} & = \frac{1}{2^n-1} \sum_{k=1}^n \frac{1}{2^{n-k}} \\ & = \frac{1}{2^n-1} \sum_{k=0}^{n-1} \frac{1}{2^k} \\ & = \frac{1}{2^n-1} \left(2-\frac{1}{2^{n-1}}\right) \\ & = \frac{1}{2^n-1} \times \frac{2^n-1}{2^{n-1}} \\ & = \frac{1}{2^{n-1}} \end{align}

I'll come back to edit this if I think (or someone points out) that there's a substantive difference between random reseeding and not reseeding.

---

There's also a pretty simple proof by induction: For $n = 1$ (two players), the probability is clearly $\frac{1}{2^n-1} = 1$. For $n > 1$, the probability that they meet in the first round is $\frac{1}{2^n-1}$. If they don't meet in the first round (with probability $\frac{2^n-2}{2^n-1}$), then they must both win their first games (with probability $\frac14$) to get to the next round. With reseeding, this is clearly the case of $n-1$, so with the premise that the probability of them meeting at that point is $\frac{1}{2^{n-1-1}} = \frac{1}{2^{n-2}}$, the overall probability for case $n$ is

\begin{align} \frac{1}{2^n-1}+\frac{2^n-2}{2^n-1} \times \frac14 \times \frac{1}{2^{n-2}} & = \frac{1}{2^n-1} \left(1+\frac{2^n-2}{2^n}\right) \\ & = \frac{1}{2^n-1} \times \frac{2^{n+1}-2}{2^n} \\ & = \frac{1}{2^n-1} \times \frac{2^n-1}{2^{n-1}} \\ & = \frac{1}{2^{n-1}} \end{align}