A probability problem involving a tournament

Question

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 ?

Answer 1

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}.$$

Answer 2

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