U-statistic

In statistical theory, a U-statistic is a class of statistics defined as the average over the application of a given function applied to all tuples of a fixed size. The letter "U" stands for unbiased. In elementary statistics, U-statistics arise naturally in producing minimum-variance unbiased estimators.

Contents

• History
• Definition
• Examples
• See also
• Notes
• References

The theory of U-statistics allows a minimum-variance unbiased estimator to be derived from each unbiased estimator of an estimable parameter (alternatively, statistical functional ) for large classes of probability distributions. ^{[1] [2]} An estimable parameter is a measurable function of the population's cumulative probability distribution: For example, for every probability distribution, the population median is an estimable parameter. The theory of U-statistics applies to general classes of probability distributions.

History

Many statistics originally derived for particular parametric families have been recognized as U-statistics for general distributions. In non-parametric statistics, the theory of U-statistics is used to establish for statistical procedures (such as estimators and tests) and estimators relating to the asymptotic normality and to the variance (in finite samples) of such quantities. ^[3] The theory has been used to study more general statistics as well as stochastic processes, such as random graphs. ^{[4] [5] [6]}

Suppose that a problem involves independent and identically-distributed random variables and that estimation of a certain parameter is required. Suppose that a simple unbiased estimate can be constructed based on only a few observations: this defines the basic estimator based on a given number of observations. For example, a single observation is itself an unbiased estimate of the mean and a pair of observations can be used to derive an unbiased estimate of the variance. The U-statistic based on this estimator is defined as the average (across all combinatorial selections of the given size from the full set of observations) of the basic estimator applied to the sub-samples.

Pranab K. Sen (1992) provides a review of the paper by Wassily Hoeffding (1948), which introduced U-statistics and set out the theory relating to them, and in doing so Sen outlines the importance U-statistics have in statistical theory. Sen says, ^[7] “The impact of Hoeffding (1948) is overwhelming at the present time and is very likely to continue in the years to come.” Note that the theory of U-statistics is not limited to ^[8] the case of independent and identically-distributed random variables or to scalar random-variables. ^[9]

Definition

The term U-statistic, due to Hoeffding (1948), is defined as follows.

Let ${\displaystyle K}$ be either the real or complex numbers, and let ${\displaystyle f\colon (K^{d})^{r}\to K}$ be a ${\displaystyle K}$-valued function of ${\displaystyle r}$${\displaystyle d}$-dimensional variables. For each ${\displaystyle n\geq r}$ the associated U-statistic ${\displaystyle f_{n}\colon (K^{d})^{n}\to K}$ is defined to be the average of the values ${\displaystyle f(x_{i_{1}},\dotsc ,x_{i_{r}})}$ over the set ${\displaystyle I_{r,n}}$ of ${\displaystyle r}$-tuples of indices from ${\displaystyle \{1,2,\dotsc ,n\}}$ with distinct entries. Formally,

${\displaystyle f_{n}(x_{1},\dotsc ,x_{n})={\frac {1}{\prod _{i=0}^{r-1}(n-i)}}\sum _{(i_{1},\dotsc ,i_{r})\in I_{r,n}}f(x_{i_{1}},\dotsc ,x_{i_{r}})}$.

In particular, if ${\displaystyle f}$ is symmetric the above is simplified to

${\displaystyle f_{n}(x_{1},\dotsc ,x_{n})={\frac {1}{\binom {n}{r}}}\sum _{(i_{1},\dotsc ,i_{r})\in J_{r,n}}f(x_{i_{1}},\dotsc ,x_{i_{r}})}$,

where now ${\displaystyle J_{r,n}}$ denotes the subset of ${\displaystyle I_{r,n}}$ of increasing tuples.

Each U-statistic ${\displaystyle f_{n}}$ is necessarily a symmetric function.

U-statistics are very natural in statistical work, particularly in Hoeffding's context of independent and identically distributed random variables, or more generally for exchangeable sequences, such as in simple random sampling from a finite population, where the defining property is termed ‘inheritance on the average’.

Fisher's k-statistics and Tukey's polykays are examples of homogeneous polynomial U-statistics (Fisher, 1929; Tukey, 1950).

For a simple random sample φ of size n taken from a population of size N, the U-statistic has the property that the average over sample values ƒ_n(xφ) is exactly equal to the population value ƒ_N(x).^{[ clarification needed ]}

Examples

Some examples: If ${\displaystyle f(x)=x}$ the U-statistic ${\displaystyle f_{n}(x)={\bar {x}}_{n}=(x_{1}+\cdots +x_{n})/n}$ is the sample mean.

If ${\displaystyle f(x_{1},x_{2})=|x_{1}-x_{2}|}$, the U-statistic is the mean pairwise deviation ${\displaystyle f_{n}(x_{1},\ldots ,x_{n})=2/(n(n-1))\sum _{i>j}|x_{i}-x_{j}|}$, defined for ${\displaystyle n\geq 2}$.

If ${\displaystyle f(x_{1},x_{2})=(x_{1}-x_{2})^{2}/2}$, the U-statistic is the sample variance ${\displaystyle f_{n}(x)=\sum (x_{i}-{\bar {x}}_{n})^{2}/(n-1)}$ with divisor ${\displaystyle n-1}$, defined for ${\displaystyle n\geq 2}$.

The third ${\displaystyle k}$-statistic ${\displaystyle k_{3,n}(x)=\sum (x_{i}-{\bar {x}}_{n})^{3}n/((n-1)(n-2))}$, the sample skewness defined for ${\displaystyle n\geq 3}$, is a U-statistic.

The following case highlights an important point. If ${\displaystyle f(x_{1},x_{2},x_{3})}$ is the median of three values, ${\displaystyle f_{n}(x_{1},\ldots ,x_{n})}$ is not the median of ${\displaystyle n}$ values. However, it is a minimum variance unbiased estimate of the expected value of the median of three values, not the median of the population. Similar estimates play a central role where the parameters of a family of probability distributions are being estimated by probability weighted moments or L-moments.

See also

• V-statistic

Notes

Related Research Articles

In statistics, an estimator is a rule for calculating an estimate of a given quantity based on observed data: thus the rule, the quantity of interest and its result are distinguished. For example, the sample mean is a commonly used estimator of the population mean.

In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value when data is orderly arranged. The basic feature of the median in describing data compared to the mean is that it is not skewed by a small proportion of extremely large or small values (outlier), and therefore provides a better representation of the center. Median income, for example, may be a better way to describe the center of an income distribution because increases in the largest incomes alone have no effect on median while the average of the distribution is influenced. For this reason, the median is of central importance in robust statistics.

In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon in terms of its sample space and the probabilities of events.

In statistics, the standard deviation is a measure of the amount of variation of a random variable expected about its mean. A low standard deviation indicates that the values tend to be close to the mean of the set, while a high standard deviation indicates that the values are spread out over a wider range.

In probability theory and statistics, skewness is a measure of the asymmetry of the probability distribution of a real-valued random variable about its mean. The skewness value can be positive, zero, negative, or undefined.

In probability theory and statistics, variance is the expected value of the squared deviation from the mean of a random variable. The standard deviation is obtained as the square root of the variance. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers is spread out from their average value. It is the second central moment of a distribution, and the covariance of the random variable with itself, and it is often represented by , , , , or .

In statistics, point estimation involves the use of sample data to calculate a single value which is to serve as a "best guess" or "best estimate" of an unknown population parameter. More formally, it is the application of a point estimator to the data to obtain a point estimate.

In statistics, completeness is a property of a statistic in relation to a parameterised model for a set of observed data.

In statistics, the mean squared error (MSE) or mean squared deviation (MSD) of an estimator measures the average of the squares of the errors—that is, the average squared difference between the estimated values and the actual value. MSE is a risk function, corresponding to the expected value of the squared error loss. The fact that MSE is almost always strictly positive is because of randomness or because the estimator does not account for information that could produce a more accurate estimate. In machine learning, specifically empirical risk minimization, MSE may refer to the empirical risk, as an estimate of the true MSE.

In statistics, the Lehmann–Scheffé theorem is a prominent statement, tying together the ideas of completeness, sufficiency, uniqueness, and best unbiased estimation. The theorem states that any estimator that is unbiased for a given unknown quantity and that depends on the data only through a complete, sufficient statistic is the unique best unbiased estimator of that quantity. The Lehmann–Scheffé theorem is named after Erich Leo Lehmann and Henry Scheffé, given their two early papers.

In statistics, a consistent estimator or asymptotically consistent estimator is an estimator—a rule for computing estimates of a parameter θ₀—having the property that as the number of data points used increases indefinitely, the resulting sequence of estimates converges in probability to θ₀. This means that the distributions of the estimates become more and more concentrated near the true value of the parameter being estimated, so that the probability of the estimator being arbitrarily close to θ₀ converges to one.

Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value affects the distribution of the measured data. An estimator attempts to approximate the unknown parameters using the measurements. In estimation theory, two approaches are generally considered:

In statistics a minimum-variance unbiased estimator (MVUE) or uniformly minimum-variance unbiased estimator (UMVUE) is an unbiased estimator that has lower variance than any other unbiased estimator for all possible values of the parameter.

In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution wherein a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n. Another way of saying "discrete uniform distribution" would be "a known, finite number of outcomes equally likely to happen".

Probability theory and statistics have some commonly used conventions, in addition to standard mathematical notation and mathematical symbols.

The mean absolute difference (univariate) is a measure of statistical dispersion equal to the average absolute difference of two independent values drawn from a probability distribution. A related statistic is the relative mean absolute difference, which is the mean absolute difference divided by the arithmetic mean, and equal to twice the Gini coefficient. The mean absolute difference is also known as the absolute mean difference and the Gini mean difference (GMD). The mean absolute difference is sometimes denoted by Δ or as MD.

Bootstrapping is any test or metric that uses random sampling with replacement, and falls under the broader class of resampling methods. Bootstrapping assigns measures of accuracy to sample estimates. This technique allows estimation of the sampling distribution of almost any statistic using random sampling methods.

In statistics, the bias of an estimator is the difference between this estimator's expected value and the true value of the parameter being estimated. An estimator or decision rule with zero bias is called unbiased. In statistics, "bias" is an objective property of an estimator. Bias is a distinct concept from consistency: consistent estimators converge in probability to the true value of the parameter, but may be biased or unbiased; see bias versus consistency for more.

In statistics, efficiency is a measure of quality of an estimator, of an experimental design, or of a hypothesis testing procedure. Essentially, a more efficient estimator needs fewer input data or observations than a less efficient one to achieve the Cramér–Rao bound. An efficient estimator is characterized by having the smallest possible variance, indicating that there is a small deviance between the estimated value and the "true" value in the L2 norm sense.

V-statistics are a class of statistics named for Richard von Mises who developed their asymptotic distribution theory in a fundamental paper in 1947. V-statistics are closely related to U-statistics introduced by Wassily Hoeffding in 1948. A V-statistic is a statistical function defined by a particular statistical functional of a probability distribution.

References

• Borovskikh, Yu. V. (1996). U-statistics in Banach spaces. Utrecht: VSP. pp. xii+420. ISBN   90-6764-200-2. MR   1419498.
• Cox, D. R., Hinkley, D. V. (1974) Theoretical statistics. Chapman and Hall. ISBN   0-412-12420-3
• Fisher, R. A. (1929) Moments and product moments of sampling distributions. Proceedings of the London Mathematical Society, 2, 30:199–238.
• Hoeffding, W. (1948) A class of statistics with asymptotically normal distributions. Annals of Statistics, 19:293–325. (Partially reprinted in: Kotz, S., Johnson, N. L. (1992) Breakthroughs in Statistics, Vol I, pp 308–334. Springer-Verlag. ISBN   0-387-94037-5)
• Koroljuk, V. S.; Borovskich, Yu. V. (1994). Theory of U-statistics. Mathematics and its Applications. Vol. 273 (Translated by P. V. Malyshev and D. V. Malyshev from the 1989 Russian original ed.). Dordrecht: Kluwer Academic Publishers Group. pp. x+552. ISBN   0-7923-2608-3. MR   1472486.
• Lee, A. J. (1990) U-Statistics: Theory and Practice. Marcel Dekker, New York. pp320 ISBN   0-8247-8253-4
• Sen, P. K. (1992) Introduction to Hoeffding (1948) A Class of Statistics with Asymptotically Normal Distribution. In: Kotz, S., Johnson, N. L. Breakthroughs in Statistics, Vol I, pp 299–307. Springer-Verlag. ISBN   0-387-94037-5.
• Serfling, Robert J. (1980). Approximation theorems of mathematical statistics . New York: John Wiley and Sons. ISBN   0-471-02403-1.
• Tukey, J. W. (1950). "Some Sampling Simplified". Journal of the American Statistical Association . 45 (252): 501–519. doi:10.1080/01621459.1950.10501142.
• Halmos, P. (1946). "The Theory of Unbiased Estimation". Annals of Mathematical Statistics . 1 (17): 34–43. doi: 10.1214/aoms/1177731020 .