The sample median may or may not be an order statistic, since there is a single middle value only when the number n of observations is odd. More precisely, if n = 2m+1 for some integer m, then the sample median is and so is an order statistic. On the other hand, when n is even, n = 2m and there are two middle values, and , 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.
Given any random variables X1, X2..., Xn, the order statistics X(1), X(2), ..., X(n) are also random variables, defined by sorting the values (realizations) of X1, ..., Xn in increasing order.
We assume throughout this section that is a random sample drawn from a continuous distribution with cdf . Denoting we obtain the corresponding random sample from the standard uniform distribution. Note that the order statistics also satisfy .
The probability density function of the order statistic is equal to
The proof of these statements is as follows. For 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 + du. The probability that more than one is in this latter interval is already , so we have to calculate the probability that exactly k − 1, 1 and n − k observations fall in the intervals , and 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 distributionedit
which is (up to terms of higher order than ) the probability that i − 1, 1, j − 1 − i, 1 and n − j sample elements fall in the intervals , , , , 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 . It is also related with another particularity of order statistics of uniform random variables: It follows from the BRS-inequality that the maximum expected number of uniform U(0,1] random variables one can choose from a sample of size n with a sum up not exceeding is bounded above by
, which is thus invariant on the set of all
with constant product .
Using the above formulas, one can derive the distribution of the range of the order statistics, that is the distribution of , i.e. maximum minus the minimum. More generally, for , also has a beta distribution:
From these formulas we can derive the covariance between two order statistics:
The formula follows from noting that
and comparing that with
where , which is the actual distribution of the difference.
Order statistics sampled from an exponential distributionedit
For a random sample of size n from an exponential distribution with parameter λ, the order statistics X(i) for i = 1,2,3, ..., n each have distribution
where the Zj 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 distributionedit
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 quantilesedit
An interesting question is how well the order statistics perform as estimators of the quantiles of the underlying distribution.
A small-sample-size exampleedit
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[clarification needed]
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 sizesedit
For the uniform distribution, as n tends to infinity, the pth 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:
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.
It can be shown that
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 estimationedit
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 at the point . Consider the random variables , which are i.i.d with distribution function . In particular, .
The expected value of the first order statistic given a sample of total observations yields,
where is the quantile function associated with the distribution , and . This equation in combination with a jackknifing technique becomes the basis for the following density estimation algorithm,
Input: A sample of observations. points of density evaluation. Tuning parameter (usually 1/3).
Output: estimated density at the points of evaluation.
3: Create an matrix which holds subsets with observations each.
4: Create a vector to hold the density evaluations.
7: Find the nearest distance to the current point within the th subset
8: end for
9: Compute the subset average of distances to
10: Compute the density estimate at
11: end for
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 variablesedit
Suppose are i.i.d. random variables from a discrete distribution with cumulative distribution function and probability mass function. To find the probabilities of the order statistics, three values are first needed, namely
The cumulative distribution function of the order statistic can be computed by noting that
Similarly, is given by
Note that the probability mass function of is just the difference of these values, that is to say
Computing order statisticsedit
The problem of computing the kth 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).
^David, H. A.; Nagaraja, H. N. (2003). Order Statistics. Wiley Series in Probability and Statistics. doi:10.1002/0471722162. ISBN 9780471722168.
^Casella, George; Berger, Roger (2002). Statistical Inference (2nd ed.). Cengage Learning. p. 229. ISBN 9788131503942.
^ abGentle, James E. (2009), Computational Statistics, Springer, p. 63, ISBN 9780387981444.
^Jones, M. C. (2009), "Kumaraswamy's distribution: A beta-type distribution with some tractability advantages", Statistical Methodology, 6 (1): 70–81, doi:10.1016/j.stamet.2008.04.001, As is well known, the beta distribution is the distribution of the m 'th order statistic from a random sample of size n from the uniform distribution (on (0,1)).
^David, H. A.; Nagaraja, H. N. (2003), "Chapter 2. Basic Distribution Theory", Order Statistics, Wiley Series in Probability and Statistics, p. 9, doi:10.1002/0471722162.ch2, ISBN 9780471722168
^Hlynka, M.; Brill, P. H.; Horn, W. (2010). "A method for obtaining Laplace transforms of order statistics of Erlang random variables". Statistics & Probability Letters. 80: 9–18. doi:10.1016/j.spl.2009.09.006.
^M. Cardone, A. Dytso and C. Rush, "Entropic Central Limit Theorem for Order Statistics," in IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2193-2205, April 2023, doi: 10.1109/TIT.2022.3219344.
^Garg, Vikram V.; Tenorio, Luis; Willcox, Karen (2017). "Minimum local distance density estimation". Communications in Statistics - Theory and Methods. 46 (1): 148–164. arXiv:1412.2851. doi:10.1080/03610926.2014.988260. S2CID 14334678.
^David, H. A.; Nagaraja, H. N. (2003), "Chapter 3. Expected Values and Moments", Order Statistics, Wiley Series in Probability and Statistics, p. 34, doi:10.1002/0471722162.ch3, ISBN 9780471722168
Order statistics at PlanetMath. Retrieved Feb 02,2005