Order statistic

In statistics, the "k"th order statistic of a statistical sample is equal to its "k"th-smallest value. Together with rank statistics, order statistics are among the most fundamental tools in non-parametric statistics and inference.
Important special cases of the order statistics are the minimum and maximum value of a sample, and (with some qualifications discussed below) the sample median and other sample quantiles.
When using probability theory to analyze order statistics of random samples from a continuous distribution, the cumulative distribution function is used to reduce the analysis to the case of order statistics of the uniform distribution.
Notation and examples.
For example, suppose that four numbers are observed or recorded, resulting in a sample of size 4. If the sample values are
the order statistics would be denoted
where the subscript enclosed in parentheses indicates the th order statistic of the sample.
The first order statistic (or smallest order statistic) is always the minimum of the sample, that is,
where, following a common convention, we use upper-case letters to refer to random variables, and lower-case letters (as above) to refer to their actual observed values.
Similarly, for a sample of size , the th order statistic (or largest order statistic) is the maximum, that is,
The sample range is the difference between the maximum and minimum. It is a function of the order statistics:
A similar important statistic in exploratory data analysis that is simply related to the order statistics is the sample interquartile range.
The sample median may or may not be an order statistic, since there is a single middle value only when the number of observations is odd. More precisely, if for some integer , then the sample median is formula_5 and so is an order statistic. On the other hand, when is even, and there are two middle values, formula_6 and formula_5, and the sample median is some function of the two (usually the average) and hence not an order statistic. Similar remarks apply to all sample quantiles.
Probabilistic analysis.
Given any random variables "X"1, "X"2..., "X""n", the order statistics X(1), X(2), ..., X("n") are also random variables, defined by sorting the values (realizations) of "X"1, ..., "X""n" in increasing order.
When the random variables "X"1, "X"2..., "X""n" form a sample they are independent and identically distributed. This is the case treated below. In general, the random variables "X"1, ..., "X""n" can arise by sampling from more than one population. Then they are independent, but not necessarily identically distributed, and their joint probability distribution is given by the Bapat–Beg theorem.
From now on, we will assume that the random variables under consideration are continuous and, where convenient, we will also assume that they have a probability density function (PDF), that is, they are absolutely continuous. The peculiarities of the analysis of distributions assigning mass to points (in particular, discrete distributions) are discussed at the end.
Cumulative distribution function of order statistics.
For a random sample as above, with cumulative distribution formula_8, the order statistics for that sample have cumulative distributions as follows
(where "r" specifies which order statistic):
the corresponding probability density function may be derived from this result, and is found to be
Moreover, there are two special cases, which have CDFs which are easy to compute.
Which can be derived by careful consideration of probabilities.
Probability distributions of order statistics.
Order statistics sampled from a uniform distribution.
In this section we show that the order statistics of the uniform distribution on the unit interval have marginal distributions belonging to the Beta distribution family. We also give a simple method to derive the joint distribution of any number of order statistics, and finally translate these results to arbitrary continuous distributions using the cdf.
We assume throughout this section that formula_13 is a random sample drawn from a continuous distribution with cdf formula_14. Denoting formula_15 we obtain the corresponding random sample formula_16 from the standard uniform distribution. Note that the order statistics also satisfy formula_17.
The probability density function of the order statistic formula_18 is equal to
that is, the "k"th order statistic of the uniform distribution is a beta-distributed random variable.
The proof of these statements is as follows. For formula_18 to be between "u" and "u" + "du", it is necessary that exactly "k" − 1 elements of the sample are smaller than "u", and that at least one is between "u" and "u" + d"u". The probability that more than one is in this latter interval is already formula_22, so we have to calculate the probability that exactly "k" − 1, 1 and "n" − "k" observations fall in the intervals formula_23, formula_24 and formula_25 respectively. This equals (refer to multinomial distribution for details)
and the result follows.
The mean of this distribution is "k" / ("n" + 1).
The joint distribution of the order statistics of the uniform distribution.
Similarly, for "i" < "j", the joint probability density function of the two order statistics "U"("i") < "U"("j") can be shown to be
which is (up to terms of higher order than formula_28) the probability that "i" − 1, 1, "j" − 1 − "i", 1 and "n" − "j" sample elements fall in the intervals formula_23, formula_24, formula_31, formula_32, formula_33 respectively.
One reasons in an entirely analogous way to derive the higher-order joint distributions. Perhaps surprisingly, the joint density of the "n" order statistics turns out to be "constant":
One way to understand this is that the unordered sample does have constant density equal to 1, and that there are "n"! different permutations of the sample corresponding to the same sequence of order statistics. This is related to the fact that 1/"n"! is the volume of the region formula_35.
Using the above formulas, one can derive the distribution of the range of the order statistics, that is the distribution of formula_36, i.e. maximum minus the minimum. More generally, for formula_37, formula_38 also has a Beta distribution: formula_39From these formulas we can derive the covariance between two order statistics:formula_40The formula follows from noting that formula_41and comparing that with formula_42where formula_43, which is the actual distribution of the difference.
Order statistics sampled from an exponential distribution.
For formula_44 random samples from an exponential distribution with parameter "λ," the order statistics "X""(i)" for "i" = 1,2,3, ..., "n" each have distribution
where the "Z""j" are iid standard exponential random variables (i.e. with rate parameter 1). This result was first published by Alfréd Rényi. 
Order statistics sampled from an Erlang distribution.
The Laplace transform of order statistics may be sampled from an Erlang distribution via a path counting method .
The joint distribution of the order statistics of an absolutely continuous distribution.
If "F""X" is absolutely continuous, it has a density such that formula_46, and we can use the substitutions
and
to derive the following probability density functions for the order statistics of a sample of size "n" drawn from the distribution of "X":
Application: confidence intervals for quantiles.
An interesting question is how well the order statistics perform as estimators of the quantiles of the underlying distribution.
A small-sample-size example.
The simplest case to consider is how well the sample median estimates the population median.
As an example, consider a random sample of size 6. In that case, the sample median is usually defined as the midpoint of the interval delimited by the 3rd and 4th order statistics. However, we know from the preceding discussion that the probability that this interval actually contains the population median is
Although the sample median is probably among the best distribution-independent point estimates of the population median, what this example illustrates is that it is not a particularly good one in absolute terms. In this particular case, a better confidence interval for the median is the one delimited by the 2nd and 5th order statistics, which contains the population median with probability
With such a small sample size, if one wants at least 95% confidence, one is reduced to saying that the median is between the minimum and the maximum of the 6 observations with probability 31/32 or approximately 97%. Size 6 is, in fact, the smallest sample size such that the interval determined by the minimum and the maximum is at least a 95% confidence interval for the population median.
Large sample sizes.
For the uniform distribution, as "n" tends to infinity, the "p"th sample quantile is asymptotically normally distributed, since it is approximated by
For a general distribution "F" with a continuous non-zero density at "F" −1("p"), a similar asymptotic normality applies:
where "f" is the density function, and "F" −1 is the quantile function associated with "F". One of the first people to mention and prove this result was Frederick Mosteller in his seminal paper in 1946. Further research led in the 1960s to the Bahadur representation which provides information about the errorbounds.
An interesting observation can be made in the case where the distribution is symmetric, and the population median equals the population mean. In this case, the sample mean, by the central limit theorem, is also asymptotically normally distributed, but with variance σ2"/n" instead. This asymptotic analysis suggests that the mean outperforms the median in cases of low kurtosis, and vice versa. For example, the median achieves better confidence intervals for the Laplace distribution, while the mean performs better for "X" that are normally distributed.
Proof.
It can be shown that
where
with "Zi" being independent identically distributed exponential random variables with rate 1. Since "X/n" and "Y/n" are asymptotically normally distributed by the CLT, our results follow by application of the delta method.
Application: Non-parametric density estimation.
Moments of the distribution for the first order statistic can be used to develop a non-parametric density estimator. Suppose, we want to estimate the density formula_60 at the point formula_61. Consider the random variables formula_62, which are i.i.d with distribution function formula_63. In particular, formula_64.
The expected value of the first order statistic formula_65 given formula_66 total samples yields,
where formula_68 is the quantile function associated with the distribution formula_69, and formula_70. This equation in combination with a jackknifing technique becomes the basis for the following density estimation algorithm,
 Input: formula_66 samples. formula_72 points of density evaluation. Tuning parameter formula_73 (usually 1/3).
 Output: formula_74 estimated density at the points of evaluation.
 1: Set formula_75
 2: Set formula_76
 3: Create an formula_77 matrix formula_78 which holds formula_79 subsets with formula_80 samples each.
 4: Create a vector formula_81 to hold the density evaluations.
 5: for formula_82 do
 6: for formula_83 do
 7: Find the nearest distance formula_84 to the current point formula_85 within the formula_86th subset
 8: end for
 9: Compute the subset average of distances to formula_87
 10: Compute the density estimate at formula_88
 11: end for
 12: return formula_81
In contrast to the bandwidth/length based tuning parameters for histogram and kernel based approaches, the tuning parameter for the order statistic based density estimator is the size of sample subsets. Such an estimator is more robust than histogram and kernel based approaches, for example densities like the Cauchy distribution (which lack finite moments) can be inferred without the need for specialized modifications such as IQR based bandwidths. This is because the first moment of the order statistic always exists if the expected value of the underlying distribution does, but the converse is not necessarily true.
Dealing with discrete variables.
Suppose formula_90 are i.i.d. random variables from a discrete distribution with cumulative distribution function formula_91 and probability mass function formula_92. To find the probabilities of the formula_93 order statistics, three values are first needed, namely
The cumulative distribution function of the formula_93 order statistic can be computed by noting that
Similarly, formula_97 is given by
Note that the probability mass function of formula_99 is just the difference of these values, that is to say
Computing order statistics.
The problem of computing the "k"th smallest (or largest) element of a list is called the selection problem and is solved by a selection algorithm. Although this problem is difficult for very large lists, sophisticated selection algorithms have been created that can solve this problem in time proportional to the number of elements in the list, even if the list is totally unordered. If the data is stored in certain specialized data structures, this time can be brought down to O(log "n"). In many applications all order statistics are required, in which case a sorting algorithm can be used and the time taken is O("n" log "n").