[Edit]

top

6, 9, 3, 8,

$x\_1=6;\; x\_2=9;\; x\_3=3;\; x\_4=8,$

$x\_=3;\; x\_=6;\; x\_=8;\; x\_=9,$

$X\_=min$

$X\_=max.$

$=\; X\_-X\_.$

top

top

$f\_(x)=\; F\_(x)$

---

top

{d over dx}Pleft(X_{(k)}leq x
ight)=P(mathrm mathrm k mathrm mathrm n Xmathrm mathrmleq x)

$=P(geq\; k\; mathrm\; mathrm\; n\; mathrm)=sum\_^nP(X\_1leq\; x)^j(1-P(X\_1leq\; x))^$

$=sum\_^n\; F(x)^j\; (1-F(x))^$

$=sum\_^n$

left(jF(x)^f(x)(1-F(x))^
+F(x)^j (n-j)(1-F(x))^(-f(x))
ight)

$=sum\_^nleft(nF(x)^(1-F(x))^\; -\; n\; F(x)^j(1-F(x))^$

ight)f(x)

$=nf(x)left(sum\_^$

F(x)^j (1-F(x))^
- sum_^n
F(x)^j (1-F(x))^
ight)

and the sum above telescopes, so that all terms cancel except the first and the last:

$=nf(x)left(\; F(x)^\; (1-F(x))^$

- underbrace
ight)

and the term over the underbrace is zero, so:

$=nf(x)\; F(x)^\; (1-F(x))^$

$=\; F(x)^\; (1-F(x))^\; f(x).$

---

top

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 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\_,\; X\_,\; ldots,\; X\_$ 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\_=F\_X(X\_)$.

---

top

The order statistics of the uniform distribution

The probability of the order statistic $U\_$ falling in the interval $u,u+du$ is equal to

$u^(1-u)^du+O(du^2),$

that is, the kth order statistic of the uniform distribution is a Beta random variable.

$U\_\; sim\; B(k,n+1-k).$

The proof of these statements is as follows. In order for $U\_$ 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)

$u^kcdot\; ducdot(1-u-du)^$

and the result follows.

---

top

Joint distributions

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,v)du,dv=\; n!,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\_,u\_,ldots,u\_),du\_1,cdots,du\_n\; =\; n!\; ,\; du\_1cdots\; 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

---

top

Application: confidence intervals for quantiles

An interesting question is how well the order statistics perform as estimators of the quantiles of the underlying distribution.

---

top

Estimating the median

The simplest case to consider is how well the sample median estimates the population median.

---

top

A small-sample-size example

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

$2^\; =\; 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\{6choose\; 2\}+\{6choose\; 3\}+\{6choose\; 4\}\; ight2^\; =\; 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.

If the distribution is known to be symmetric and have finite variance (as is the case for the normal distribution) the population mean equals the median, and the sample mean has much better confidence intervals than the sample median. This is an illustration of the relative weakness of distribution-free statistical methods. On the other hand, using methods tailored to the wrong distribution can lead to large systematic errors in estimation.

---

top

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).

---

top

See also

Quantile

Median

Rankit

Box plot

Fisher-Tippett distribution