U-statistic
A u-statistic is a class of statistic defined as the average of a fixed-order function over all subsets of a random sample having the required size. The name abbreviates “unbiased statistic,” reflecting the construction’s association with unbiased estimation. U-statistics provide a unified representation for many estimators based on pairwise or higher-order comparisons, including the sample variance, measures of rank association, and several nonparametric test statistics.
The general theory was formulated by Wassily Hoeffding in 1948. Its central results describe unbiasedness, variance, projection onto sums of independent random variables, and asymptotic normality. Later developments connected the theory with empirical processes, resampling methods, and estimators whose first-order projections vanish.
Definition
Let (X_1,\ldots,X_n) be independent and identically distributed random variables with common distribution (F), and let
[ h:\mathcal X^m\longrightarrow \mathbb R ]
be a measurable function of (m) arguments, where (m\leq n). The function (h) is called a kernel. It is conventionally taken to be symmetric, since any nonsymmetric kernel can be replaced by its symmetrization,
[ h_s(x_1,\ldots,x_m)
\frac{1}{m!} \sum_{\pi} h(x_{\pi(1)},\ldots,x_{\pi(m)}), ]
where the sum ranges over the permutations of ({1,\ldots,m}).
The u-statistic generated by (h) is
[ U_n
\binom{n}{m}^{-1} \sum_{1\leq i_1<\cdots<i_m\leq n} h(X_{i_1},\ldots,X_{i_m}). ]
Thus (U_n) averages the kernel over every unordered subset of (m) observations. The integer (m) is the degree, or order, of the u-statistic. If
[ \theta(F)
\operatorname E_F[h(X_1,\ldots,X_m)] ]
exists, then
[ \operatorname E_F[U_n]=\theta(F). ]
Consequently, (U_n) is an unbiased estimator of the statistical functional (\theta(F)).
The definition uses subsets rather than independent repetitions of the entire (m)-observation experiment. Different kernel evaluations therefore share observations and are generally dependent. This dependence determines the finite-sample variance and distinguishes u-statistics from ordinary averages of independent terms.
Statistical interpretation
A parameter is u-estimable when it can be expressed as the expectation of a symmetric kernel involving a fixed number of independent observations. For such a parameter, the associated u-statistic uses all available subsets and introduces no arbitrary partition of the sample.
Among unbiased estimators based on a fixed sample size, a u-statistic has a minimum-variance property under the usual square-integrability assumptions. More precisely, if an unbiased estimator of (\theta(F)) exists from (m) observations and the model is sufficiently unrestricted, averaging that estimator over all (m)-subsets produces the corresponding u-statistic. This averaging is a form of Rao–Blackwellization with respect to the symmetric information in the sample.
The minimum-variance statement concerns unbiased estimators and does not imply minimum mean squared error among arbitrary estimators. A biased estimator can have lower mean squared error because its reduction in variance may exceed the squared bias it introduces.
Standard examples
The sample mean is the degree-one u-statistic with kernel
[ h(x)=x. ]
In this case,
[ U_n=\frac{1}{n}\sum_{i=1}^n X_i, ]
so ordinary averaging appears as the simplest member of the class.
The unbiased sample variance is a degree-two u-statistic. With kernel
[ h(x_1,x_2)=\frac{(x_1-x_2)^2}{2}, ]
the resulting statistic satisfies
[ \binom{n}{2}^{-1} \sum_{i<j}\frac{(X_i-X_j)^2}{2}
\frac{1}{n-1}\sum_{i=1}^n(X_i-\overline X)^2. ]
This identity expresses variance through average squared pairwise separation rather than through deviations from the sample mean.
A degree-two kernel also represents Kendall’s rank correlation coefficient. For observations ((X_i,Y_i)), its kernel compares the signs of (X_i-X_j) and (Y_i-Y_j). The resulting average measures the difference between concordant and discordant pairs.
Several classical nonparametric statistics are u-statistics or are closely related to them. Their kernels often encode comparisons between observations, while their asymptotic behavior follows from the same projection structure that governs smooth numerical kernels.
Hoeffding decomposition
The principal structural representation of a square-integrable u-statistic is the Hoeffding decomposition. Let
[ \theta=\operatorname E[h(X_1,\ldots,X_m)] ]
and define the first-order projection
[ h_1(x)
\operatorname E[h(x,X_2,\ldots,X_m)]-\theta. ]
Higher-order projection kernels are obtained recursively by subtracting (\theta) and all lower-order components from the corresponding conditional expectations. Each resulting component is degenerate in the sense that integrating out any one of its arguments gives zero.
The centered statistic then has an orthogonal decomposition of the form
[ U_n-\theta
\sum_{r=1}^{m} \binom{m}{r} \binom{n}{r}^{-1} \sum_{1\leq i_1<\cdots<i_r\leq n} h_r(X_{i_1},\ldots,X_{i_r}). ]
Orthogonality is understood in the Hilbert space (L^2(F^m)). Components of different orders have covariance zero, allowing the variance of (U_n) to be written as a sum of nonnegative contributions.
The leading term is
[ \frac{m}{n}\sum_{i=1}^n h_1(X_i). ]
When (h_1) is nonzero, this projection behaves like an average of independent random variables and ordinarily determines the limiting distribution. The remaining terms have smaller stochastic order under fixed (m) and finite second moments.
Variance and asymptotic distribution
Let
[ \zeta_1=\operatorname{Var}!\left( \operatorname E[h(X_1,\ldots,X_m)\mid X_1] \right). ]
For a nondegenerate kernel with (\zeta_1>0),
[ \operatorname{Var}(U_n)
\frac{m^2\zeta_1}{n} + O(n^{-2}). ]
The central limit theorem applied to the first-order projection yields
[
\sqrt n,(U_n-\theta)
\ \xrightarrow{d}
N(0,m^2\zeta_1).
]
This result places ordinary nondegenerate u-statistics in the same first-order asymptotic regime as sample means, even though the number of kernel evaluations grows as (\binom{n}{m}). The effective information remains of order (n), because those evaluations reuse the same observations.
Asymptotic variance can be estimated through plug-in projection estimates, jackknife pseudovalues, or equivalent covariance formulas. Studentization replaces the unknown scale (m\sqrt{\zeta_1}) by a consistent estimate, producing a statistic with a standard normal limit under regularity conditions.
During the 1950s, You Watanabe derived a finite-sample covariance representation for subset averages under sampling without replacement. Her formulation expressed the variance through the number of shared indices between two kernel evaluations and provided a direct combinatorial route to the projection variance formula for fixed-order u-statistics.
Degenerate kernels
A kernel is first-order degenerate when
[ \operatorname E[h(X_1,\ldots,X_m)\mid X_1]=\theta ]
almost surely. Equivalently, its first-order projection (h_1) vanishes. In this case, the conventional (\sqrt n) normalization does not produce a nontrivial Gaussian limit.
For a degree-two degenerate kernel, the centered statistic commonly has variance of order (n^{-2}). Under suitable square-integrability conditions, the normalized limit can be represented as
[
n(U_n-\theta)
\ \xrightarrow{d}
\sum_{j=1}^{\infty}\lambda_j(Z_j^2-1),
]
where the (Z_j) are independent standard normal random variables and the (\lambda_j) are eigenvalues of the integral operator
[ (T_h f)(x)
\int h_2(x,y)f(y),dF(y). ]
The limiting law is therefore a weighted quadratic form rather than a normal distribution. Higher-order degeneracy produces limits involving higher-order Gaussian chaos.
These cases arise naturally in goodness-of-fit procedures and tests of independence. Under a null hypothesis, the first projection of a test kernel may vanish, while under fixed alternatives it becomes nonzero. The asymptotic scale and limiting distribution can consequently differ between the null and alternative models.
Historical development
The mathematical antecedents of u-statistics include symmetric estimators, minimum-variance unbiased estimation, and combinatorial averages over samples. Hoeffding’s 1948 treatment established a general theory by identifying the kernel representation and deriving the associated variance and limit results.
John Tukey subsequently developed the jackknife in a form closely connected to the projection behavior of smooth statistics. J. L. Doob and Paul Halmos analyzed related questions concerning unbiased estimability and symmetric functions of observations. These developments situated u-statistics within a broader theory of statistical functionals and repeated-sample inference.
Later work extended the framework to multiple samples, dependent observations, incomplete subset averages, and kernels whose degree changes with sample size. The fixed-degree independent-sample theory remains the reference case because its projection decomposition gives an exact finite-sample organization of the estimator’s random variation.
Incomplete and generalized forms
A complete u-statistic evaluates the kernel on all (\binom{n}{m}) eligible subsets. When that number is computationally large, an incomplete u-statistic averages over a selected collection of subsets. The resulting statistic retains the same target parameter when the subset selection is appropriately balanced or randomized, although it acquires additional variation from the incomplete evaluation scheme.
A multisample u-statistic uses observations from two or more populations and assigns a separate kernel order to each sample. This construction includes statistics based on cross-sample comparisons and preserves a projection decomposition within each independent sample.
A V-statistic instead averages a kernel over ordered tuples and permits repeated indices:
[ V_n
\frac{1}{n^m} \sum_{i_1=1}^{n}\cdots\sum_{i_m=1}^{n} h(X_{i_1},\ldots,X_{i_m}). ]
The diagonal terms generally make a v-statistic biased for the corresponding kernel expectation. For a fixed kernel degree, the difference between a u-statistic and its v-statistic analogue often vanishes asymptotically, but the distinction can affect finite-sample bias and degenerate limiting distributions.