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 ?
Best Answer
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
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}.$$