# A probability problem involving a tournament

In a knockout tennis tournament of $$2^n$$ contestants, the players are paired and play a match. The losers depart, the remaining $$2^{n-1}$$ players are paired, and they play a match. This continues for $$n$$ rounds, after which a single player remains unbeaten and is declared the winner. Suppose that the contestants are numbered $$1$$ through $$2^n$$, and that whenever two players contest a match, the lower numbered one wins with probability $$p$$. Also, suppose that the pairings of the remaining players are always done at random so that all possible for that round are equally likely. What is the probability that player 2 wins the tournament ?

Hint : Imagine that the random pairings are done in advance of the tournament. That is, the first-round pairings are randomly determined; the $$2^{n-1}$$ first-round pairs are then themselves randomly paired, with the winners of each pair to play in round 2; these $$2^{n-2}$$ groupings (of four players each) are then randomly paired, with the winners of each grouping to play in round $$3$$, and so on. Say that players $$i$$ and $$j$$ are scheduled to meet in round $$k$$ if, provided they both win their first $$k-1$$ matches, they will meet in round $$k$$. Now condition on the round in which players $$1$$ and $$2$$ are scheduled to meet.

Taking the hint I have found the probability as :

$$\sum _{k=1}^{n} p^{2k-2} \prod_{i=1}^{k-1}\Big(1-\frac{1}{2^{n-i+1}-1}\Big)\frac{1}{2^{n-k+1}-1}(1-p)p^{n-k} + \bigg(1-\sum _{k=1}^{n} p^{2k-2} \prod_{i=1}^{k-1}\Big(1-\frac{1}{2^{n-i+1}-1}\Big)\bigg)p^n$$

But, I could not understand why "Imagine that the random pairings are done in advance of the tournament" is required here ?

Why the hint is required depends on the way you derived your result, not just on the result you post.

However, here's an alternative solution. Denote $$p_{k,n}:=P(\text{Player #k wins an n round tournament}).$$

As a preliminary step, we should eliminate the cases $p=\frac12$ as then everything is symmetric, i.e. the probability that player #2 (or anybody else) wins, is exactly $\frac1n$. Similarly, if $p=1$, then #1 wins the tournament a.s., hence $p_{2,n}=0$. And if $p=0$, then the max player will win a.s., i.e. then $p_{2,n}=0$ except that $p_{2,1}=1$. After these remarks, we don't get into trouble if we wish to divide by $p$, or $1-p$ or $1-2p$ below.

Next, let us compute the probability that player $1$ wins the tournament. To do so, he must survive the first round and then win a tournament of $2^{n-1}$ players among which he (after renumbering the players to fill the gaps without changing relative order) is still number one. Then we have $$p_{1,n}=\begin{cases}1&\text{if }n=0,\\ p\cdot p_{1,n-1}&\text{if }n>0,\end{cases}$$ In other words $$p_{1,n}=p^n.$$ Now what about player $2$? To win, he must survive the first round; that is he

• either plays player #1 (with probaility $\frac1{2^n-1}$) and wins with probaility $1-p$, after which he is automatically the #1 of the remaining players
• or plays somebody else (with $1-\frac1{2^n-1}$) and wins with probability $p$. Player #1 also wins with porbability $p$, and then player #2 is still #2 of the remaining players
• or as before, but player #1 loses his match, so our #2 becomes #1 of the survivors.

That is, for $n>0$ (otherwise, a player #2 doesn't even participate) we have \begin{align}p_{2,n}&=\frac1{2^n-1}\cdot(1-p)\cdot p_{1,n-1}+\left(1-\frac1{2^n-1}\right)\cdot\left( p^2\cdot p_{2,n-1}+ p\cdot (1-p)\cdot p_{1,n-1}\right) \\&=\frac{p^{n-1}(1-p)}{2^{n}-1} +\frac{(2^{n}-2)(1-p)p^n}{2^{n}-1}+\frac{(2^{n}-2)p^2}{2^{n}-1}\cdot p_{2,n-1}. \end{align} (Note that this immediately gives $p_{2,1}=1-p$). If we substitue $p_{2,n}=\frac{p^n}{2^n-1}(a_n+c)$, we obtain $$a_n +c= \frac{1-p}{p}+(2^n-2)(1-p)+2p(a_{n-1}+c),$$ hence by chosing $c=\frac{1-p}{p(1-2p)}$ $$a_n = (2^n-2)(1-p)+2pa_{n-1}.$$ Note that $p_{2,1}=1-p$ implies $a_1=\frac{2(1-p)}{2p-1}$, so we can extend this to $a_0=\frac{1-p}{(2p-1)p}$. Substitute again, $a_n=2^np^nb_n$, to find $$b_n = \frac{(2^n-2)(1-p)}{2^np^n}+b_{n-1}= (1-2^{1-n})\frac{(1-p)}{p^n}+b_{n-1}.$$ Hence \begin{align} b_n &= b_0+\sum_{k=1}^n(1-2^{1-k})\frac{(1-p)}{p^k}\\&=b_0 + (1-p)\sum_{k=1}^np^{-k}-2(1-p)\sum_{k=1}^n(2p)^{-k}\\& = b_0 + (p^{-n}-1) -2(1-p) \frac{(2p)^{-n}-1}{1-2p}\\ &= \frac1{p^{n}}-\frac{2(1-p)}{(1-2p)(2p)^n} +\left(b_0-1+\frac{2(1-p)}{1-2p}\right) \\&=\frac1{p^{n}}-\frac{2(1-p)}{(1-2p)(2p)^n}-\frac1p\end{align} Therefore, $$a_n = 2^n-\frac{2(1-p)}{1-2p}-2^np^{n-1}$$ and ultimately, $$p_{2,n} = \left(2^n-2^np^{n-1}+\frac{1-p}{p}\right)\frac{p^n}{2^n-1}.$$

• I derived this while writing it, so there may be some shortcuts or simplifications available ... Commented May 1, 2013 at 11:42
• I thought you would derive $p_{k,n}$ for arbitrary $k$.
– Hans
Commented May 21, 2019 at 22:47
• Maybe it's a silly question. If the condition of winning the match is : If Pi vs Pj and i < j , then Pi will win the match. Then it's obvious that P1 shall win the tournament. Will the probability of others be same and won't it be equal to zero ?? Commented Oct 28, 2021 at 10:50

@Hagen von Eitzen has derived the formula typing it in directly,
a feat I can't even imagine !

However, being a tennis buff, I thought I'd try my hand at it.

Briefly, the approach I adopted was

P(2 wins)

• If #2 goes through to win w/o meeting #1, $$Pr = p^n$$

• Pr of meeting #1 in round 1 is $$\frac{2^0}{2n-1}$$, in round 2 it is $$\frac{2^1}{2n-1}$$, in round 3, $$\frac{2^3}{2n-1}$$ etc remembering that #1 should have reached that round for them to meet

• In each round, #2 wins with $$Pr= (1-p)$$ if meeting #1, else with Pr= p

Proceeding thus, the form my formula took was

P(2 wins) = $$\dfrac{p^{n-1}\left[1+ (2^n-1)p - 2^np^n\right]}{2^n-1}$$

This is just old wine in new bottle, but my curiosity was aroused when I "deciphered" the formula for $$n=4$$

$$Pr = \dfrac{p^3(1 +15p - 16p^4)}{15}\;\;\; or\;\;\; \dfrac{p^3[(1-p^4) +15p(1-p^3)]}{15}$$

Do they hint that it might be possible to directly arrive at the formula through reasoning, and if so, how ?

After some effort, I have come to the reluctant conclusion that it doesn't appear to be feasible through logic alone, but I have been able to minimize the Algebra.

Probability that #1 & #2 meet $$= 1 + 2p^2 + 4p^4 + 8p^6= \frac{16p^4-1}{2p-1}$$

Difference in probability of win due to meeting $$= p - (1-p) = (2p-1)$$ so Pr she meets and wins = $$(16p^4-1)$$

There are $$15$$ places from which these results flow, thus

Pr of win $$= p^3(p - \frac{(16p^4-1)}{15})$$

$$= \frac{p^3}{15}(1+15p-16p^4)$$

• @Hagen von Eitzen: I vainly tried to get the pattern that emerges through logic alone. Do you have any ideas ? Commented Jun 19, 2021 at 7:24