| This article needs attention from an expert in statistics. Please add a reason or a talk parameter to this template to explain the issue with the article. WikiProject Statistics (or its Portal) may be able to help recruit an expert. (November 2008) |
In statistics, the kth order statistic of a statistical sample is equal to its kth-smallest value.^{[1]} 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
- 6, 9, 3, 8,
they will usually be denoted
- $x\_1=6,\backslash \; \backslash \; x\_2=9,\backslash \; \backslash \; x\_3=3,\backslash \; \backslash \; x\_4=8,\backslash ,$
where the subscript i in $x\_i$ 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
- $x\_\{(1)\}=3,\backslash \; \backslash \; x\_\{(2)\}=6,\backslash \; \backslash \; x\_\{(3)\}=8,\backslash \; \backslash \; x\_\{(4)\}=9,\backslash ,$
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,
- $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 n, the 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 clearly 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 n of observations is odd. More precisely, if n = 2m+1 for some m, then the sample median is $X\_\{(m+1)\}$ and so is an order statistic. On the other hand, when n is even, 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.
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 (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.
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 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)\})$.
Order statistics sampled from a uniform distribution
The probability of the order statistic $U\_\{(k)\}$ falling in the interval $[u,\backslash \; u+du]$ is equal to
- $\{n!\backslash over\; (k-1)!(n-k)!\}u^\{k-1\}(1-u)^\{n-k\}\backslash ,du+O(du^2),$
that is, the kth order statistic of the uniform distribution is a Beta random variable.
- $U\_\{(k)\}\; \backslash sim\; B(k,n+1-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).
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
- $f\_\{U\_\{(i)\},U\_\{(j)\}\}(u,v)\backslash ,du\backslash ,dv=\; 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)!\}\backslash ,du\backslash ,dv$
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\})\backslash ,du\_1\backslash cdots\; du\_n\; =\; n!\; \backslash ,\; du\_1\backslash cdots\; du\_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 $0\backslash cdots1\; math>.$
Order statistics sampled from an Erlang distribution
The Laplace transform of order statistics sampled from an Erlang distribution via a path counting method.^{[2]}
The joint distribution of the order statistics of an absolutely continuous distribution
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
- $u=F\_X(x)$
and
- $du=f\_X(x)\backslash ,dx$
to derive the following probability density functions (pdfs) for the order statistics of a sample of size n drawn from the distribution of X:
- $f\_\{X\_\{(k)\}\}(x)\; =\backslash frac\{n!\}\{(k-1)!(n-k)!\}[F\_X(x)]^\{k-1\}[1-F\_X(x)]^\{n-k\}\; f\_X(x)$
- $f\_\{X\_\{(j)\},X\_\{(k)\}\}(x,y)\; =\; \backslash frac\{n!\}\{(j-1)!(k-j-1)!(n-k)!\}[F\_X(x)]^\{j-1\}[F\_X(y)-F\_X(x)]^\{k-1-j\}[1-F\_X(y)]^\{n-k\}f\_X(x)f\_X(y)$ where $x\backslash le\; y$
- $f\_\{X\_\{(1)\},\backslash ldots,X\_\{(n)\}\}(x\_1,\backslash ldots,x\_n)=n!f\_X(x\_1)\backslash cdots\; f\_X(x\_n)$ where $x\_1\backslash le\; x\_2\backslash le\; \backslash dots\; \backslash le\; x\_n.$
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
- $\{6\backslash choose\; 3\}2^\{-6\}\; =\; \{5\backslash over\; 16\}\; \backslash approx\; 31\backslash \%.$
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
- $\backslash left\{=\}\backslash \; \backslash frac\{X\}\{X\; +\; Y\},$
where
- $X\; =\; \backslash sum\_\{i=1\}^\{k\}\; Z\_i,\; \backslash quad\; Y\; =\; \backslash sum\_\{i=k+1\}^\{n+1\}\; Z\_i,$
with Z_{i} 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.
Dealing with discrete variables
Suppose $X\_1,X\_2,...,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
- $p\_1=P(X)=f(x)-f(x),\; \backslash \; p\_2="P(X=x)=f(x),\backslash text\{"\; and\; \}p\_3="P(X">x)=1-F(x).$
The cumulative distribution function of the $k^\backslash text\{th\}$ order statistic can be computed by noting that
- $$
\begin{align}
P(X_{(k)}\leq x)& =P(\text{there are at most }n-k\text{ observations greater than }x) ,\\
& =\sum_{j=0}^{n-k}{n\choose j}p_3^j(p_1+p_2)^{n-j} .
\end{align}
Similarly, $P(X\_\{(k)\})\; math>\; is\; given\; by$
- $$
\begin{align}
P(X_{(k)}< x)& =P(\text{there are at most }n-k\text{ observations greater than or equal to }x) ,\\
&=\sum_{j=0}^{n-k}{n\choose j}(p_2+p_3)^j(p_1)^{n-j} .
\end{align}
Note that the probability mass function of $X\_\{k\}$ is just the difference of these values, that is to say
- $$
\begin{align}
P(X_{(k)}=x)&=P(X_{(k)}\leq x)-P(X_{(k)}< x) ,\\
&=\sum_{j=0}^{n-k}{n\choose j}\left(p_3^j(p_1+p_2)^{n-j}-(p_2+p_3)^j(p_1)^{n-j}\right) ,\\
&=\sum_{j=0}^{n-k}{n\choose j}\left((1-F(x))^j(F(x))^{n-j}-(1-F(x)+f(x))^j(F(x)-f(x))^{n-j}\right).
\end{align}
Computing order statistics
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).
See also
Examples of order statistics
References
External links
- PlanetMath Retrieved Feb 02,2005
- MathWorld. Retrieved Feb 02,2005
- Dr. Susan Holmes Order Statistics Retrieved Feb 02,2005
- C++ source Dynamic Order Statistics
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.