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 ?  
 A: 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}.$$
A: @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)$
