13
$\begingroup$

$2^n$ players $P_1, \dots, P_{2^n}$, ordered in decreasing order of skill are placed uniformly at random at the leaves of a binary tree of depth $n$.

They play a knockout tournament according to the tree structure. When two players meet, the more skilled player always wins and advances to the next round, while the less skilled player is knocked out.

An upset is a pair of players $P_i, P_j$ with $i < j$, but $P_i$ is knocked out at a strictly earlier stage of the tournament than $P_j$, that is, at a lower depth on the binary tree.

Question: What is the expected number of upsets? Can we obtain sharp asymptotics in $n$?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ From numerical experiments one has approximately for {n, E_n}: {2,1/3}, {3, 2.33}, {4, 11.7}, {5,51.6}, {6,217.2}, {7,889},{8,3599} This suggest that for larger n: E_(n+1)/E_n ~ 4. $\endgroup$ Commented 2 days ago

2 Answers 2

Reset to default
18
$\begingroup$

I can now give a simpler argument, inspired by Julian Rosen's answer, but giving an exact formula. The expected number of upsets is exactly $\frac{4^n}{18} - \frac{2^n}{6} + \frac{1}{9}=(2^n-2) (2^n-1)/18$.

The expected number of upsets in the first round is $2^n (2^n-2)/ 24$ since there are $2^n (2^n-2)$ ordered pairs of seats that don't play each other and, given such an ordered pair $L_1,L_2$, the probability is an upset is $1/24$, since if $L_1$ plays $L_3$ and $L_2$ plays $L_4$, an upset happens if and only if $L_3$ is weaker than $L_1$ who is weaker than $L_2$ who is weaker than $L_4$, which is one out of $24$ possible orderings, all equally unlikely.

After the first round, the tournament is exactly like the tournament with $2^{n-1}$ players. It does not matter who won in the first round, as the skills of the players in the next round are still totally ordered and randomly distributed through the tree. Thus if $E_n$ is the expected number of upsets we get

$$E_n = \frac{2^n (2^n-2)}{24} + E_{n-1}$$ for $n>1$ and $E_1=0$ so that $$E_n = \frac{4^n}{18} - \frac{2^n}{6} + \frac{1}{9}$$ by induction on $n$.

This fits very well with the numerical data computed by Karl Fabian - the discrepancy is $<4$ for all $n$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice analysis! Do we know anything about the behaviour of $a_d$? Does it limit to a nonzero number? $\endgroup$ Commented yesterday
  • $\begingroup$ Oh i guess it is increasing. $\endgroup$ Commented yesterday
5
$\begingroup$

Each player has some probability $p$ of having higher skill than a random other player. A player survives through round $d$ of the tournament precisely when they are the most skilled of the $2^d-1$ potential opponents through round $d$, and for $n$ large, this probability approaches $p^{2^d-1}$. So the probability player with probability $p$ is eliminated before player with probability $q$ is close to $$ \sum_{d\geq 1}\left(p^{2^{d-1}-1}-p^{2^{d}-1}\right)q^{2^{d}-1}. $$ As $n\to\infty$, the player probabilities approach uniform distribution on $[0,1]$, and there are $\sim 4^n$ ordered pairs of players, so expected number of upsets should be asymptotic to $$ \begin{align*} 4^n \sum_{d\geq 1}\int_{0\leq q\leq p\leq 1} \left(p^{2^{d-1}-1}-p^{2^{d}-1}\right)q^{2^{d}-1}dq\,dp &= 4^n \sum_{d\geq 1} \frac{1}{2^d}\int_{0}^1\left(p^{2^{d-1}-1}-p^{2^{d}-1}\right) p^{2^d} \,dp\\ &=4^n\sum_{d\geq 1} \frac{1}{2^d}\left(\frac{1}{2^{d-1} + 2^{d}} -\frac{1}{2^d + 2^d}\right)\\ &= 4^n\sum_{d\geq 1} \frac{1}{6\cdot 4^d}=\frac{4^n}{18}. \end{align*} $$

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.