Introduction to Order Statistics

This article was published as a part of the Data Science Blogathon.

Introduction

Order statistics are a very useful concept in statistical sciences. They have a wide range of applications including modeling auctions, car races, and insurance policies, optimizing production processes, estimating parameters of distributions, et al. Through this article, we’ll understand the idea of order statistics. We’ll first understand its meaning and gradually proceed to its distribution, eventually covering more advanced concepts.

Suppose we have a set of random variables X₁, X₂, …, X_n, which are independent and identically distributed (i.i.d). By independence, we mean that the value taken by a random variable is not influenced by the values taken by other random variables. By identical distribution, we mean that the probability density function (PDF) (or equivalently, the Cumulative distribution function, CDF) for the random variables is the same. The k^th order statistic for this set of random variables is defined as the k^th smallest value of the sample.

To better understand this concept, we’ll take 5 random variables X₁, X₂, X₃, X₄, X₅. We’ll observe a random realization/outcome from the distribution of each of these random variables. Suppose we get the following values:

The k^th order statistic for this experiment is the k^th smallest value from the set {4, 2, 7, 11, 5}. So, the 1^st order statistic is 2 (smallest value), the 2^nd order statistic is 4 (next smallest), and so on. The 5^th order statistic is the fifth smallest value (the largest value), which is 11. We repeat this process many times i.e., we draw samples from the distribution of each of these i.i.d random variables, & find the k^th smallest value for each set of observations. The probability distribution of these values gives the distribution of the k^th order statistics.

In general, if we arrange random variables X₁, X₂, …, X_n in ascending order, then the k^th order statistic is shown as:

The general notation of the k^th order statistic is X_(k). Note X_(k) is different from X_k. X_k is the k^th random variable from our set, whereas X_(k) is the k^th order statistic from our set. X_(k) takes the value of X_k if X_k is the k^th random variable when the realizations are arranged in ascending order.

The 1^st order statistic X₍₁₎ is the set of the minimum values from the realization of the set of ‘n’ random variables. The n^th order statistic X_(n) is the set of the maximum values (nth minimum values) from the realization of the set of ‘n’ random variables. They can be expressed as:

Distribution of Order Statistics

We’ll now try to find out the distribution of order statistics. We’ll first describe the distribution of the n^th order statistic, then the 1^st order statistic & finally the k^th order statistic in general.

A) Distribution of the n^th Order Statistic:

Let the probability density function (PDF) & cumulative distribution function (CDF) our random variables be f_x(x), and F_x(x) respectively. By definition of CDF,

Since our random variables are identically distributed, they have the same PDF f_x(x) & CDF F_x(x). We’ll now calculate the CDF of n^th order statistic (F_n(x)) as follows:

The random variables X₁, X₂, …, X_n are also independent. Therefore, by property of independence,

 

The PDF of the n^th order statistic (f_n(x)) is calculated as follows:

Thus, the expression for the PDF & CDF of n^th order statistic has been obtained.

B) Distribution of the 1^st Order Statistic:

The CDF of a random variable can also be calculated as the one minus the probability that the random variable X takes a value more than or equal to x. Mathematically,

We’ll determine the CDF of 1^st order statistic (F₁(x)) as follows:

 

Once again, using the property of independence of random variables,

 

The PDF of the 1^st order statistic (f₁(x)) is calculated as follows:

Thus, the expression for PDF & CDF of 1^st order statistic has been obtained.

C) Distribution of the k^th Order Statistic:

For k^th order statistic, in general, the following equation describes its CDF (F_k(x)):

The PDF of k^th order statistic (f_k(x)) is expressed as:

 

To avoid confusion, we’ll use geometric proof to understand the equation. As discussed before, the set of random variables have the same PDF (f_X(x)). The following graph shows a sample PDF with the k^th order statistic obtained from random sampling:

So, the PDF of the random variables f_X(x) is defined between the interval [a,b]. The kth order statistic for a random sample is shown by the red line. The other variable realizations (for the random sample) are shown by the small black lines on the x-axis.

There are exactly (k – 1) random variable observations that fall in the yellow region of the graph (the region between a & k^th order statistic). The probability that a particular observation falls in this region is given by the CDF of the random variables (F_X(x)). But we are aware that (k – 1) observations did fall in the region, which gives us the term (by independence) (F_X(x))^{(k – 1)}.

There are exactly (n – k) random variable observations that fall in the blue region of the graph (the region between k^th order statistic & b). The probability that a particular observation falls in this region is given by the 1 – CDF of the random variables (1– F_X(x)). But we are aware that (n – k) observations did fall in the region, which gives us the term (by independence) (1–F_X(x))^{(n – k)}.

Finally, exactly 1 observation falls exactly at the kth order statistic with probability f_X(x). Thus, the product of the 3 terms gives us an idea of the geometric meaning of the equation for PDF of the kth order statistic. But where does the factorial term come from? The above scenario just showed one of the many orderings. There can be many such combinations. The total number of such combinations is shown as follows:

Thus, the product of all of these terms gives us the general distribution of the k^th order statistic.

Useful Functions of Order Statistics

Order statistics give rise to various useful functions. Among them, the notable ones include sample range and sample median.

1) Sample range: It is defined as the difference between the largest and smallest value. It is expressed as follows:

2) Sample median: The sample median divides the random sample (realizations from the set of random variables) into two halves, one that contains samples with lower values, and the other that contains the samples with higher values. It’s like the middle/central order statistic. It is mathematically defined as:

Joint PDF of Order Statistics

A joint probability density function can help us better understand the relationship between two random variables (two order statistics
in our case). The joint PDF for any 2 order statistics X_(a) & X_(b), such that 1 ≤ a ≤ b ≤ n is given by the following equation:

Example

We’ll use a very simple example to illustrate the distribution of order statistics- the standard uniform distribution (U[0, 1] distribution). We’ll take 5 random variables X₁, X₂, X₃, X₄, X₅, all having the U[0, 1] distribution. For this set of random variables, we’ll calculate & plot the 1^st, 3^rd (the sample median) & 5^th (n^th) order statistics. The following figure shows the U[0, 1] distribution:

We’ll draw random samples as follows and find the 1^st, 3^rd & 5^th order statistic for each sample. Two of the samples are shown below:

The PDF & CDF of standard uniform distribution is given as:

We’ll use this information and calculate X₍₁₎, X₍₃₎ & X₍₅₎ using the formulas we derived. We’ll take the case only when x is between 0 & 1 (for other cases, the order statistic is zero as PDF is zero).

A) For 1^st order statistic:

Plot for f₁(x):

B) For 3^rd order statistic:

Plot for f₅(x):

C) For 5^th order statistic:

Plot for f₅(x):

Conclusion

Thus, we’ve explored the concepts of order statistics thoroughly. A wide range of physical processes can be modeled through order statistics, by exploiting their properties, particularly their distributions.

The media shown in this article are not owned by Analytics Vidhya and is used at the Author’s discretion.