2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Did you try a small example to see what would have to happen for A and B to meet in the second round, or the third round, and then see how it may generalize from that? $\endgroup$ – Bram28 Oct 20 '17 at 16:17
3
$\begingroup$
  • 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}}$

$\endgroup$
  • $\begingroup$ Elegantly simple. $\endgroup$ – true blue anil Oct 21 '17 at 2:14
0
$\begingroup$
  • $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}})}$
$\endgroup$
  • $\begingroup$ I think you're missing minus ones. Assume there are only two players. Is the probability that they will play $\frac12$? Also each round you have to multiply with that stages probability that they will play. $\endgroup$ – karakfa Oct 20 '17 at 16:32
  • $\begingroup$ @karakfa, your first comment is not correct. I explain it by an example. $\endgroup$ – Hasan Heydari Oct 20 '17 at 16:42
  • $\begingroup$ yes, my mistake $2^n$ people means for two people n=1. $\endgroup$ – karakfa Oct 20 '17 at 16:48
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.