Order statistic
s 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.
≈ 14 min read
Order statistic. encyclopegia.org, snapshot enwiki-001375907550. /a/order-statistic
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
s 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. Given a sample of size n , the kth order statistic is denoted x_{(k)} , with 1 \le k \le n . 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.
s 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. Given a sample of size n , the kth order statistic is denoted x_{(k)} , with 1 \le k \le n . 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. \begin{align} x_{(1)} &= 3 \\ x_{(2)} &= 6 \\ x_{(3)} &= 7 \\ x_{(4)} &= 9 \end{align} 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 , the 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 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 of observations is odd. More precisely, if for some integer , then the sample median is X_{(m+1)} and so is an order statistic.
On the other hand, when is even, 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.
F_{X_{(r)}}(x) = \sum_{j=r}^{n} \binom{n}{j} \left[ F_{X}(x) \right]^{j} \left[ 1 - F_{X}(x) \right]^{n-j} The proof of this formula is pure combinatorics: for the r th order statistic to be \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 \leq x , there has to be j samples \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 \binom{n}{j} different ways of choosing which of the n samples are of the \leq x kind. The corresponding probability density function may be derived from this result, and is found to be f_{X_{(r)}}(x) = \frac{n!}{(r-1)!(n-r)!} f_{X}(x) \left[ F_{X}(x) \right]^{r-1} \left[ 1 - F_{X}(x) \right]^{n-r}.
Moreover, there are two special cases, which have CDFs that are easy to compute. F_{X_{(n)}}(x) = \Pr(\max\{\,X_1,\ldots,X_n\,\} \leq x) = [ F_{X}(x) ]^n F_{X_{(1)}}(x) = \Pr(\min\{\,X_1,\ldots,X_n\,\} \leq x) = 1- [ 1 - F_{X}(x) ]^n Which can be derived by careful consideration of probabilities.
We assume throughout this section that X_1, X_2, \ldots, X_n are random samples 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)}) .
The probability density function of the order statistic U_{(k)} is equal to f_{U_{(k)}}(u)={n!\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. U_{(k)} \sim \operatorname{Beta}(k,n+1\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!\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). f_{U_{(i)},U_{(j)}}(u,v) = n!{u^{i-1}\over (i-1)!}{(v-u)^{j-i-1}\over(j-i-1)!}{(1-v)^{n-j}\over (n-j)!} 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}) = 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 . It is also related with another particularity of order statistics of uniform random variables: It follows from the BRS-inequality that the maximum expected number of uniform U(0,1] random variables one can choose from a sample of size n with a sum up not exceeding 0 is bounded above by \sqrt{2sn} , which is thus invariant on the set of all s, n with constant product s n . Using the above formulas, one can derive the distribution of the range of the order statistics, that is the distribution of U_{(n)}-U_{(1)} , i.e. maximum minus the minimum.
More generally, for n\geq k>j\geq 1 , U_{(k)}-U_{(j)} also has a beta distribution: U_{(k)}-U_{(j)}\sim \operatorname{Beta}(k-j, n-(k-j)+1) From these formulas we can derive the covariance between two order statistics: \operatorname{Cov}(U_{(k)},U_{(j)})=\frac{j(n-k+1)}{(n+1)^2(n+2)} The formula follows from noting that \begin{align} \operatorname{Var}(U_{(k)}-U_{(j)}) &=\operatorname{Var}(U_{(k)}) + \operatorname{Var}(U_{(j)})-2\cdot \operatorname{Cov}(U_{(k)},U_{(j)}) \\[1ex] &=\frac{k(n-k+1)}{(n+1)^2(n+2)}+\frac{j(n-j+1)}{(n+1)^2(n+2)}-2\cdot \operatorname{Cov}(U_{(k)},U_{(j)}) \end{align} and comparing that with \operatorname{Var}(U)=\frac{(k-j)(n-(k-j)+1)}{(n+1)^2(n+2)} where U\sim \operatorname{Beta}(k-j,n-(k-j)+1) , which is the actual distribution of the difference. 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 X_{(i)} \stackrel{d}{=} \frac{1}{\lambda}\left( \sum_{j=1}^i \frac{Z_j}{n-j+1} \right) where the Z j are i.i.d. standard exponential random variables (i.e. with rate parameter 1).
This result was first published by Alfréd Rényi. 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 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. {6\choose 3}(1/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](1/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.
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 −1 (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 −1 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.
Further research led in the 1960s to the Bahadur representation which provides information about the error bounds. The convergence to normal distribution also holds in a stronger sense, such as convergence in relative entropy or KL divergence. 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 σ 2 /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. 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. I(X_{(r)}; X_{(m)}) = I(U_{(r)}; U_{(m)}), In other words, mutual information is independent of the parent distribution.
For discrete random variables, the equality need not to hold and we only have I(X_{(r)}; X_{(m)}) \le I(U_{(r)}; U_{(m)}), The mutual information between uniform order statistics is given by I(U_{(r)}; U_{(m)}) = T_{m-1} + T_{n-r} - T_{m-r+1} - T_n where T_k = \log(k!) - kH_k where H_k is the k -th harmonic number. Moments of the distribution for the first order statistic can be used to develop a non-parametric density estimator.
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^*) = \frac{g_Y(0)}{2} .
The expected value of the first order statistic Y_{(1)} given a sample of N total observations yields, E(Y_{(1)}) = \frac{1}{(N+1) g(0)} + \frac{1}{(N+1)(N+2)} \int_{0}^{1} Q(z) \delta_{N+1}(z) \, dz where Q is the quantile function associated with the distribution g_{Y} , and \delta_N(z) = (N+1)(1-z)^N . This equation in combination with a jackknifing technique becomes the basis for the following density estimation algorithm, Input: A sample of N observations. \{x_\ell\}_{\ell=1}^M points of density evaluation. Tuning parameter a \in (0,1) (usually 1/3).
Output: \{\hat{f}_\ell\}_{\ell=1}^M estimated density at the points of evaluation. 1: Set m_N = \operatorname{round}(N^{1-a}) 2: Set s_N = \frac{N}{m_N} 3: Create an s_N \times m_N matrix M_{ij} which holds m_N subsets with s_N observations each. 4: Create a vector \hat{f} to hold the density evaluations.
5: for \ell = 1 \to M do 6: for k = 1 \to m_N do 7: Find the nearest distance d_{\ell k} to the current point x_\ell within the k th subset 8: end for 9: Compute the subset average of distances to x_\ell:d_\ell = \sum_{k=1}^{m_N} \frac{d_{\ell k}}{m_N} 10: Compute the density estimate at x_\ell:\hat{f}_\ell = \frac{1}{2 (1+ s_N) d_\ell} 11: end for 12: return \hat{f} In contrast to the bandwidth/length based tuning parameters for histogram and kernel based approaches, the tuning parameter for the order statistic based density estimator is the size of sample subsets. Such an estimator is more robust than histogram and kernel based approaches, for example densities like the Cauchy distribution (which lack finite moments) can be inferred without the need for specialized modifications such as IQR based bandwidths.
This is because the first moment of the order statistic always exists if the expected value of the underlying distribution does, but the converse is not necessarily true. \begin{align} p_1 &= \Pr(X x) = 1-F(x). \end{align} The cumulative distribution function of the k^\text{th} order statistic can be computed by noting that \begin{align} \Pr(X_{(k)}\leq x)& = \Pr(\text{there are at least }k\text{ observations less than or equal to }x) ,\\ & = \Pr(\text{there are at most }n-k\text{ observations greater than }x) ,\\ & = \sum_{j=0}^{n-k} \binom{n}{j}p_3^j(p_1+p_2)^{n-j} . \end{align} Similarly, P(X_{(k)} is given by \begin{align} \Pr(X_{(k)} Note that the probability mass function of X_{(k)} is just the difference of these values, that is to say \begin{align} \Pr(X_{(k)}=x) &= \Pr(X_{(k)}\leq x)-\Pr(X_{(k)}
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375907550 under CC BY-SA 4.0; modifications have been made.