How to Choose a Champion
E.~Ben-Naim and N.~W.~Hengartner
We study a stochastic process that mimics single-game elimination
tournaments. In our model, the outcome of each match is stochastic:
the weaker player wins with upset probability $q\leq 1/2$, and the
stronger player wins with probability $1-q$. The loser is then
eliminated. Extremal statistics of the initial distribution of
player strengths governs the tournament outcome. For a uniform
initial distribution of strengths, the rank of the winner, $x_*$,
decays algebraically with the number of players, $N$, as $x_*\sim
N^{-\beta}$. Different decay exponents are found analytically for
sequential dynamics, \hbox{$\beta_{\rm seq}=1-2q$} and parallel
dynamics, \hbox{$\beta_{\rm par}=1+\frac{\ln (1-q)}{\ln 2}$}. The
distribution of player strengths becomes self-similar in the long
time limit and moreover, it has an algebraic tail.
source,
ps,
pdf