Order statistic ($X_{(r)}$)

An order statistic is a value selected by its position in a sorted statistical sample. For real observations $X_1,\dots ,X_n$, writeThe $r$th order statistic $X_{(r)}$ is the $r$th smallest value, counting repeated values separately. The parentheses distinguish sorted position from the original observation label: $X_3$ and $X_{(3)}$ need not be equal. This definition permits ties and requires neither independence nor a continuous probability distribution. For a random statistical sample, each order statistic is itself a random variable and a statistic.

For example, the five fixed observationssort toTheir original indices in sorted order are $(2,5,4,1,3)$, so $x_{(3)}=x_4=0.4$. Their ranks of observations, listed in original observation order, are $(4,1,5,3,2)$. Here $x_{(1)}=0.1$ is the minimum, $x_{(5)}=0.9$ is the sample maximum, and $x_{(3)}=0.4$ is the sample median. These are deliberately chosen observations, rather than simulated draws.

Order statistics put extremes and typical values in one language: the first and last locate the minimum and sample maximum, while intermediate positions give sample quantiles and the sample median. Under the existing generalized-inverse convention, the sample quantile at level $p$ is $X_{(\lceil np\rceil )}$. For the five observations, the sample quantiles at $p=0.2,0.5,0.8$ are $0.1,0.4,0.7$. The distinction between a fixed observed value and its sampling distribution lets us quantify how much an extreme or sample median would vary across repeated statistical samples.

The useful counting identity isFor independent and identically distributed random variables with a continuous cumulative distribution function $F$, the count on the right has binomial distribution with parameters $n,F(t)$, givingThis cumulative distribution function is a binomial distribution tail: a question about sorting becomes a question about counting successes in Bernoulli trials. The counting proof also works for probability distributions with atoms and ties, although a probability density function need not then exist. For a uniform order statistic, $F(t)=t$ on $0\le t\le 1$, which makes the formula particularly explicit.

For independent survival times $T_1,T_2$ with cumulative distribution functions $F_1,F_2$, the probability both components have failed by time $t$ isThe probability at least one has failed isThe first equality uses independence of random variables; the second applies it to the complementary event that both survive. These are the distributions of the two extreme order statistics.

Marginal distributions alone do not determine these probabilities. Without independence, the Fréchet inequalities give $\max (0,F_1+F_2-1)\le P(\text{both})\le \min (F_1,F_2)$, and inclusion-exclusion gives $P(\text{at least one})=F_1+F_2-P(\text{both})$.

For an iid sample of size $n\ge 2$ from a continuous cumulative distribution function, the probability integral transform makes the transformed sample uniform. Integrating the joint density of its minimum and maximum gives range density $n(n-1)r^{n-2}(1-r)$ on $0<r<1$. Its distribution function is $n{r}^{n-1}-(n-1)r^n$. The result describes population content between the extreme order statistics, independently of the underlying continuous distribution.

The rank of an observation records where that observation lies among the order statistics of a statistical sample. When all values are distinct, $r_i=1+\#\{j:x_j<x_i\}$ and $x_i=x_{(r_i)}$. For $(0.7,0.1,0.9,0.4,0.2)$, the ranks of observations in original order are $(4,1,5,3,2)$: the first observation is fourth smallest, while the fourth observation is third smallest.

Ties require a convention. A tied block occupying sorted positions $a,\dots ,b$ can assign each member the average rank of an observation $(a+b)/2$, the minimum position $a$, or the maximum position $b$; an explicit rule can also break ties into distinct positions. R's official documentation describes these choices and uses average ranks by default. ^[ref].

For example, $(0.1,0.4,0.4,0.9)$ has order statistics $(0.1,0.4,0.4,0.9)$. The two $0.4$ observations occupy positions $2$ and $3$; average ranks of observations are $(1,2.5,2.5,4)$, whereas minimum-position ranks are $(1,2,2,4)$. A fractional average rank is a summary of tied positions, rather than an index of one order statistic. Without omissions, distinct ranks and average ranks sum to $n(n+1)/2$, since averaging each tied block preserves its sum; minimum-position ranks need not.

Wilcoxon signed-rank tests rank the absolute nonzero paired differences, while Wilcoxon rank sum tests rank the pooled observations from two samples; these are different rankings.

For independent and identically distributed random variables, suppose normalized sample maxima have limiting distribution function $G$. At a threshold $a_{n}x+b_n$ with $G(x)>0$, the exceedance count has limiting Poisson distribution with parameter $-\log G(x)$. The $r$th largest observation lies below the threshold exactly when at most $r-1$ observations strictly exceed it, including in samples with ties. Summing the first $r$ limiting Poisson probabilities gives the displayed limit for every fixed positive integer $r$. The equivalence follows from $F(a_{n}x+b_n{)}^n\to G(x)$ and $-\log (1-p)\sim p$ as $p\downarrow 0$.

For two independent random variables with the uniform distribution on $[0,1]$, put $U=\min (X,Y)$ and $V=\max (X,Y)$. Then $P(U>u)=(1-u{)}^2$, so $\mathbb{E}U=1/3$. Since $U+V=X+Y$ and $UV=XY$, $\mathbb{E}V=2/3$ and $\mathbb{E}(UV)=1/4$. Thus their covariance is $1/36$, although the original variables are independent. Rescaling the interval to $[a,b]$ multiplies the covariance by $(b-a{)}^2$.

For $n$ independent and identically distributed rate-$\lambda$ exponential random variables, let $M_0=0$ and $M_1<\cdots <M_n$ be their order statistics. The gaps $D_i=M_i-M_{i-1}$ are independent and have rates $(n-i+1)\lambda$. After the first clock rings, the memoryless property makes the surviving clocks fresh independent exponentials, independently of the elapsed minimum and the winning label. Induction gives the result. Equivalently, the ordered joint probability density is $n!{\lambda }^n\exp [-\lambda {\sum }_i{m}_i]$ on $0<m_1<\cdots <m_n$; changing to gaps gives a product of exponential densities because ${\sum }_i{m}_i={\sum }_i(n-i+1)D_i$.

For independent identically distributed observations with continuous cumulative distribution function $F$, fix the maximum $Y_n$ of the first $n\ge 1$ observations and let $\tau$ be the first subsequent observation exceeding it. The probability integral transform gives $U=F(Y_n)$ density $n{u}^{n-1}$ on $(0,1)$. Conditional on $U=u$, $\tau$ has a geometric distribution of parameter $1-u$. ThereforeThe masses sum to one, so the waiting time is finite almost surely, but the tail-sum formula for expectation gives $E\tau =\infty$. These conclusions require only continuity of $F$, not a density or a strictly increasing distribution function.

For two independent rate-$\lambda >0$ exponential distributions, set $U=\min (X,Y)$ and $V=\max (X,Y)$. Summing the two ordering branches gives joint probability density $2{\lambda }^2{e}^{-\lambda (2u+d)}$ for $(U,d=V-U)$ with $u,d>0$. It factors into independent exponential probability density functions. Thus $V$ is distributed as $X+Y/2$, with expected value $3/(2\lambda )$ and variance $5/(4{\lambda }^2)$. This spacing result is the order-statistic manifestation of the memorylessness of the exponential distribution.

Independence factors the events that both variables exceed a threshold or both lie below it. This gives the two cumulative distribution functions above, including for distributions with atoms. The minimum formula is most naturally expressed through survival probabilities, while the maximum formula uses the CDFs directly.

Descending order statistics list a sample from greatest to least. If $V_{(1)}\le \cdots \le V_{(n)}$ uses the usual increasing convention, then $V_{[k]}=V_{(n-k+1)}$. This notation distinguishes the next-highest value used by revenue equivalence from the second-smallest sample value.

For independent and identically distributed random variables with distribution function $F$, the sample maximum $M_n={\max }_{1\le i\le n}{X}_i$ has distribution function $F(x{)}^n$.

For observations $X_1,\dots ,X_n$, the nearest neighbour distance of order $k$ at $x$ is the $k$th order statistic of the distances $|X_i-x|$. An atomless distance distribution function ensures ties occur with probability zero.

For independent and identically distributed random variables with continuous distance distribution function $p_x$, the probability integral transform makes the probability content of the order-$k$ nearest ball a uniform order statistic, with the Beta distribution $\mathrm{Beta}(k,n+1-k)$.

For a strictly positive probability density function with Lipschitz bound $L$, $p_x(r)={\int }_{x-r}^{x+r}f(y)dy$ satisfies $|p_x(r)-2rf(x)|\le L{r}^2$. If $0<s<1$ and $s\le f(x{)}^2/L$, monotonicity gives $p_x^{-1}(s)\le s/f(x)$ and hence $|2f(x)p_x^{-1}(s)-s|\le L{s}^2/f(x{)}^2$. The Lipschitz density height bound prevents extending this local argument to every $s\in (0,1)$ by assuming $f(x)\ge \sqrt{L}$ for a strictly positive density.

For independent and identically distributed random variables $U_1,\dots ,U_n$ with the continuous uniform distribution on $(0,1)$, the $r$th order statistic has Beta distributionIts probability density function, mean, and variance areThe probability density function is zero outside $[0,1]$; values assigned to its endpoints do not change any probability. Peter Kempthorne's MIT lecture notes derive the uniform order statistic law and these moments. ^[ref].

For $n=5$, the minimum, sample median, and sample maximum correspond to $r=1,3,5$. Their probability density functions are $5(1-t{)}^4$, $30t^2(1-t{)}^2$, and $5t^4$, respectively. The sample median therefore has Beta distribution $\mathrm{Beta}(3,3)$, mean $1/2$, and variance $1/28\approx 0.0357143$. Its cumulative distribution function isFor instance, $\mathbb{P}(U_{(3)}\le 1/4)=53/512\approx 0.103516$. The mean of the minimum is $1/6$, and the mean of the sample maximum is $5/6$. The fixed observed sample median $0.4$ in the order statistic example is one possible outcome; $1/2$ is the average over repeated statistical samples from this uniform distribution.

Each curve has area one. The extreme order statistics favor the ends, while the sample median favors the center. The endpoint density height $5$ is legitimate: the probability density function gives area per unit length, rather than point probability. In particular, a continuous uniform distribution has zero probability of producing an endpoint.

For a short proof, the binomial distribution counting identity under order statistic gives $\mathbb{P}(U_{(r)}\le t)={\sum }_{k=r}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)t^k(1-t{)}^{n-k}$. Taking its derivative cancels consecutive terms, leaving the displayed probability density function. Recognize its normalizing factorial coefficient as that of the Beta distribution, then substitute $\alpha =r$, $\beta =n+1-r$ into the Beta distribution mean and variance formulas. Although the original observations are independent, their order statistics generally are dependent; see the positive covariance of two uniform order statistics.

For independent and identically distributed random variables $U_i$ with the continuous uniform distribution on $[0,1]$, let $M_n={\max }_{1\le i\le n}{U}_i$. Its cumulative distribution function is $x^n$ on $[0,1]$, so $M_n\stackrel{\mathrm{d}}{\to }1$. The endpoint error has a nonconstant limiting probability distribution: for fixed $z\ge 0$ and $n\ge z$,This survival function gives the displayed exponential distribution limit. More generally, for observations uniform on $[a,b]$, $n(b-M_n)/(b-a)$ has the same limit. The scaling identifies an error of order $1/n$, in contrast to the $1/\sqrt{n}$ fluctuations of a typical sample mean with nonzero finite variance.

Independent and identically distributed random variables with a continuous probability distribution realize each of their possible strict orderings with equal probability.

For independent and identically distributed random variables with a continuous probability distribution, let $N\ge 2$ be the index of the first increase. The event $N\ge n$ requires the first $n-1$ observations to be decreasing; symmetry among their $(n-1)!$ possible strict orders gives probability $1/(n-1)!$ for $n\ge 2$. Subtracting successive tails gives the displayed mass function for $r\ge 2$. The tails tend to zero, so $N$ is finite almost surely. The tail-sum formula for expectation gives $\mathbb{E}N=1+{\sum }_{j\ge 1}1/j!=e$, independently of the continuous sampling law.