Order statistic#Application: Non-parametric Density Estimation

For example, suppose that four numbers are observed or recorded, resulting in a sample of size 4. If the sample values are

:6, 9, 3, 7,

the order statistics would be denoted

:$x\_\{(1)\}=3,\backslash \; \backslash \; x\_\{(2)\}=6,\backslash \; \backslash \; x\_\{(3)\}=7,\backslash \; \backslash \; x\_\{(4)\}=9,\backslash ,$

where the subscript {{math|({{italics correction|i}})}} enclosed in parentheses indicates the {{math|{{italics correction|i}}}}th order statistic of the sample.

The first order statistic (or smallest order statistic) is always the minimum of the sample, that is,

:$X\_\{(1)\}=\backslash min\backslash \{\backslash ,X\_1,\backslash ldots,X\_n\backslash ,\backslash \}$

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 {{math|n}}, the {{math|{{italics correction|n}}}}th order statistic (or largest order statistic) is the maximum, that is,

:$X\_\{(n)\}=\backslash max\backslash \{\backslash ,X\_1,\backslash ldots,X\_n\backslash ,\backslash \}.$

The sample range is the difference between the maximum and minimum. It is a function of the order statistics:

:$\{\backslash rm\; Range\}\backslash \{\backslash ,X\_1,\backslash ldots,X\_n\backslash ,\backslash \}\; =\; X\_\{(n)\}-X\_\{(1)\}.$

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}} of observations is odd. More precisely, if {{math|1=n = 2m+1}} for some integer {{math|m}}, then the sample median is $X\_\{(m+1)\}$ and so is an order statistic. On the other hand, when {{math|n}} is even, {{math|1=n = 2m}} and there are two middle values, $X\_\{(m)\}$ and $X\_\{(m+1)\}$, 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 X₁, X₂, ..., X_n, the order statistics X₍₁₎, X₍₂₎, ..., X_(n) are also random variables, defined by sorting the values (realizations) of X₁, ..., X_n in increasing order.

When the random variables X₁, X₂, ..., X_n form a sample they are independent and identically distributed. This is the case treated below. In general, the random variables X₁, ..., 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.

For a random sample as above, with cumulative distribution $F\_X(x)$, the order statistics for that sample have cumulative distributions as follows{{cite book

|last1=Casella

|first1=George

|last2=Berger

|first2=Roger

|title=Statistical Inference

|year=2002

|publisher=Cengage Learning

|isbn=9788131503942

|page=229

|edition=2nd

|url={{Google books|0x_vAAAAMAAJ|page=228|plainurl=yes}}

}}

(where r specifies which order statistic):

F_{X_{(r)}}(x) = \sum_{j=r}^{n} \binom{n}{j} [ F_{X}(x) ]^{j} [ 1 - F_{X}(x) ]^{n-j}

The proof of this formula is pure combinatorics: for the $r$th order statistic to be $\backslash leq\; x$, the number of samples that are $>\; x$ has to be between $0$ and $n-r$. In the case that $X\_\{(j)\}$ is the largest order statistic $\backslash leq\; x$, there has to be $j$ samples $\backslash leq\; x$ (each with an independent probability of $F\_X(x)$) and $n-j$ samples $>x$ (each with an independent probability of $1\; -\; F\_X(x)$). Finally there are $\backslash textstyle\; \backslash binom\{n\}\{j\}$ different ways of choosing which of the $n$ samples are of the $\backslash leq\; x$ kind.

The corresponding probability density function may be derived from this result, and is found to be

:$f\_\{X\_\{(r)\}\}(x)\; =\; \backslash frac\{n!\}\{(r-1)!(n-r)!\}\; f\_\{X\}(x)\; [\; F\_\{X\}(x)\; ]^\{r-1\}\; [\; 1\; -\; F\_\{X\}(x)\; ]^\{n-r\}.$

Moreover, there are two special cases, which have CDFs that are easy to compute.

:$F\_\{X\_\{(n)\}\}(x)\; =\; \backslash operatorname\{Prob\}(\backslash max\backslash \{\backslash ,X\_1,\backslash ldots,X\_n\backslash ,\backslash \}\; \backslash leq\; x)\; =\; [\; F\_\{X\}(x)\; ]^n$

:$F\_\{X\_\{(1)\}\}(x)\; =\; \backslash operatorname\{Prob\}(\backslash min\backslash \{\backslash ,X\_1,\backslash ldots,X\_n\backslash ,\backslash \}\; \backslash leq\; x)\; =\; 1-\; [\; 1\; -\; F\_\{X\}(x)\; ]^n$

Which can be derived by careful consideration of probabilities.

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 $X\_1,\; X\_2,\; \backslash ldots,\; X\_n$ is a random sample drawn from a continuous distribution with cdf $F\_X$. Denoting $U\_i=F\_X(X\_i)$ we obtain the corresponding random sample $U\_1,\backslash ldots,U\_n$ from the standard uniform distribution. Note that the order statistics also satisfy $U\_\{(i)\}=F\_X(X\_\{(i)\})$.

The probability density function of the order statistic $U\_\{(k)\}$ is equal to{{citation|title=Computational Statistics|first=James E.|last=Gentle|publisher=Springer|year=2009|isbn=9780387981444|page=63|url=https://books.google.com/books?id=mQ5KAAAAQBAJ&pg=PA63}}.

:$f\_\{U\_\{(k)\}\}(u)=\{n!\backslash over\; (k-1)!(n-k)!\}u^\{k-1\}(1-u)^\{n-k\}$

that is, the kth order statistic of the uniform distribution is a beta-distributed random variable.{{citation|title=Kumaraswamy's distribution: A beta-type distribution with some tractability advantages|first=M. C.|last=Jones|journal=Statistical Methodology|volume=6|issue=1|year=2009|pages=70–81|doi=10.1016/j.stamet.2008.04.001|quote=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)).}}

:$U\_\{(k)\}\; \backslash sim\; \backslash operatorname\{Beta\}(k,n+1\backslash mathbf\{-\}k).$

The proof of these statements is as follows. For $U\_\{(k)\}$ 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 $O(du^2)$, so we have to calculate the probability that exactly k − 1, 1 and n − k observations fall in the intervals $(0,u)$, $(u,u+du)$ and $(u+du,1)$ respectively. This equals (refer to multinomial distribution for details)

:$\{n!\backslash over\; (k-1)!(n-k)!\}u^\{k-1\}\backslash cdot\; du\backslash cdot(1-u-du)^\{n-k\}$

and the result follows.

The mean of this distribution is k / (n + 1).

Similarly, for i < j, the joint probability density function of the two order statistics U_(i) < U_(j) can be shown to be

:$f\_\{U\_\{(i)\},U\_\{(j)\}\}(u,v)\; =\; n!\{u^\{i-1\}\backslash over\; (i-1)!\}\{(v-u)^\{j-i-1\}\backslash over(j-i-1)!\}\{(1-v)^\{n-j\}\backslash over\; (n-j)!\}$

which is (up to terms of higher order than $O(du\backslash ,dv)$) the probability that i − 1, 1, j − 1 − i, 1 and n − j sample elements fall in the intervals $(0,u)$, $(u,u+du)$, $(u+du,v)$, $(v,v+dv)$, $(v+dv,1)$ 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:

:$f\_\{U\_\{(1)\},U\_\{(2)\},\backslash ldots,U\_\{(n)\}\}(u\_\{1\},u\_\{2\},\backslash ldots,u\_\{n\})\; =\; n!.$

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 is bounded above by

For $X\_1,\; X\_2,\; ..,\; X\_n$ 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

The Laplace transform of order statistics may be sampled from an Erlang distribution via a path counting method {{Clarify|reason=Unclear: Scope and relevance. Order statistics of Erlang RVs? Are we sampling from Erlang RVs to learn simulate order statistics of other RVs. Why do we care?|date=February 2019}}.{{Cite journal | last1 = Hlynka | first1 = M. | last2 = Brill | first2 = P. H. | last3 = Horn | first3 = W. | title = A method for obtaining Laplace transforms of order statistics of Erlang random variables | doi = 10.1016/j.spl.2009.09.006 | journal = Statistics & Probability Letters | volume = 80 | pages = 9–18 | year = 2010 }}

If F_X is absolutely continuous, it has a density such that $dF\_X(x)=f\_X(x)\backslash ,dx$, and we can use the substitutions

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.

For the uniform distribution, as n tends to infinity, the p^th sample quantile is asymptotically normally distributed, since it is approximated by

It can be shown that

The mutual information and f-divergence between order statistics have also been considered. A. Dytso, M. Cardone and C. Rush, "Measuring Dependencies of Order Statistics: An Information Theoretic Perspective," in 2020 IEEE Information Theory Workshop, 2021, doi: 10.1109/ITW46852.2021.9457617. For example, if the parent distribution is continuous, then for all $1\; \backslash le\; r,\; m\backslash le\; n$

Moments of the distribution for the first order statistic can be used to develop a non-parametric density estimator.{{cite journal |last1= Garg|first1= Vikram V.|last2= Tenorio|first2= Luis|last3= Willcox|first3= Karen|author3-link=Karen Willcox| date= 2017|title= Minimum local distance density estimation.|journal= Communications in Statistics - Theory and Methods|volume= 46|issue= 1|pages= 148–164|doi= 10.1080/03610926.2014.988260|arxiv= 1412.2851|s2cid= 14334678}} Suppose, we want to estimate the density $f\_\{X\}$ at the point $x^*$. Consider the random variables $Y\_i\; =\; |X\_i\; -\; x^*|$, which are i.i.d with distribution function $g\_Y(y)\; =\; f\_X(y\; +\; x^*)\; +\; f\_X(x^*\; -\; y)$. In particular, $f\_X(x^*)\; =\; \backslash frac\{g\_Y(0)\}\{2\}$.

Suppose $X\_1,X\_2,\backslash ldots,X\_n$ are i.i.d. random variables from a discrete distribution with cumulative distribution function $F(x)$ and probability mass function $f(x)$. To find the probabilities of the $k^\backslash text\{th\}$ order statistics, three values are first needed, namely

{{main|Selection algorithm|Sampling in order}}

Order statistics have a lot of applications in areas as reliability theory, financial mathematics, survival analysis, epidemiology, sports, quality control, actuarial risk, etc. There is an extensive literature devoted to studies on applications of order statistics in these fields.

• Rankit
• Box plot
• BRS-inequality
• Concomitant (statistics)
• Fisher–Tippett distribution
• Bapat–Beg theorem for the order statistics of independent but not necessarily identically distributed random variables
• Bernstein polynomial
• L-estimator – linear combinations of order statistics
• Rank-size distribution
• Selection algorithm

• Sample maximum and minimum
• Quantile
• Percentile
• Decile
• Quartile
• Median
• Mean
• Sample mean and covariance

{{Reflist}}

• {{PlanetMath | urlname=OrderStatistics | title=Order statistics}} Retrieved Feb 02, 2005
• {{MathWorld | urlname=OrderStatistic | title=Order Statistic}} Retrieved Feb 02, 2005
• C++ source [https://github.com/xtaci/algorithms/blob/master/include/dos_tree.h Dynamic Order Statistics]