45.05.05 · mathematical-statistics / 05-empirical-processes-nonparametric

U-Statistics and Their Asymptotics

shipped3 tiersLean: none

Anchor (Master): Lee, U-Statistics: Theory and Practice (Marcel Dekker, 1990) Ch. 1-3; van der Vaart, Asymptotic Statistics (Cambridge, 1998) Ch. 11-12 (the projection / Hájek-projection method, the H-decomposition, degenerate limits); Hoeffding, A class of statistics with asymptotically normal distribution (1948)

Intuition Beginner

Many of the most useful summaries of data are built by averaging a small calculation over every possible little group you can pull out of your sample. The plainest example is the ordinary average: you take each single data point, and you average. But some questions are about relationships between data points, not about single points, so the natural calculation looks at a pair at a time, or sometimes a triple. The trick is always the same. Decide on a fixed rule that takes a small fixed-size group and returns a number, then average that rule over every group of that size in your sample.

A U-statistic is exactly this kind of average. The letter U stands for "unbiased": these estimators are designed so that, on average over many samples, they land exactly on the true quantity you are after, with no built-in lean. The fixed rule is called the kernel, and the size of the group it eats — one point, a pair, a triple — is the degree.

Why bother with pairs and triples instead of just single points? Because the things we most want to measure are often comparisons. How spread out is the data? Compare two points and see how far apart they typically are. Do two treatments differ? Compare a point from one group against a point from the other and count how often the first wins. Do two rankings agree? Compare two items and check whether both rankings order them the same way. Each of these is a pairwise question, and averaging the pairwise answer over all pairs gives a clean, unbiased estimate.

The one-sentence takeaway: a U-statistic estimates a quantity by averaging a fixed symmetric rule over every small group of data points of a fixed size, and "U" marks that this average is exactly unbiased for the quantity it targets.

Visual Beginner

Picture five data points laid out as dots. A degree-two U-statistic looks at every pair of dots — every line you could draw between two of them — applies its rule to each pair, and averages the results.

Group size (degree)	What the rule eats	How many groups in a sample of 5	Example estimate
1	one point	5	the sample average
2	a pair of points	10	average pairwise gap; "first beats second" rate
3	a triple of points	10	agreement among three rankings

The picture is the whole idea: lay out all the small groups of the chosen size, run the same rule on each, and average. Counting the groups is plain combinatorics — for pairs in a sample of five there are ten — and the U-statistic is just the average over that many numbers.

Worked example Beginner

We compute a degree-two U-statistic by hand: the average pairwise gap, $g = (1/2) E ∣ X - Y ∣$ for two independent draws, which measures spread. The rule (kernel) applied to a pair of points $a$ and $b$ is $h (a, b) = (1/2) ∣ a - b ∣$ . We average it over all pairs.

Step 1. The data. Take the four numbers $1, 4, 6, 9$ . With four points there are six pairs.

Step 2. List the pairs and the rule's value on each. The pairs and their gaps $∣ a - b ∣$ are: $(1, 4) \to 3$ ; $(1, 6) \to 5$ ; $(1, 9) \to 8$ ; $(4, 6) \to 2$ ; $(4, 9) \to 5$ ; $(6, 9) \to 3$ . Halving each gives the kernel values $1.5, 2.5, 4, 1, 2.5, 1.5$ .

Step 3. Average over the six pairs. The sum of the kernel values is $1.5 + 2.5 + 4 + 1 + 2.5 + 1.5 = 13$ . Dividing by the six pairs gives $13/6 = 2.1 \overline{6}$ .

Step 4. Read off the estimate. The U-statistic equals about $2.17$ . This is the sample's estimate of the true average half-gap between two random draws from the same source.

Step 5. What this tells us. We never had to know the underlying distribution. We picked a rule for a pair, ran it on every pair, and averaged. The result is an unbiased estimate of the half-gap, and because every pair is weighted the same way, no special point dominates. This same recipe — pick a rule, average over all groups — produces the sample variance, the Wilcoxon rank statistic, and Kendall's rank-agreement measure, simply by changing the rule.

Check your understanding Beginner

Formal definition Intermediate+

Let $X_{1}, \dots, X_{n}$ be i.i.d. with law $P$ on a measurable space $(X, A)$ . Fix an integer $m \leq n$ , the degree, and a measurable kernel $h : X^{m} \to R$ that is symmetric: $h (x_{1}, \dots, x_{m}) = h (x_{σ (1)}, \dots, x_{σ (m)})$ for every permutation $σ$ . The parameter estimated by $h$ is

θ = θ (P) = E_{P} h (X_{1}, \dots, X_{m}) = \int h d P^{\otimes m} .

Definition (U-statistic). The U-statistic with kernel $h$ is

U_{n} = U_{n} (h) = (m n)^{- 1} 1 \leq i_{1} < \dots < i_{m} \leq n \sum h (X_{i_{1}}, \dots, X_{i_{m}}),

the average of $h$ over all $(m n)$ subsets of size $m$ . By construction each summand has mean $θ$ , so $E U_{n} = θ$ : the U-statistic is the unique symmetric unbiased estimator of $θ$ that is a function of the order statistics, and the prefix U records unbiasedness. Any non-symmetric kernel $g$ may be replaced by its symmetrisation $h = (m!)^{- 1} \sum_{σ} g (x_{σ (1)}, \dots, x_{σ (m)})$ with the same expectation and a variance no larger, so symmetry costs nothing.

Notation: $E$ and $Var$ are under $P$ ; $P^{\otimes m}$ is the $m$ -fold product measure; $d$ , $P$ , $a . s .$ are the modes of stochastic convergence from 45.04.01; $E [\cdot ∣ G]$ is conditional expectation in the $L^{2}$ sense developed in 37.04.01.

Definition (projection kernels and the variance components). For $0 \leq c \leq m$ define

h_{c} (x_{1}, \dots, x_{c}) = E h (x_{1}, \dots, x_{c}, X_{c + 1}, \dots, X_{m}),

the kernel with its last $m - c$ arguments integrated out; thus $h_{0} = θ$ and $h_{m} = h$ . Set the centred projections

\tilde{h}_{c} (x_{1}, \dots, x_{c}) = j = 0 \sum c (- 1)^{c - j} 1 \leq k_{1} < \dots < k_{j} \leq c \sum h_{j} (x_{k_{1}}, \dots, x_{k_{j}}),

the inclusion-exclusion residual of $h_{c}$ after subtracting all lower-order projections, and the variance components

ζ_{c} = Var h_{c} (X_{1}, \dots, X_{c}) = Var \tilde{h}_{c} (X_{1}, \dots, X_{c}), ζ_{0} = 0.

The kernel is non-degenerate (more precisely, of order one) when $ζ_{1} > 0$ , and degenerate of order $k$ when $ζ_{1} = \dots = ζ_{k} = 0 < ζ_{k + 1}$ .

Counterexamples to common slips Intermediate+

A U-statistic is not a sum of independent terms. The summands $h (X_{i_{1}}, \dots, X_{i_{m}})$ share data points across overlapping subsets and are strongly dependent. The variance is therefore not $(m n)^{- 1} ζ_{m}$ ; cross-covariances between overlapping subsets dominate, and computing them is the content of the variance formula below.
Symmetry of the kernel is required for the standard theory. If one averages an asymmetric $g$ over ordered tuples one obtains a V-statistic-like object whose unbiasedness and variance bookkeeping differ; the clean projection theory below assumes a symmetric $h$ .
$ζ_{1} = 0$ is not a pathology to be assumed away. Several important U-statistics — among them Cramér-von Mises type kernels and the sample-variance kernel evaluated at the wrong centring — are first-order degenerate, and their limit is not normal but a weighted sum of chi-squares. The non-degenerate theory does not apply to them.
$U_{n}$ unbiased does not make $h$ unique as a function. Many kernels share the same expectation $θ$ ; the U-statistic is unique only after one fixes the kernel. Different kernels for the same $θ$ can have different variances, and choosing the lowest-variance kernel is a real design question.

Key theorem with proof Intermediate+

The asymptotics of a non-degenerate U-statistic are governed by a single linear approximation: $U_{n}$ behaves to first order like an average of i.i.d. terms, its Hájek projection, and the central limit theorem does the rest ^{[van der Vaart 1998]}.

Theorem (variance formula and asymptotic normality of non-degenerate U-statistics). Let $h$ be a symmetric kernel of degree $m$ with $E h^{2} < \infty$ , parameter $θ = E h$ , and variance components $ζ_{c}$ .

(i) Variance. $Var (U_{n}) = (m n)^{- 1} c = 1 \sum m (c m) (m - c n - m) ζ_{c} .$

(ii) Leading term. Define the Hájek projection $\hat{U}_{n} = θ + \frac{m}{n} \sum_{i = 1}^{n} \tilde{h}_{1} (X_{i})$ , where $\tilde{h}_{1} (x) = h_{1} (x) - θ$ . Then $Var (U_{n}) = \frac{m ^{2} ζ _{1}}{n} + O (n^{- 2})$ and

E (U_{n} - \hat{U}_{n})^{2} = Var (U_{n}) - Var (\hat{U}_{n}) = O (n^{- 2}) .

(iii) Limit law. If $ζ_{1} > 0$ then $n (U_{n} - θ) d N (0, m^{2} ζ_{1}) .$

Proof. (i). Write the U-statistic as the average $U_{n} = (m n)^{- 1} \sum_{S} h (X_{S})$ over $m$ -subsets $S$ , with $h (X_{S})$ centred at $θ$ for variance purposes. Two subsets $S, S^{'}$ with $∣ S \cap S^{'} ∣ = c$ have, by independence of the disjoint coordinates and the tower property,

Cov (h (X_{S}), h (X_{S^{'}})) = ζ_{c},

because conditioning on the $c$ shared coordinates and integrating the rest replaces $h$ by $h_{c}$ on each factor, and $Cov (h_{c}, h_{c}) = ζ_{c}$ with the independent parts contributing nothing. Counting ordered pairs $(S, S^{'})$ with $∣ S \cap S^{'} ∣ = c$ gives $(m n) (c m) (m - c n - m)$ , so

Var (U_{n}) = (m n)^{- 2} c = 1 \sum m (m n) (c m) (m - c n - m) ζ_{c} = (m n)^{- 1} c = 1 \sum m (c m) (m - c n - m) ζ_{c} .

The $c = 0$ term vanishes since $ζ_{0} = 0$ . As $n \to \infty$ the $c = 1$ summand is $(m n)^{- 1} m (m - 1 n - m) ζ_{1} = \frac{m ^{2}}{n} ζ_{1} (1 + O (n^{- 1}))$ , and every $c \geq 2$ summand is $O (n^{- c})$ ; hence $Var (U_{n}) = m^{2} ζ_{1} / n + O (n^{- 2})$ .

(ii). The Hájek projection is the conditional expectation of $U_{n} - θ$ onto the sums of single-coordinate functions: $\hat{U}_{n} - θ = \sum_{i = 1}^{n} E [U_{n} - θ ∣ X_{i}]$ . Computing one term, $E [U_{n} - θ ∣ X_{i}] = (m n)^{- 1} (m - 1 n - 1) (h_{1} (X_{i}) - θ) = \frac{m}{n} \tilde{h}_{1} (X_{i})$ , since exactly $(m - 1 n - 1)$ of the subsets contain index $i$ and each contributes $h_{1} (X_{i}) - θ$ after integrating its other coordinates. Summing gives the stated $\hat{U}_{n}$ . Because $\hat{U}_{n}$ is the $L^{2}$ -orthogonal projection of $U_{n}$ onto the closed subspace of sums $\sum_{i} g (X_{i})$ (the conditioning is onto a sub- $σ$ -field, an orthogonal projection in $L^{2}$ as in 37.04.01), Pythagoras gives $E (U_{n} - \hat{U}_{n})^{2} = Var (U_{n}) - Var (\hat{U}_{n})$ . Now $Var (\hat{U}_{n}) = (m^{2} / n^{2}) \cdot n ζ_{1} = m^{2} ζ_{1} / n$ by independence of the $X_{i}$ , and $Var (U_{n}) = m^{2} ζ_{1} / n + O (n^{- 2})$ from (i); subtracting, $E (U_{n} - \hat{U}_{n})^{2} = O (n^{- 2})$ .

(iii). Scale by $n$ : $n (U_{n} - θ) = n (\hat{U}_{n} - θ) + n (U_{n} - \hat{U}_{n})$ . The remainder satisfies $E [n (U_{n} - \hat{U}_{n})^{2}] = n \cdot O (n^{- 2}) = O (n^{- 1}) \to 0$ , so $n (U_{n} - \hat{U}_{n}) P 0$ by Markov's inequality, an $o_{P} (1)$ term in the language of 45.04.01. The leading term is an i.i.d. average: $n (\hat{U}_{n} - θ) = \frac{m}{n} \sum_{i = 1}^{n} \tilde{h}_{1} (X_{i})$ with $\tilde{h}_{1} (X_{i})$ i.i.d., mean $0$ , variance $ζ_{1} \in (0, \infty)$ . The central limit theorem 37.03.02 gives $\frac{1}{n} \sum_{i} \tilde{h}_{1} (X_{i}) d N (0, ζ_{1})$ , hence $n (\hat{U}_{n} - θ) d N (0, m^{2} ζ_{1})$ . Slutsky's lemma absorbs the $o_{P} (1)$ remainder, yielding $n (U_{n} - θ) d N (0, m^{2} ζ_{1})$ . $□$

Bridge. This projection argument builds toward every limit theorem for smooth statistics in the chapter, and it appears again in the asymptotics of rank statistics, where the same one-coordinate conditional expectation linearises a non-linear functional of the sample. The foundational reason the theorem works is that a symmetric statistic with finite variance is, after centring, dominated in $L^{2}$ by its projection onto sums of single-coordinate functions: the higher-order interaction terms carry variance of order $n^{- 2}$ and smaller, and the central limit theorem 37.03.02 then operates on the surviving i.i.d. average. This is exactly the Hájek-projection method, and it generalises the elementary fact that the sample mean is asymptotically normal: the mean is the U-statistic of degree one, for which $U_{n} = \hat{U}_{n}$ identically and the remainder is absent. Putting these together, the calculus of stochastic order from 45.04.01 — discard an $o_{P} (1)$ remainder, freeze the leading term — is what converts the variance bookkeeping into a clean normal limit, and the bridge from the combinatorial variance formula to the limit law is the orthogonality of the H-decomposition introduced next.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

The Wilcoxon-Mann-Whitney functional uses the kernel $h (x, y) = 1 {x \leq y}$ symmetrised, estimating $θ = P (X \leq Y)$ for two i.i.d. draws. Taking the (non-symmetric form for concreteness) one-sample kernel $h (x, y) = 1 {x + y \leq 0}$ on i.i.d. data, compute $h_{1} (x)$ and explain when $ζ_{1} = 0$ .

Hint

$h_{1} (x) = E h (x, X_{2}) = P (X_{2} \leq - x) = F (- x)$ , where $F$ is the distribution function. Degeneracy means $h_{1}$ is constant.

Answer

$h_{1} (x) = E 1 {x + X_{2} \leq 0} = P (X_{2} \leq - x) = F (- x)$ . Then $θ = E F (- X_{1}) = \int F (- x) d F (x)$ and $ζ_{1} = Var F (- X_{1})$ . Non-degeneracy $ζ_{1} > 0$ holds whenever $x \mapsto F (- x)$ is not $P$ -almost-surely constant, which is the generic situation for a continuous $F$ ; $ζ_{1} = 0$ would require $F (- X_{1})$ to be degenerate, an exceptional symmetry. So the statistic is generically asymptotically normal with variance $4 ζ_{1} / n$ .

Exercise 5 (medium, symbolic).

Show directly that the Hájek projection $\hat{U}_{n}$ is the $L^{2}$ -orthogonal projection of $U_{n}$ onto the linear space $L = {c + \sum_{i} g (X_{i}) : c \in R, E g (X_{1})^{2} < \infty}$ , and deduce $E (U_{n} - \hat{U}_{n}) Z = 0$ for every $Z \in L$ .

Hint

A conditional expectation onto a sub- $σ$ -field is an $L^{2}$ -orthogonal projection; the sum of single-coordinate conditional expectations projects onto $L$ for i.i.d. data.

Answer

For i.i.d. data, functions $g (X_{i})$ for distinct $i$ are uncorrelated after centring, and any $Z = c + \sum_{i} g (X_{i}) \in L$ has $E [U_{n} Z]$ depending on $U_{n}$ only through the single-coordinate conditional expectations $E [U_{n} ∣ X_{i}]$ . By 37.04.01, $E [U_{n} ∣ X_{i}]$ is the orthogonal projection of $U_{n}$ onto $L^{2} (σ (X_{i}))$ , and summing the centred versions and adding the constant $θ$ projects onto $L$ , giving $\hat{U}_{n}$ . Orthogonality of a projection residual to the subspace yields $E (U_{n} - \hat{U}_{n}) Z = 0$ for all $Z \in L$ ; in particular $\hat{U}_{n}$ minimises $E (U_{n} - Z)^{2}$ over $Z \in L$ .

Exercise 6 (hard, symbolic).

Kendall's tau uses the degree-two kernel $h ((x_{1}, y_{1}), (x_{2}, y_{2})) = 1 {(x_{1} - x_{2}) (y_{1} - y_{2}) > 0} - 1 {(x_{1} - x_{2}) (y_{1} - y_{2}) < 0}$ on i.i.d. pairs $(X_{i}, Y_{i})$ , estimating $τ = P (concordant) - P (discordant)$ . Under independence of $X$ and $Y$ , show $τ = 0$ and find the asymptotic distribution of $n U_{n}$ , identifying $ζ_{1}$ .

Hint

Under independence the pair is exchangeable in a way that makes concordance and discordance equally likely, so $τ = 0$ . Then compute $h_{1}$ and check $ζ_{1} > 0$ to invoke the normal limit with variance $4 ζ_{1}$ .

Answer

Under independence of $X$ and $Y$ (both continuous), for two independent draws the sign of $(X_{1} - X_{2}) (Y_{1} - Y_{2})$ is symmetric: concordant and discordant are equally likely, each with probability $1/2$ , so $τ = \frac{1}{2} - \frac{1}{2} = 0$ . The first projection is $h_{1} ((x, y)) = E h ((x, y), (X_{2}, Y_{2})) = P {(x - X_{2}) (y - Y_{2}) > 0} - P {(x - X_{2}) (y - Y_{2}) < 0}$ . With $F, G$ the marginals, $h_{1} (x, y) = (2 F (x) - 1) (2 G (y) - 1)$ after using independence. Then $ζ_{1} = Var h_{1} (X_{1}, Y_{1}) = Var [(2 F (X_{1}) - 1) (2 G (Y_{1}) - 1)]$ . Since $F (X_{1}), G (Y_{1})$ are independent uniforms on $[0, 1]$ , $2 F (X_{1}) - 1$ and $2 G (Y_{1}) - 1$ are independent, mean zero, variance $1/3$ ; their product has variance $(1/3) (1/3) = 1/9$ , so $ζ_{1} = 1/9$ . By the Key theorem with $m = 2$ , $n U_{n} d N (0, 4 ζ_{1}) = N (0, 4/9)$ . This is the basis of Kendall's-tau independence test.

Exercise 7 (hard, symbolic).

Prove that $(U_{n})_{n \geq m}$ , suitably indexed, is a reverse martingale: with $G_{n} = σ (U_{n}, U_{n + 1}, \dots)$ one has $E [U_{n} ∣ G_{n + 1}] = U_{n + 1}$ , hence $U_{n} a . s . θ$ when $E ∣ h ∣ < \infty$ (the strong law for U-statistics).

Hint

Show $U_{n} = E [h (X_{1}, \dots, X_{m}) ∣ S_{n}]$ for the exchangeable $σ$ -field $S_{n}$ generated by the order statistics of $X_{1}, \dots, X_{n}$ ; these fields decrease in $n$ , giving a reverse martingale, and apply the reverse martingale convergence theorem from 37.04.01.

Answer

Let $S_{n}$ be the $σ$ -field of the unordered sample ${X_{1}, \dots, X_{n}}$ (symmetric functions / order statistics). By symmetry of $h$ and exchangeability of the data, $U_{n} = E [h (X_{1}, \dots, X_{m}) ∣ S_{n}]$ : conditioning $h$ on the unordered $n$ -sample and averaging over which $m$ of the $n$ points are used reproduces the U-statistic average. The fields decrease, $S_{n} \supseteq S_{n + 1} \supseteq \dots$ , since the unordered $(n + 1)$ -sample determines the unordered $n$ -sample's symmetric functions through the larger one; hence $E [U_{n} ∣ S_{n + 1}] = E [E [h ∣ S_{n}] ∣ S_{n + 1}] = E [h ∣ S_{n + 1}] = U_{n + 1}$ by the tower property 37.04.01. So $(U_{n})$ is a reverse martingale with respect to the decreasing fields $(S_{n})$ . The reverse martingale convergence theorem gives $U_{n} \to E [h ∣ S_{\infty}]$ a.s. and in $L^{1}$ ; the tail field $S_{\infty}$ is degenerate by the Hewitt-Savage zero-one law, so the limit is the constant $E h = θ$ . Thus $U_{n} a . s . θ$ , the strong consistency of every U-statistic with an integrable kernel.

Exercise 8 (hard, symbolic).

Let $h$ be a first-order-degenerate symmetric kernel of degree two: $ζ_{1} = 0 < ζ_{2}$ and $h_{1} \equiv θ$ . Show that the correct normalisation is $n$ , not $n$ , and that the limit of $n (U_{n} - θ)$ is non-normal. State the limit in terms of the eigenvalues of the kernel operator.

Hint

The Hájek projection vanishes ( $ζ_{1} = 0$ ), so the leading term is the degree-two interaction. Diagonalise the centred kernel $\tilde{h}_{2}$ as a Hilbert-Schmidt operator on $L^{2} (P)$ .

Answer

With $ζ_{1} = 0$ the Hájek projection $\hat{U}_{n} - θ = (m / n) \sum_{i} \tilde{h}_{1} (X_{i})$ is identically $θ$ (its variance is $m^{2} ζ_{1} / n = 0$ ), so the $n$ -rescaled statistic converges to $0$ and carries no information. The leading nonzero term is the degree-two component, whose variance is $Var (U_{n}) = (2 n)^{- 1} ζ_{2} = O (n^{- 2})$ , so $n (U_{n} - θ)$ has a nondegenerate limit. Treat the centred kernel $\tilde{h}_{2} (x, y) = h (x, y) - h_{1} (x) - h_{1} (y) + θ$ as the integral operator $T ϕ (x) = \int \tilde{h}_{2} (x, y) ϕ (y) d P (y)$ on $L^{2} (P)$ ; being symmetric and (under $E h^{2} < \infty$ ) Hilbert-Schmidt, it has real eigenvalues $λ_{1}, λ_{2}, \dots$ with $\sum_{j} λ_{j}^{2} = ζ_{2} < \infty$ . Then

n (U_{n} - θ) d j \geq 1 \sum λ_{j} (χ_{1, j}^{2} - 1),

where $χ_{1, j}^{2}$ are i.i.d. chi-squared-one variables (squares of i.i.d. standard normals). The limit is a weighted infinite sum of centred chi-squares, normal only in the degenerate case of a single nonzero eigenvalue, and the rate is $n$ rather than $n$ . This is the prototype for Cramér-von Mises and other quadratic goodness-of-fit limits.

Advanced results Master

Theorem 1 (Hoeffding decomposition). Every symmetric kernel $h$ with $E h^{2} < \infty$ admits the orthogonal expansion

U_{n} (h) = θ + c = 1 \sum m (c m) U_{n}^{(c)} (\tilde{h}_{c}),

where $U_{n}^{(c)} (\tilde{h}_{c})$ is the degree- $c$ U-statistic of the completely degenerate kernel $\tilde{h}_{c}$ defined in the formal section, the projections $\tilde{h}_{c}$ are mutually orthogonal in $L^{2}$ , and each is degenerate in the strong sense that integrating out any one argument gives zero. The decomposition is the ANOVA of the symmetric statistic: it splits $U_{n} - θ$ into uncorrelated "interaction" pieces of pure order $c = 1, \dots, m$ , with $Var (U_{n}^{(c)} (\tilde{h}_{c})) = (c n)^{- 1} ζ_{c}^{\circ}$ for the variance $ζ_{c}^{\circ} = Var \tilde{h}_{c}$ of the $c$ -th projection. Orthogonality is what makes the variance formula of the Key theorem a sum with no cross-terms, and it is the structural source of the entire asymptotic theory ^{[Hoeffding 1948]}.

Theorem 2 (the projection / Hájek-projection method). For any sequence of statistics $T_{n}$ with $Var T_{n} < \infty$ , let $\hat{T}_{n} = E T_{n} + \sum_{i = 1}^{n} (E [T_{n} ∣ X_{i}] - E T_{n})$ be its projection onto sums of single-coordinate functions. Then $\hat{T}_{n}$ is the $L^{2}$ -closest such sum, $Var (T_{n} - \hat{T}_{n}) = Var T_{n} - Var \hat{T}_{n}$ , and whenever $Var (T_{n} - \hat{T}_{n}) / Var \hat{T}_{n} \to 0$ the standardised statistics $T_{n}$ and $\hat{T}_{n}$ have the same limit law. Asymptotic normality of $T_{n}$ then reduces to the central limit theorem 37.03.02 for the i.i.d. average $\hat{T}_{n}$ . Hájek isolated this principle for rank statistics; for U-statistics it is the content of part (ii) of the Key theorem, and it is the single most reused device in nonparametric asymptotics ^{[Hájek 1968]}.

Theorem 3 (degenerate limit via the spectrum of the kernel operator). Let $h$ be symmetric of degree two with $ζ_{1} = 0 < ζ_{2}$ and $E h^{2} < \infty$ . The centred kernel $\tilde{h}_{2}$ defines a symmetric Hilbert-Schmidt operator on $L^{2} (P)$ with real eigenvalues $(λ_{j})$ and orthonormal eigenfunctions $(ϕ_{j})$ , $\sum_{j} λ_{j}^{2} = ζ_{2}$ . Then $n (U_{n} - θ) d \sum_{j} λ_{j} (χ_{1, j}^{2} - 1)$ with i.i.d. $χ_{1, j}^{2} = ξ_{j}^{2}$ , $ξ_{j} \sim N (0, 1)$ . The limit is Gaussian iff exactly one eigenvalue is nonzero. The general degree- $m$ degenerate-of-order- $k$ case rescales by $n^{(k + 1) /2}$ and produces a multiple Wiener-Itô integral against the leading nondegenerate projection ^{[Lee 1990]}.

Theorem 4 (Hoeffding's CLT, general form, and the variance estimator). If $E h^{2} < \infty$ and $ζ_{1} > 0$ , then $n (U_{n} - θ) d N (0, m^{2} ζ_{1})$ , and the jackknife / plug-in estimator $\hat{ζ}_{1, n}$ formed from the leave-one-out projection estimates is consistent, so $n (U_{n} - θ) / (m \hat{ζ}_{1, n}^{1/2}) d N (0, 1)$ by Slutsky's lemma 45.04.01. This makes U-statistics directly usable for confidence intervals and tests without knowing $P$ , which is the practical payoff of the theory and the reason U-statistics underlie rank-based inference ^{[Hoeffding 1948]}.

Synthesis. The foundational reason U-statistic asymptotics are tractable is the Hoeffding decomposition: a symmetric square-integrable statistic splits orthogonally into interaction terms of pure order, the degree-one term is an i.i.d. average, and the higher terms carry vanishing relative variance. This is exactly the structure that the Hájek projection exploits, and it generalises the elementary central limit theorem 37.03.02 in two directions at once — to non-linear symmetric functionals of the sample, and, through the reverse-martingale identity, to a strong law that gives almost-sure consistency for any integrable kernel. The central insight is that the projection onto sums of single-coordinate functions is an $L^{2}$ -orthogonal projection, dual to conditional expectation onto the one-coordinate $σ$ -fields 37.04.01, so the residual is automatically orthogonal to the leading term and the Pythagorean variance split is forced rather than assumed. Putting these together, the non-degenerate theory is the case where the order-one term dominates and the limit is normal with variance $m^{2} ζ_{1}$ , while the degenerate theory is the case where that term vanishes and the order-two interaction surfaces as a weighted sum of chi-squares governed by the spectrum of the kernel operator; the two regimes are one decomposition read at different scales. This is the bridge from the modes of convergence and the stochastic-order calculus of 45.04.01 to the empirical-process viewpoint of the chapter, where the U-statistic is the empirical measure applied to a symmetric kernel and the Hoeffding decomposition is the U-process analogue of the linearisation that drives Donsker theory.

Full proof set Master

Proposition 1 (unbiasedness and the reverse-martingale property). For a symmetric kernel $h$ with $E ∣ h ∣ < \infty$ , $E U_{n} = θ$ and $(U_{n})$ is a reverse martingale with respect to the decreasing exchangeable $σ$ -fields $S_{n} = σ (unordered X_{1}, \dots, X_{n})$ ; consequently $U_{n} a . s . θ$ .

Proof. Each summand $h (X_{i_{1}}, \dots, X_{i_{m}})$ has mean $θ$ by the i.i.d. assumption and the definition of $θ$ , so averaging preserves the mean and $E U_{n} = θ$ . By symmetry of $h$ , $U_{n} = E [h (X_{1}, \dots, X_{m}) ∣ S_{n}]$ , the average of $h$ over all relabellings of the unordered sample. The fields $S_{n}$ decrease in $n$ because the unordered $(n + 1)$ -sample determines the unordered $n$ -sample's symmetric statistics. The tower property 37.04.01 gives $E [U_{n} ∣ S_{n + 1}] = E [E [h ∣ S_{n}] ∣ S_{n + 1}] = E [h ∣ S_{n + 1}] = U_{n + 1}$ . The reverse martingale convergence theorem yields $U_{n} \to E [h ∣ S_{\infty}]$ almost surely and in $L^{1}$ ; the Hewitt-Savage zero-one law makes the exchangeable tail field $S_{\infty}$ degenerate (its events have probability $0$ or $1$ ), so the limit equals its mean $θ$ . $□$

Proposition 2 (the covariance of overlapping subsets). For $m$ -subsets $S, S^{'}$ with $∣ S \cap S^{'} ∣ = c$ , $Cov (h (X_{S}), h (X_{S^{'}})) = ζ_{c}$ .

Proof. Index the shared coordinates by $S \cap S^{'}$ and write $X_{S} = (X_{S \cap S^{'}}, X_{S ∖ S^{'}})$ and $X_{S^{'}} = (X_{S \cap S^{'}}, X_{S^{'} ∖ S})$ , with the three blocks mutually independent. Condition on $X_{S \cap S^{'}} = (x_{1}, \dots, x_{c})$ . The conditional expectation of $h (X_{S})$ integrates out the $m - c$ private coordinates of $S$ , returning $h_{c} (x_{1}, \dots, x_{c})$ , and likewise for $S^{'}$ ; the private blocks being independent of each other and of the shared block, the conditional covariance is zero and

Cov (h (X_{S}), h (X_{S^{'}})) = Cov (h_{c} (X_{S \cap S^{'}}), h_{c} (X_{S \cap S^{'}})) = Var h_{c} = ζ_{c}

by the law of total covariance, the cross term vanishing because each centred private average has conditional mean zero. $□$

Proposition 3 (orthogonality of the H-decomposition). The projections $\tilde{h}_{c}$ satisfy $E \tilde{h}_{c} (X_{1}, \dots, X_{c}) \tilde{h}_{c^{'}} (X_{j_{1}}, \dots, X_{j_{c^{'}}}) = 0$ whenever ${1, \dots, c} \neq = {j_{1}, \dots, j_{c^{'}}}$ or $c \neq = c^{'}$ , and each $\tilde{h}_{c}$ is completely degenerate: $E [\tilde{h}_{c} (X_{1}, \dots, X_{c}) ∣ X_{2}, \dots, X_{c}] = 0$ .

Proof. Complete degeneracy is built into the inclusion-exclusion definition: $\tilde{h}_{c}$ is $h_{c}$ with all lower-order projections subtracted, so integrating any single argument annihilates it — the integral of $h_{c}$ over the $j$ -th coordinate equals $h_{c - 1}$ on the remaining coordinates, which is exactly the term removed by the alternating sum. Given complete degeneracy, if two index sets differ, say some index $k$ lies in one but not the other, condition on all variables except $X_{k}$ and integrate $X_{k}$ out of the factor that contains it; that factor has conditional mean zero by complete degeneracy, so the product has mean zero. For equal index sets with $c \neq = c^{'}$ the same argument applies to any index in the symmetric difference. Hence distinct interaction terms are orthogonal in $L^{2}$ , and $U_{n} - θ$ decomposes as an orthogonal sum, giving the variance formula of the Key theorem with no cross-terms. $□$

Proposition 4 (asymptotic normality, full statement). If $E h^{2} < \infty$ and $ζ_{1} > 0$ , then $n (U_{n} - θ) d N (0, m^{2} ζ_{1})$ .

Proof. By Propositions 2-3 the variance is $Var (U_{n}) = (m n)^{- 1} \sum_{c = 1}^{m} (c m) (m - c n - m) ζ_{c} = m^{2} ζ_{1} / n + O (n^{- 2})$ . The Hájek projection $\hat{U}_{n} - θ = (m / n) \sum_{i = 1}^{n} \tilde{h}_{1} (X_{i})$ has variance $m^{2} ζ_{1} / n$ , and orthogonality of the residual gives $E (U_{n} - \hat{U}_{n})^{2} = Var (U_{n}) - Var (\hat{U}_{n}) = O (n^{- 2})$ . Therefore $n (U_{n} - \hat{U}_{n}) P 0$ , an $o_{P} (1)$ term 45.04.01. The leading term $n (\hat{U}_{n} - θ) = (m / n) \sum_{i} \tilde{h}_{1} (X_{i})$ is $m$ times a standardised i.i.d. average with summand variance $ζ_{1}$ ; the central limit theorem 37.03.02 gives $d N (0, m^{2} ζ_{1})$ . Slutsky's lemma combines the two, $n (U_{n} - θ) = n (\hat{U}_{n} - θ) + o_{P} (1) d N (0, m^{2} ζ_{1})$ . $□$

Proposition 5 (degenerate limit, degree two). If $ζ_{1} = 0 < ζ_{2}$ and $E h^{2} < \infty$ , then $n (U_{n} - θ) d \sum_{j} λ_{j} (ξ_{j}^{2} - 1)$ with $(λ_{j})$ the eigenvalues of the kernel operator $T ϕ = \int \tilde{h}_{2} (\cdot, y) ϕ (y) d P (y)$ and $ξ_{j}$ i.i.d. standard normal.

Proof (sketch with the load-bearing steps). With $ζ_{1} = 0$ , $U_{n} - θ = (2 n)^{- 1} \sum_{i < j} \tilde{h}_{2} (X_{i}, X_{j})$ , a completely degenerate degree-two U-statistic. The Hilbert-Schmidt operator $T$ on $L^{2} (P)$ has spectral decomposition $\tilde{h}_{2} (x, y) = \sum_{j} λ_{j} ϕ_{j} (x) ϕ_{j} (y)$ converging in $L^{2} (P \otimes P)$ , with $(ϕ_{j})$ orthonormal, $E ϕ_{j} (X) = 0$ (complete degeneracy forces eigenfunctions to be centred), and $\sum_{j} λ_{j}^{2} = ζ_{2} < \infty$ . Substituting and using $\sum_{i < j} ϕ_{j} (X_{i}) ϕ_{j} (X_{i^{'}}) = \frac{1}{2} [(\sum_{i} ϕ_{j} (X_{i}))^{2} - \sum_{i} ϕ_{j} (X_{i})^{2}]$ ,

n (U_{n} - θ) = \frac{n}{( 2 n )} i < j \sum \tilde{h}_{2} (X_{i}, X_{j}) = k \sum λ_{k} [(\frac{1}{n} i \sum ϕ_{k} (X_{i}))^{2} - \frac{1}{n} i \sum ϕ_{k} (X_{i})^{2}] + o_{P} (1) .

For each fixed $k$ the central limit theorem 37.03.02 gives $n^{- 1/2} \sum_{i} ϕ_{k} (X_{i}) d ξ_{k} \sim N (0, 1)$ jointly over finitely many $k$ (the $ϕ_{k}$ are orthonormal, so the limit coordinates are independent), and $n^{- 1} \sum_{i} ϕ_{k} (X_{i})^{2} P 1$ by the law of large numbers. A truncation argument controls the tail $\sum_{k > K} λ_{k} (\cdot)$ uniformly using $\sum_{k > K} λ_{k}^{2} \to 0$ . Passing to the limit term by term and reassembling, $n (U_{n} - θ) d \sum_{k} λ_{k} (ξ_{k}^{2} - 1)$ , the stated weighted sum of centred chi-squares. $□$

Connections Master

The modes of stochastic convergence and the $o_{P} / O_{P}$ calculus of 45.04.01 are used at the decisive step of every limit theorem here: the Hájek-projection argument writes $n (U_{n} - θ)$ as an i.i.d. average plus an $o_{P} (1)$ remainder, and Slutsky's lemma — proved there — is what discards the remainder and freezes the consistent variance estimate to obtain the studentised normal limit of Theorem 4.

Discrete-time martingales and conditional expectation 37.04.01 supply two distinct pieces of the machinery: the projection $\hat{U}_{n}$ is a sum of one-coordinate conditional expectations and is therefore an $L^{2}$ -orthogonal projection, which makes the Pythagorean variance split exact; and the reverse-martingale identity $E [U_{n} ∣ S_{n + 1}] = U_{n + 1}$ over the decreasing exchangeable fields delivers the strong law $U_{n} a . s . θ$ through the reverse martingale convergence theorem proved in that unit.

The Lindeberg-Feller central limit theorem 37.03.02 is the limit theorem the projection method delegates to: once $U_{n}$ is reduced to its leading i.i.d. average $(m / n) \sum_{i} \tilde{h}_{1} (X_{i})$ , the normal limit is exactly the classical central limit theorem applied to the bounded-variance summands $\tilde{h}_{1} (X_{i})$ , and in the degenerate case the same theorem applied coordinatewise to the eigenfunction scores $ϕ_{k} (X_{i})$ produces the Gaussian variables whose squares give the chi-squared limit.

Empirical processes and Glivenko-Cantelli classes 45.05.02 generalise U-statistics to U-processes — kernels indexed by a parameter — where the Hoeffding decomposition becomes a decomposition into empirical and degenerate U-processes and the Donsker theory there controls the leading empirical-process term uniformly; the present unit is the fixed-kernel case that motivates that machinery.

The Bernstein inequality and sub-exponential concentration 45.05.01 provide the finite-sample companion to the asymptotics here: exponential tail bounds for non-degenerate U-statistics follow by applying sub-Gaussian/sub-exponential concentration to the Hájek-projection leading term plus a higher-order remainder bound, turning the central limit theorem into a quantitative confidence statement.

Historical & philosophical context Master

The theory was created in a single paper by Wassily Hoeffding, "A class of statistics with asymptotically normal distribution," published in the Annals of Mathematical Statistics in 1948 ^{[Hoeffding 1948]}. Hoeffding defined the U-statistic as the unbiased average of a symmetric kernel over subsets, proved the variance formula in terms of the components $ζ_{c}$ , and established asymptotic normality in the non-degenerate case, unifying the sample variance, Gini's mean difference, and the rank statistics of Wilcoxon and Kendall under one limit theorem. The orthogonal decomposition that now bears his name — the Hoeffding or H-decomposition — is implicit in his variance computation and was made explicit in later expositions.

The projection method that streamlines the normality proof was abstracted by Jaroslav Hájek in his 1968 Annals of Mathematical Statistics paper on the asymptotic normality of rank statistics ^{[Hájek 1968]}, where the projection of a statistic onto sums of single-coordinate functions and the $L^{2}$ bound on the residual were isolated as a general tool; applied to U-statistics it reproduces Hoeffding's theorem with the projection made the center of the argument. The degenerate case, with its weighted-chi-squared limit governed by the eigenvalues of the kernel operator, was developed through the 1940s-1980s and is treated systematically in the monograph of A. J. Lee, U-Statistics: Theory and Practice (1990) ^{[Lee 1990]}, and in van der Vaart's chapters ^{[van der Vaart 1998]}, which also place the subject within the empirical-process framework. Serfling's Approximation Theorems of Mathematical Statistics ^{[Serfling 1980]} gives the standard textbook account of the reverse-martingale strong law and the variance bookkeeping.

Bibliography Master

@article{Hoeffding1948,
  author  = {Hoeffding, Wassily},
  title   = {A class of statistics with asymptotically normal distribution},
  journal = {Annals of Mathematical Statistics},
  volume  = {19},
  number  = {3},
  year    = {1948},
  pages   = {293--325}
}

@article{Hajek1968,
  author  = {H\'ajek, Jaroslav},
  title   = {Asymptotic normality of simple linear rank statistics under alternatives},
  journal = {Annals of Mathematical Statistics},
  volume  = {39},
  number  = {2},
  year    = {1968},
  pages   = {325--346}
}

@book{Lee1990,
  author    = {Lee, A. J.},
  title     = {U-Statistics: Theory and Practice},
  publisher = {Marcel Dekker},
  address   = {New York},
  year      = {1990}
}

@book{Serfling1980,
  author    = {Serfling, Robert J.},
  title     = {Approximation Theorems of Mathematical Statistics},
  publisher = {John Wiley \& Sons},
  address   = {New York},
  year      = {1980}
}

@book{vanderVaart1998,
  author    = {van der Vaart, Aad W.},
  title     = {Asymptotic Statistics},
  publisher = {Cambridge University Press},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  year      = {1998}
}

Prerequisites

45.04.01
37.04.01
37.03.02

Tier anchors

beginner: Wasserman, All of Statistics §9 (estimators built by averaging over pairs); Hollander-Wolfe, Nonparametric Statistical Methods Ch. 4 (Wilcoxon, Mann-Whitney, Kendall's tau as averages over pairs)
intermediate: van der Vaart, Asymptotic Statistics (Cambridge, 1998) Ch. 12 (U-statistics, the Hoeffding decomposition, projections, asymptotic normality); Serfling, Approximation Theorems of Mathematical Statistics Ch. 5
master: Lee, U-Statistics: Theory and Practice (Marcel Dekker, 1990) Ch. 1-3; van der Vaart, Asymptotic Statistics (Cambridge, 1998) Ch. 11-12 (the projection / Hájek-projection method, the H-decomposition, degenerate limits); Hoeffding, A class of statistics with asymptotically normal distribution (1948)

References

van der Vaart — Asymptotic Statistics · Cambridge University Press, 1998; Ch. 11 (projections) and Ch. 12 (U-statistics, Hoeffding decomposition, asymptotic normality)
Hoeffding — A class of statistics with asymptotically normal distribution · Annals of Mathematical Statistics 19 (1948), 293-325
Lee — U-Statistics: Theory and Practice · Marcel Dekker, New York, 1990; Ch. 1-3 (kernels, the H-decomposition, variance, normal and degenerate limits)
Serfling — Approximation Theorems of Mathematical Statistics · Wiley, New York, 1980; Ch. 5 (U-statistics)
Hájek — Asymptotic normality of simple linear rank statistics under alternatives · Annals of Mathematical Statistics 39 (1968), 325-346 (the projection lemma)

Estimated time

beginner: 20m
intermediate: 55m
master: 95m