Order statistics

Last time we have simulated really simple football tournament. That time we have asked the question about average strength of the champion. But we can also inquire about the distribution, which leads us to order statistics.

In general

Let us assume that we have \( N \) samples from a particular probability distribution with probability density function \( p(x) \) and cumulative distribution function \( P(x) \). Let us order samples from smallest to largest and look at the distribution of \( k \)-th ordered sample (with \( 1 \leq k \leq N \). What is the probability density function of that sample, \( p_k( x ) \)?

If \( k = 1 \), then things are quite simple: we just need \( N-1 \) samples to be less or equal to \( x \) and one sample to be equal to \( x \). This leads to:

\begin{equation} p_1( x ) = N p( x ) \left[ 1-P(x) \right]^{N-1} . \end{equation}

Similar logic leads to \( k = N \) case: we need \( N-1 \) samples to be greater or equal to \( x \) and one sample being equal to \( x \). Resulting in:

\begin{equation} p_N( x ) = N p( x ) P(x)^{N-1} . \end{equation}

Other cases, \( 1 < k < N \), are a bit harder to wrap your head around, but note the \( N \) term in the expression above. It simply stands for the number of possible permutations of \( N \) elements satisfying particular conditions. For the other cases number of permutations is somewhat more complicated, but the general expression has a similar form:

\begin{equation} p_k( x ) = \frac{N!}{(k-1)!(N-k)!} p( x ) P(x)^{k-1} \left[ 1-P(x) \right]^{N-k} . \end{equation}

For uniform distribution

In the particular case considered last week \( x \) were sampled from uniform distribution. Then:

\begin{equation} p_k( x ) = \frac{N!}{(k-1)!(N-k)!} x^{k-1} \left[ 1-x \right]^{N-k} . \end{equation}

We see that in this case \( k \)-th team's strength distribution will follow Beta distribution, \( \mathcal{B}e(k, N+1-k) \). Note that, here we have ranked teams in ascending strength order. To flip the order, simply reverse the order of Beta distribution parameters.

It is important to note that a ranked set of samples from uniform distribution (ranked set of team strengths) is not statistically equivalent to an independent samples from the four respective Beta distributions.

Interactive app

In this interactive app you can change the desired order \( k \) and the sample size \( N \). Blue dots will show simulated probability density function, while dark grey curve shows theoretical result: probability density function of Beta distribution.