Probability of team winning in a single-elimination tournament

In a tournament of football (or whatever sport you prefer), let's say we have $2^n$ teams and for all $2^{n-1}(2^n-1)$ possible matches we know the probability of one team winning against the other. The tournament is a single-elimination tournament (therefore having $n$ rounds) and the teams are to be randomly allocated for the first round. How do we go about computing the probability of team $x$ winning the tournament?

• Given that you are explicitly given the probabilities for each possible match this is possible to calculate but you will need to consider all possible arrangements. Because if it were to be that the best team plays the third best team in the first round and the second best team plays the fourth best team in the same round with the winners of these two matches playing each other in the next round the forth best team has much lower probability of winning overall than if the arrangement in the first round means they can't meet a decent team unless they get to the final. Commented Jun 3, 2014 at 15:26
• $(2^n)!$ is too many for the number of possible pairs: $2^n (2^n-1)$ or $2^{n-1} (2^n-1)$ would be better, depending on whether order matters in the pairing. For $n$ of a reasonable size, I suspect Monte Carlo modelling would give you reasonable estimates reasonably quickly. Commented Jun 3, 2014 at 15:45
• You're right about the number of possible pairs. Monte Carlo methods would give us an estimate, but is there a direct systematic approach? Something like a Markov chain perhaps... Commented Jun 3, 2014 at 15:59

For each team $i$ the probability of getting into the second round is $$P_2(i)=\frac{1}{2^n-1}\sum_{j\ne i}P_v(i,j)$$ where $P_v(i,j)$ is the probability that $i$ will defeat $j$.

Similarly, the probability that $i$ will get into the round $r+1$ is $$P_{r+1}(i)=P_r(i)\frac{1}{2^{n-r+1}-1}\sum_{j\ne i}P_v(i,j)P_r(j)$$

So, all you need to do is compute $P_n(i)$ recursively.

• Don't we need to exclude teams that have lost? If A beats B in round $r + 1$, we somehow need to exclude the probability $P_v(A, B)$ from subsequent rounds. Commented Jun 4, 2014 at 8:49
• that possibility is taken care of by $P_r(j)$.
– sds
Commented Jun 6, 2014 at 1:48
• @sds's answer is not correct. Use an all equal skilled 4 team tournament for example. Any team has a win chance of 0.25. But his formula wont give the correct number. Commented Mar 31, 2016 at 21:40
• @user245259: yes it will - all the probabilities will be uniform.
– sds
Commented Apr 1, 2016 at 14:32

@sds's answer is not correct. Use an all equal skilled 4 team tournament for example. Any team has a win chance of 0.25. But his formula gives 0.75.

Should be:

$$P_2(i) = \sum_{j!=i}\frac{1}{2^{n}-1} P_v(i,j)$$

$$P_{r+1}(i) = \sum_{j!=i}\frac{2^{r-1}}{2^{n}-1} P_r(i,!j)P_v(i,j)P_r(j)$$

$P_r(i,!j)$ is the probability that $i$ reached round $r$ without meeting $j$ in the previous matches.

To calculate $P_r(i,!j)$, use recursion again:

$$P_2(i,!j) = \frac{2^{n}-2}{2^{n}-1}\sum_{k!=i,k!=j}\frac{1}{2^{n}-2} P_v(i,k)$$

$$P_{r+1}(i,!j) = \frac{2^{n}-2^{r}}{2^{n}-1}\sum_{k!=i, k!=j}\frac{2^{r-1}}{2^{n}-2} P_r(i,!j)P_v(i,k)P_r(k)$$