Order statistic 160986 214927206 2008-05-25T22:55:58Z Fangz 57409 templates go at the topic, not at the bottom {{expert-subject|statistics}} [[Image:OrderStatistics.gif|thumb|[[Probability distributions]] for the ''n'' = 5 order statistics of an [[exponential distribution]] with ''θ'' = 3.]] In [[statistics]], the ''k''th '''order statistic''' of a [[statistical sample]] is equal to its ''k''th-smallest value. Together with [[ranking|rank statistic]]s, order statistics are among the most fundamental tools in [[non-parametric statistics]] and [[non-parametric inference|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 [[quantile|sample quantiles]]. When using [[probability theory]] to analyze order statistics of [[random sample]]s from a [[continuous probability distribution|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 <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 ''i''th 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 ''' ''n''th order statistic''' (or ''largest order statistic'') is the ''maximum'', that is, :<math>X_{(n)}=\max\{\,X_1,\ldots,X_n\,\}.</math> The [[Range (statistics)|sample range]] is the difference between the maximum and minimum. It is clearly a function of the order statistics: :<math>{\rm Range}\{\,X_1,\ldots,X_n\,\} = X_{(n)}-X_{(1)}.</math> 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 <math>n</math> of observations is [[odd]]. More precisely, if <math>n=2m+1</math> for some <math>m</math>, then the sample median is <math>X_{(m+1)}</math> and so is an order statistic. On the other hand, when <math>n</math> is [[even]], <math>n=2m</math> and 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 an order statistic. Similar remarks apply to all sample quantiles. == Probabilistic analysis == Given any random variables <math>X_{1}, X_{2}, \ldots, X_{n}</math>, the order statistics <math>X_{(1)}, X_{(2)}, \ldots, X_{(n)}</math> are also random variables, defined by sorting the values ([[realization (probability)|realizations]]) of <math>X_{1}, X_{2}, \ldots, X_{n}</math> in increasing order. When the random variables <math>X_{1}, X_{2}, \ldots, X_{n}</math> form a [[Sample (statistics)|sample]], they are independent and identically distributed ([[Independent and identically-distributed random variables|iid]]). This is the case treated below. In general, the random variables <math>X_{1}, X_{2}, \ldots, X_{n}</math> can arise by sampling from more than one population. Then they are [[Independent (statistics)|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 probability distribution|continuous]] and, where convenient we will also assume that they [[probability density function|have a density]] (that is, they are [[absolute continuity|absolutely continuous]]). The peculiarities of the analysis of distributions assigning mass to points (in particular, [[discrete distribution]]s) are discussed at the end. === Distribution of each order statistic of an absolutely continuous distribution === Let <math>X_{1}, X_{2}, \ldots, X_{n}</math> be [[Independent and identically-distributed random variables|iid]] absolutely continuously distributed [[random variable]]s, and <math>X_{(1)}, X_{(2)}, \ldots, X_{(n)}</math> be the corresponding order statistics. Let <math>f(x)</math> be the [[probability density function]] and <math>F(x)</math> be the [[cumulative distribution function]] of <math>X_{i}</math>. Then the probability density of the ''k''<sup>th</sup> statistic can be found as follows. ::<math> \begin{align} f_{X_{(k)}}(x) & {} ={d \over dx} F_{X_{(k)}}(x) ={d \over dx}P\left(X_{(k)}\leq x\right)={d \over dx}P(\mathrm{at}\ \mathrm{least}\ k\ \mathrm{of}\ \mathrm{the}\ n\ X\mathrm{s}\ \mathrm{are}\leq x) \\ & {} ={d \over dx}P(\geq k\ \mathrm{successes}\ \mathrm{in}\ n\ \mathrm{trials})={d \over dx}\sum_{j=k}^n{n \choose j}P(X_1\leq x)^j(1-P(X_1\leq x))^{n-j} \\ & {} ={d \over dx}\sum_{j=k}^n{n \choose j} F(x)^j (1-F(x))^{n-j} \\ & {} =\sum_{j=k}^n{n \choose j}\left(jF(x)^{j-1}f(x)(1-F(x))^{n-j} +F(x)^j (n-j)(1-F(x))^{n-j-1}(-f(x))\right) \\ & {} =\sum_{j=k}^n\left(n{n-1 \choose j-1}F(x)^{j-1}(1-F(x))^{n-j} - n{n-1 \choose j} F(x)^j(1-F(x))^{n-j-1} \right)f(x) \\ & {} = nf(x)\left(\sum_{j=k-1}^{n-1} {n-1 \choose j} F(x)^j (1-F(x))^{(n-1)-j} - \sum_{j=k}^n {n-1 \choose j} F(x)^j (1-F(x))^{(n-1)-j}\right) \end{align} </math> and the sum above [[telescoping sum|telescopes]], so that all terms cancel except the first and the last: :<math>{} = nf(x)\left({n-1 \choose k-1} F(x)^{k-1} (1-F(x))^{(n-1)-(k-1)} - \underbrace{{n-1 \choose n} F(x)^n (1-F(x))^{(n-1)-n}}\right)</math> and the term over the underbrace is zero, so: :<math> \begin{align} & {} = nf(x){n-1 \choose k-1} F(x)^{k-1} (1-F(x))^{(n-1)-(k-1)} \\ & {} = {n! \over (k-1)!(n-k)!} F(x)^{k-1} (1-F(x))^{n-k} f(x). \end{align} </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 distribution|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 [[cumulative distribution function|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 ''k''th order statistic of the uniform distribution is a [[beta distribution|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''+d''u'', 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 <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-1}\cdot du\cdot(1-u-du)^{n-k}</math> and the result follows. ==== Joint distributions ==== Similarly, for ''i''&nbsp;<&nbsp;''j'', the joint probability density function of the two order statistics ''U''<sub>''i''</sub>&nbsp;<&nbsp;''U''<sub>''j''</sub> 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''&nbsp;&minus;&nbsp;1, 1, ''j''&nbsp;&minus;&nbsp;1&nbsp;&minus;&nbsp;''i'', 1 and ''n''&nbsp;&minus;&nbsp;''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<u_1<\cdots<u_n<1</math>. == Application: confidence intervals for quantiles == An interesting question is how well the order statistics perform as estimators of the [[quantile]]s 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 :<math>{6\choose 3}2^{-6} = {5\over 16} \approx 31\%.</math> Although the sample median is probably among the best distribution-independent [[point estimate]]s 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 :<math>\left[{6\choose 2}+{6\choose 3}+{6\choose 4}\right]2^{-6} = {25\over 32} \approx 78\%.</math> 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<sup>th</sup> sample quantile is asymptotically normally distributed, since it is approximated by <math>U_{(\lceil np \rceil)} \sim AN\left(p,\frac{p(1-p)}{n}\right).</math> For a general distribution F with a continuous non-zero density at ''F<sup>-1</sup>(p)'', a similar asymptotic normality applies: <math>X_{(\lceil np \rceil)} \sim AN\left(F^{-1}(p),\frac{p(1-p)}{n[f(F^{-1}(p))]^2}\right)</math> where ''f'' is the [[density function]], and ''F<sup>-1</sup>'' is the [[quantile function]] associated with F. 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 σ<sup>2</sup>''/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 <math>B(k,n+1-k)\ \stackrel{\mathrm{d}}{=}\ \frac{X}{X + Y},</math> where <math> X = \sum_{i=1}^{k} Z_i, \quad Y = \sum_{i=k+1}^{n+1} Z_i,</math> with ''Z<sub>i</sub>'' being independent identically distributed [[exponential distribution|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]]. == Dealing with discrete variables == == Computing order statistics == {{main|Selection algorithm}} 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''). ==See also== * [[Quantile]] * [[Median]] * [[Rankit]] * [[Box plot]] * [[Fisher-Tippett distribution]] * [[Bapat-Beg theorem]] for the order statistics of independent but not necessarily identically distributed random variables ==External links== * {{PlanetMath | urlname=OrderStatistics | title=order statistics}} Retrieved Feb 02,2005 * {{MathWorld | urlname=OrderStatistic | title=Order Statistic}} Retrieved Feb 02,2005 * Dr. Susan Holmes [http://www-stat.stanford.edu/~susan/courses/s116/node79.html Order Statistics] Retrieved Feb 02,2005 ==References== David,H.A., Nagaraja,H.N. (2003) Order Statistics (3rd Edition). Wiley, New Jersey pp458. ISBN 0-471-38926-9 [[Category:Summary statistics]] [[Category:Permutations]] [[fr:Statistique d'ordre]] [[ja:順序統計量]] [[ru:Порядковая статистика]] [[uk:Порядкова статистика]]