In statistics, the kth order statistic of a statistical sample is equal to its kth-smallest value. 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
where the subscript i in 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
where the subscript (i) enclosed in parentheses indicates the ith order statistic of the sample.
The first order statistic (or smallest order statistic) is always the minimum of the sample, that is,
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 nth order statistic (or largest order statistic) is the maximum, that is,
The sample range is the difference between the maximum and minimum. It is a function of the order statistics:
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 integer m, then the sample median is and so is an order statistic. On the other hand, when n is even, n = 2m and there are two middle values, and , 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.
Given any random variables X1, X2..., Xn, the order statistics X(1), X(2), ..., X(n) are also random variables, defined by sorting the values (realizations) of X1, ..., Xn in increasing order.
When the random variables X1, X2..., Xn form a sample they are independent and identically distributed. This is the case treated below. In general, the random variables X1, ..., Xn 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
Order statistics sampled from a uniform distribution
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 is a random sample drawn from a continuous distribution with cdf . Denoting we obtain the corresponding random sample from the standard uniform distribution. Note that the order statistics also satisfy .
The probability of the order statistic falling in the interval is equal to
that is, the kth order statistic of the uniform distribution is a Beta random variable.
The proof of these statements is as follows. For 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 , so we have to calculate the probability that exactly k − 1, 1 and n − k observations fall in the intervals , and respectively. This equals (refer to multinomial distribution for details)
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
which is (up to terms of higher order than ) the probability that i − 1, 1, j − 1 − i, 1 and n − j sample elements fall in the intervals , , , , 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:
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 .
Order statistics sampled from an exponential distribution
For random samples from an exponential distribution with parameter λ the order statistics X(i) for i = 1,2,3, ..., n each have distribution
where the Zj are iid standard exponential random variables (i.e. with rate parameter 1). This result was first published by Alfréd Rényi.
Order statistics sampled from an Erlang distribution
The Laplace transform of order statistics sampled from an Erlang distribution via a path counting method.
The joint distribution of the order statistics of an absolutely continuous distribution
If FX is absolutely continuous, it has a density such that , and we can use the substitutions
to derive the following probability density functions (pdfs) for the order statistics of a sample of size n drawn from the distribution of X:
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
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
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 pth sample quantile is asymptotically normally distributed, since it is approximated by
For a general distribution F with a continuous non-zero density at F −1(p), a similar asymptotic normality applies:
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 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 σ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.
It can be shown that
Introducing Higher Order Statistics (HOS) for the Detection of Nonlinearities
S McLaughlin, A Stogioglou and J Fackrell
Department of Electrical Engineering, University of Edinburgh
- What are HOS ?
- Why use HOS ?
- Frequency domain methods for detecting nonlinearities
- Getting more information
- Some HOS jargon
IntroductionEngineering judgement concerning the predictability of a signal is often based on an examination of the signal spectrum. The conclusion is then drawn that if a signal has a flat or near-to-flat spectral density that the quality of the prediction will be poor. While this line of reasoning can provide useful guidelines in the design of linear predictive systems it is not true in general not least because it ignores the existence of purely deterministic mechanisms which generate signals with flat or near-to-flat spectral densities.
Speech or music signals are generated mechanically by systems with nonlinear dynamics. If the prediction and coding quality of such signals is to be improved then more of the information available in the signal must be used : the signal higher order statistics (HOS) must be exploited.
The aim of this article is to introduce HOS to a wide audience (assuming basic knowledge of signal processing and statistics), and to outline some of the reasons why they can be useful in practical applications.
History of Higher Order Statistics (HOS)Several key papers in HOS were published in the 1960's, but most of these papers took a statistical and theoretical viewpoint of the subject. It was not until the 1970's the people started to apply HOS techniques to real signal processing problems. The last 15 years has seen a revival of interest in HOS techniques, and there is now a growing number of researchers around the world working in this field.
In recent years the field of HOS has continued its expansion, and applications have been found in fields as diverse as economics, speech, seismic data processing, plasma physics and optics. Many signal processing conferences (ICASSP, EUSIPCO) now have sessions specifically for HOS, and an IEEE Signal Processing Workshop on HOS has been held every two years since 1989 (the most recent one took place in June 1995 in Spain).
What are HOS ?HOS measures are extensions of second-order measures (such as the autocorrelation function and power spectrum) to higher orders. The second-order measures work fine if the signal has a Gaussian (Normal) probability density function, but as mentioned above, many real-life signals are non-Gaussian. The easiest way to introduce the HOS measures is just to show some definitions, so that the reader can see how they are related to the familiar second-order measures. Here are definitions for the time-domain and frequency-domain third-order HOS measures, assuming a zero-mean, discrete signal ,
Time domain measuresIn the time domain, the second order measure is the autocorrelation function
where is the expectation operator.
The third-order measure is called the third-order moment
Note that the third-order moment depends on two independent lags and . Higher order moments can be formed in a similar way by adding lag terms to the above equation. The signal cumulants can be easily derived from the moments.
Frequency domainIn the frequency domain the second-order measure is called the power spectrum , and it can be calculated in two ways:
- Take a Discrete Fourier Transform (DFT) of the autocorrelation function ;
- Or: Multiply together the signal Fourier Transform with its complex conjugate ;
- Take a Double Discrete Fourier Transform (DDFT) of the third-order cumulant ;
- Or: Form a product of Fourier Transforms at different frequencies ;
Now just as the second-order measures are related to the signal variance so the third-order measures (third-order cumulant and bispectrum) are related to the signal skewness, the fourth-order measures (fourth-order cumulant and trispectrum) are related to the signal kurtosis, and higher-order measures are related to higher-order moments of the signal.
Why use HOS ?Some of the key advantages to such techniques over traditional second-order techniques are
- Second-order measures (such as the power spectrum and autocorrelation functions) contain no phase information. As a consequence of this
- non-minimum phase signals cannot be correctly identified by 2nd-order techniques. This is important in the field of linear processes, which will not be discussed in this article.
- certain types of phase coupling (associated with nonlinearities) cannot be correctly identified using 2nd order techniques.
- Any Gaussian signal is completely characterised by its mean and variance. Consequently the HOS of Gaussian signals are either zero (e.g. the 3rd order moment of a Gaussian signal is zero), or contain redundant information. Many signals encountered in practice have non-zero HOS, and many measurement noises are Gaussian, and so in principle the HOS are less affected by Gaussian background noise than the 2nd order measures. (e.g. the power spectrum of a deterministic signal plus Gaussian noise is very different from the power spectrum of the signal alone. However the bispectrum of the signal + noise is, at least in principle, the same as that of the signal).
Frequency domain methods for detecting nonlinearitiesNonparametric frequency domain methods (such as the power spectrum) remain popular in fields where signals are of an unkown type, as a rough-and-ready tool for investigation. In the field of HOS there are extensions to the familiar power spectrum at 3rd, 4th and higher orders. These "Higher Order Spectra", or "Polyspectra" provide supplementary information to the power spectrum. The 3rd order polyspectrum is the easiest to compute, and hence the most popular, and is called the bispectrum. The 4th order polyspectrum is called the trispectrum. These can be estimated in a way similar to the power spectrum, but more data is usually needed to get reliable estimates. For this reason it is often not practicable to compute the polspectra of high orders. Closely related to the bispectrum is the 3rd-order coherence measure, the bicoherence. An example of a bicoherence plot is shown in the Figure below.
Figure 1 - an example of a bicoherence magnitude plot of a male vowel sound. The horizontal and vertical scales are frequency scales k and l respectively, in kHz.
It is evident that the bicoherence has two independent frequency axes k and l, and that the bicoherence magnitude emerges from the frequency plane. We only consider the bicoherence in a small region of the k,l plane because of symmetry relations. The bicoherence has phase too, and under certain circumstances that needs to be examined too. The interpretation of the bicoherence varies depending on the type of signal under study.
- For stochastic wide-band signals, the level of the bicoherence gives a measure of the signal skewness (a statistical test for skewness based on the bispectrum was devised by Hinich in 1982).
- For deterministic signals, a peak in the bicoherence indicates the presence of Quadratic Phase Coupling (QPC), which is a specific type of nonlinearity.
Figure 2 - annotated bicoherence plot.
ConclusionsWe have attempted to give a brief overview of some of the ideas behind the use of HOS in signal processing. Key to these ideas is the fact that many signals in real life cannot be adequately modelled using the traditional second-order measures such as the power spectrum and autocorrelation function. Much has already been achieved, but there is still a great deal of work to do before HOS measures become as familiar and comprehensible as their second-order counterparts.
Getting More InformationFurther information about HOS can be obtained by visiting the HOS home page . This page contains links to research groups around the world with interests in HOS, as well as hos bibliographies and a noticeboard of forthcoming HOS events.
In Edinburgh, our own special areas of interest include HOS in Speech Signals, HOS for seismic deconvolution, Chaos in Speech, Nonlinear signal prediction. For more information on these areas, or general questions concerning this article, please contact
- Steve McLaughlin (any area of nonlinear signal processing).
- Achilleas Stogioglou (seismic deconvolution using parametric HOS methods),
- Justin Fackrell (detecting nonlinearities in speech using HOS).
Some HOS jargon
- moments Moments are statistical measures which characterise signal properties. We are used to using the mean and the variance (the first and second moments, respectively) to characterise a signal's probability distribution, but unless the signal is Gaussian (Normal) then moments of higher orders are needed to fully describe the distribution. In practice in HOS we usually use the cumulants rather than the moments (see below).
- cumulants The nth order cumulant is a function of the moments of orders up to (and including) n. For reasons of mathematical convenience, HOS equations/discussions most often deal with a signal's cumulants rather than the signal's moments.
- polyspectra This term is used to describe the family of all frequency-domain spectra, including the 2nd order. Most HOS work on polyspectra focusses attention on the bispectrum (third-order polyspectrum) and the trispectrum (fourth-order polyspectrum).
- bicoherence This is used to denote a normalised version of the bispectrum. The bicoherence takes values bounded between 0 and 1, which make it a convenient measure for quantifying the extent of phase coupling in a signal. The normalisation arises because of variance problems of the bispectral estimators for which there is insufficient space to explain (see Hinich 1982 for more details).
ReferencesThe number of papers published on HOS continues to rise each year. One of the most widely referenced papers is the tutorial paper by Mendel (referenced below). Below we also reference the first textbook on HOS, which was published in 1993.
J M MendelTutorial on Higher Order Statistics (Spectra) in signal processing and system theory: theoretical results and some applications Proceedings of the IEEE, 79(3), pp 278-305, March, 1991.
C L Nikias and A P PetropuluHigher-Order Spectra analysis PTR Prentice Hall, New Jersey, 1993.
M J HinichTesting for Gaussianity and linearity of a stationary time series Journal of Time Series Analysis,3(3), pp 169-176, 1982.
<< Move to UK Nonlinear NewsIssue Two index page
15 Sept. 1995