Order statistic
|
|
In statistics, the kth order statistic of a statistical sample is equal its kth-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 applying probability theory to the analysis of the 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.
| Contents |
|
|
Notation and examples
For example, suppose that four numbers are observed or recorded, resulting in a sample of size <math>n=4<math>. if the sample values are
- 6, 9, 3, 8,
they will usually be denoted
- <math>x_1=6; x_2=9; x_3=3; x_4=8<math>
where the subscript i in <math>x_i<math> indicates simply the order in which the observations were recorded and is usually assumed not to be significant. A case when the order is significant is when the observations are part of a time series.
The order statistics would be denoted
- <math>x_{(1)}=3; x_{(2)}=6; x_{(3)}=8; x_{(4)}=9<math>
where the subscript (i) enclosed in parentheses indicates the ith order statistic of the sample.
The first order statistic (or smallest order statistic) is always the minimum of the sample, that is,
- <math>X_{(1)}=\min(X_1,\ldots,X_n)<math>
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 n, the nth order statistic (or largest order statistic) is the maximum, that is,
- <math>X_{(n)}=\max(X_1,\ldots,X_n).<math>
The sample range, being the difference between the maximum and minimum, is clearly a function of the order statistics:
- <math>{\rm Range}(X_1,\ldots,X_n)=X_{(n)}-X_{(1)}.<math>
The sample median may or may not be an order statistic, as only when the number of observations is odd will there be a single middle value. More precisely, if <math>n=2m+1<math>, then the sample median is <math>X_{(m+1)}<math> and so is an order statistic. On the other hand, when <math>n=2m<math> there are two middle values, <math>X_{(m)}<math> and <math>X_{(m+1)}<math>, and the sample median is some function of the two (usually the average) and hence not strictly an order statistic. Similar remarks apply to all sample quantiles. Another important statistic in exploratory data analysis which is simply related to the order statistics is the sample interquartile range.
Probabilistic analysis
We will assume that the random variables under consideration are continuous and, where convenient, we will make the additional assumption that they have a density. The peculiarities of the analysis of distributions assigning mass to points (in particular, discrete distributions) are discussed at the end.
The key observation underlying the whole theory is that the cumulative distribution function
- <math>F_X(x)=\Pr(X\le x)<math>
transforms the random variable X into a uniform random variable. More precisely,
- <math>U=F_X(X)<math>
is a random variable distributed uniformly on <math>[0,1]<math>.
In mathematical statistics, the observations <math>(X_1,\ldots,X_n)<math> are assumed to make up a random sample, that is, one assumes that they are independent, and identically distributed according to a single distribution <math>F_X<math>. In that case, the random variables <math>U_i=F_X(X_i)<math> are together a random sample of the uniform distribution on <math>[0,1]<math>.
There is a very basic relationship between the order statistics of a random sample and the quantiles of the underlying probability distribution, namely
- the probability that the qth quantile of a probability distribution falls between the kth and (k+1)th order statistics of a random sample of size n drawn from that same distribution is
- <math>{n\choose k} q^k(1-q)^{n-k}<math>
This is easily understood, as the interval <math>(X_{(k)},X_{(k+1)})<math> will straddle the qth quantile only if exactly k of the sample observations are below the qth quantile, and exactly n-k are above it. Now, the meaning of the qth quantile is precisely that the probability of a random observation falling under it is q and the probability that an observation falls above it is 1-q. Since the order of the observations does not matter, but only how many fall below and above the qth quantile, there are <math>{}^n_k C<math> equally likely permutations of the n sample observations which lead to the same result. See binomial distribution and Bernoulli trial for additional discussion of similar situations.
Finally, an equivalent statement involving the cdf <math>F_X<math> is obtained by realizing that <math>X=x<math> is the <math>F(x)<math>-th quantile of the distribution of <math>X<math>. The previous result can be rephrased thus:
- the probability that the value x is straddled by the kth and (k+1)th order statistics of a random sample of size n drawn from the probability distribution of the random variable X is
- <math>{n\choose k}[F_X(x)]^k[1-F(x)]^{n-k}<math>
Probability distributions of order statistics
In this section we show that the order statistics of the uniform distribution on the unit interval have marginal distributions belonging to the Beta 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 <math>X_{1}, X_{2}, \ldots, X_{n}<math> is a random sample drawn from a continuous distribution with cdf <math>F_X<math>. Denoting <math>U_i=F_X(X_i)<math> we obtain the corresponding random sample <math>U_1,\ldots,U_n<math> from the standard uniform distribution. Note that the order statistics also satisfy <math>U_{(i)}=F_X(X_{(i)})<math>.
The order statistics of the uniform distribution
The probability of the order statistic <math>U_{(k)}<math> falling in the interval <math>[u,u+du]<math> is equal to
- <math>{n!\over (k-1)!(n-k)!}u^{k-1}(1-u)^{n-k}du+O(du^2),<math>
that is, the kth order statistic of the uniform distribution is a Beta random variable.
- <math>U_{(k)} \sim B(k,n+1-k).<math>
The proof of these statements is as follows. In order for <math>U_{(k)}<math> 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 <math>O(du^2)<math>, so we have to calculate the probability that exactly k-1, 1 and n-k observations fall in the intervals <math>(0,u)<math>, <math>(u,u+du)<math> and <math>(u+du,1)<math> respectively. This equals (refer to multinomial distribution for details)
- <math>{n!\over (k-1)!1!(n-k)!}u^k\cdot du\cdot(1-u-du)^{n-k}<math>
and the result follows.
Joint distributions
Similarly, for i < j, the joint probability density function of the two order statistics Ui<Uj can be shown to be
- <math>f_{U_{(i)},U_{(j)}}(u,v)du\,dv= n!{u^{i-1}\over (i-1)!}{(v-u)^{j-i-1}\over(j-i-1)!}{(1-v)^{n-j}\over n-j}du\,dv<math>
which is (up to terms of higher order than <math>O(du\,dv)<math>) the probability that i-1, 1, j-1-i, 1 and n-j sample elements fall in the intervals <math>(0,u)<math>, <math>(u,u+du)<math>, <math>(u+du,v)<math>, <math>(v,v+dv)<math>, <math>(v+dv,1)<math> 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:
- <math>f_{U_{(1)},U_{(2)},\ldots,U_{(n)}}(u_{1},u_{2},\ldots,u_{n})du_1\,\cdots\,du_n = n! du_1\cdots du_n.<math>
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 <math>0 If FX is absolutely continuous it has a density such that <math>dF_X(x)=f_X(x)\,dx<math>. Then, we can use the substitutions
and
to derive the following pdfs for the order statistics of a sample of size n drawn from the distribution of X:
An interesting question is how well the order statistics perform as estimators of the quantiles of the underlying distribution.
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.
If the distribution is known to be symmetric and have finite variance (as is the case for the normal distribution) the population mean equals the median, and the sample mean has much better confidence intervals than the sample median. This is an illustration of the relative weakness of distribution-free statistical methods. On the other hand, using methods tailored to the wrong distribution can lead to large systematic errors in estimation.
The order statistics of any absolutely continuous distribution
Application: confidence intervals for quantiles
Estimating the median
A small-sample-size example
Large sample sizes
Estimating quantiles
Dealing with discrete variables
See also
External links