Order statistic

Probability density functions of the order statistics for a sample of size n = 5 from an exponential distribution with unit scale parameter.

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,\ \ x_2=9,\ \ x_3=3,\ \ x_4=8,\,

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,\ \ x_{(2)}=6,\ \ x_{(3)}=8,\ \ x_{(4)}=9,\,

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,

X_{(1)}=\min\{\,X_1,\ldots,X_n\,\}

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,

X_{(n)}=\max\{\,X_1,\ldots,X_n\,\}.

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

{\rm Range}\{\,X_1,\ldots,X_n\,\} = 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 = 2 m +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 = 2 m$ 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₁, 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 (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}, \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,\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,\ u+du]$ is equal to^[2]

{n!\over (k-1)!(n-k)!}u^{k-1}(1-u)^{n-k}\,du+O(du^2),

that is, the kth order statistic of the uniform distribution is a Beta random variable.^[2]^[3]

U_{(k)} \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!\over (k-1)!(n-k)!}u^{k-1}\cdot du\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)\,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

which is (up to terms of higher order than $O(du\,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)},\ldots,U_{(n)}}(u_{1},u_{2},\ldots,u_{n})\,du_1\cdots \,du_n = n! \, du_1\,\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<u_1<\cdots<u_n<1$ .

Order statistics sampled from an Erlang distribution

The Laplace transform of order statistics sampled from an Erlang distribution via a path counting method.^[4]

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)\,dx$ , and we can use the substitutions

u=F_X(x)

and

du=f_X(x)\,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) =\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) = \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\le y

f_{X_{(1)},\ldots,X_{(n)}}(x_1,\ldots,x_n)=n!f_X(x_1)\cdots f_X(x_n)

where

x_1\le x_2\le \dots \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\choose 3}2^{-6} = {5\over 16} \approx 31\%.

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

\left[{6\choose 2}+{6\choose 3}+{6\choose 4}\right]2^{-6} = {25\over 32} \approx 78\%.

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^th sample quantile is asymptotically normally distributed, since it is approximated by

U_{(\lceil np \rceil)} \sim AN\left(p,\frac{p(1-p)}{n}\right).

For a general distribution F with a continuous non-zero density at F⁻¹(p), a similar asymptotic normality applies:

X_{(\lceil np \rceil)} \sim AN\left(F^{-1}(p),\frac{p(1-p)}{n[f(F^{-1}(p))]^2}\right)

where f is the density function, and F⁻¹ is the quantile function associated with F. One of the first people to mention and prove this result was Frederick Mosteller in his seminal paper in 1946.^[5] Further research lead in the 1960s to the Bahadur representation which provides information about the errorbounds.

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 σ²/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

B(k,n+1-k)\ \stackrel{\mathrm{d}}{=}\ \frac{X}{X + Y},

where

X = \sum_{i=1}^{k} Z_i, \quad Y = \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^\text{th}$ order statistics, three values are first needed, namely

p_1=P(X<x)=F(x)-f(x), \ p_2=P(X=x)=f(x),\text{ and }p_3=P(X>x)=1-F(x).

The cumulative distribution function of the $k^\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)}<x)$ 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

Main articles: Selection algorithm and Sampling in order

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). More sophisticated methods can reduce the time to O(n).

References

↑ David, H. A.; Nagaraja, H. N. (2003). "Order Statistics". Wiley Series in Probability and Statistics. doi:10.1002/0471722162. ISBN 9780471722168.
1 2 Gentle, 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)).
↑ 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. doi:10.1016/j.spl.2009.09.006.
↑ Mosteller, Frederick (1946). "On Some Useful "Inefficient" Statistics". Annals of Mathematical Statistics (Institute of Mathematical Statistics) 17 (4): 377–408. doi:10.1214/aoms/1177730881. Retrieved February 26, 2015.

Sefling, R. J. (1980). Approximation Theorems of Mathematical Statistics. New York: Wiley. ISBN 0-471-02403-1.

External links

Order statistics at PlanetMath.org. Retrieved Feb 02,2005
Weisstein, Eric W., "Order Statistic", MathWorld. Retrieved Feb 02,2005
Dr. Susan Holmes Order Statistics Retrieved Feb 02,2005
C++ source Dynamic Order Statistics

Statistics

Descriptive statistics

Continuous data

Location	Mean arithmetic geometric harmonic Median Mode

Dispersion	Range Standard deviation Coefficient of variation Percentile Interquartile range

Shape	Variance Skewness Kurtosis Moments L-moments

Count data

Index of dispersion

Summary tables

Dependence

Statistical graphics

Data collection

Study design	Effect size Standard error Statistical power Sample size determination

Survey methodology	Sampling stratified cluster Opinion poll Questionnaire

Controlled experiments	Design control optimal Controlled trial Randomized Random assignment Replication Blocking Factorial experiment

Uncontrolled studies	Observational study Natural experiment Quasi-experiment

Statistical inference

Statistical theory

Frequentist inference

Confidence interval Testing hypotheses Power

Unbiased estimators	Mean unbiased minimum-variance Median unbiased

Biased estimators	Maximum likelihood Method of moments Minimum distance Density estimation

Parametric tests	Likelihood-ratio Wald Score

Specific tests

Z (normal) Student's t-test F Shapiro–Wilk Kolmogorov–Smirnov

Goodness of fit	Chi-squared G Sample source (Anderson–Darling) Sample normality (Shapiro–Wilk) Skewness / kurtosis normality (Jarque-Bera) Model comparison (Likelihood-ratio) Model quality (Akaike criterion)

Signed-rank	1-sample (Wilcoxon) 2-sample (Mann–Whitney U) 1-way anova (Kruskal–Wallis)

Bayesian inference

Correlation	Pearson product–moment Partial correlation Confounding variable Coefficient of determination

Regression analysis	Errors and residuals Regression model validation Mixed effects models Simultaneous equations models Multivariate adaptive regression splines (MARS)

Linear regression	Simple linear regression Ordinary least squares General linear model Bayesian regression

Non-standard predictors	Nonlinear regression Nonparametric Semiparametric Isotonic Robust Heteroscedasticity Homoscedasticity

Generalized linear model	Exponential families Logistic (Bernoulli) / Binomial / Poisson regressions

Partition of variance	Analysis of variance (ANOVA, anova) Analysis of covariance Multivariate ANOVA Degrees of freedom

Categorical / Multivariate / Time-series / Survival analysis

Categorical

Multivariate

Time-series

General	Decomposition Trend Stationarity Seasonal adjustment Exponential smoothing Cointegration Structural break Granger causality

Specific tests	Dickey–Fuller Johansen Q-statistic (Ljung–Box) Durbin–Watson Breusch–Godfrey

Time domain	Autocorrelation (ACF) partial (PACF) Cross-correlation (XCF) ARMA model ARIMA model (Box–Jenkins) Autoregressive conditional heteroskedasticity (ARCH) Vector autoregression (VAR)

Frequency domain	Spectral density estimation Fourier analysis Wavelet

Survival

Survival function	Kaplan–Meier estimator (product limit) Proportional hazards models Accelerated failure time (AFT) model First hitting time

Hazard function	Nelson–Aalen estimator

Test	Log-rank test

Applications

Biostatistics	Bioinformatics Clinical trials / studies Epidemiology Medical statistics

Engineering statistics	Chemometrics Methods engineering Probabilistic design Process / quality control Reliability System identification

Social statistics	Actuarial science Census Crime statistics Demography Econometrics National accounts Official statistics Population Psychometrics

Spatial statistics	Cartography Environmental statistics Geographic information system Geostatistics Kriging

Category
Portal
Commons
WikiProject

This article is issued from Wikipedia - version of the Friday, January 22, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Order statistic

Notation and examples

Probabilistic analysis

Probability distributions of order statistics

Order statistics sampled from a uniform distribution

The joint distribution of the order statistics of the uniform distribution

Order statistics sampled from an Erlang distribution

The joint distribution of the order statistics of an absolutely continuous distribution

Application: confidence intervals for quantiles

A small-sample-size example

Large sample sizes

Proof

Dealing with discrete variables

Computing order statistics

See also

Examples of order statistics

References

External links