Chapter 13: U-statistics (Part 1)

1. Why Study U-statistics?

1.1 Core Idea

In statistics, many estimands of interest are not expectations of a single observation, but rather expectations of a function of several independent observations:

\[ \theta(P) = E h(X_1, \dots, X_m), \quad X_i \stackrel{iid}{\sim} P \]

A U-statistic estimates this quantity by averaging the function \(h\) over all distinct \(m\)-tuples in the sample.

Applications:

• Classical statistics: Unbiased sample variance, Gini mean difference, Kendall's tau, Mann-Whitney/Wilcoxon statistic.

• Statistical inference: Asymptotic variance estimation, confidence intervals, permutation tests, rank tests.

• Modern machine learning: AUC/ranking problems, kernel two-sample tests based on MMD, independence tests based on HSIC, scalable incomplete U-statistics.

1.2 Intuition: Averaging over all subsamples

Suppose we have a simple unbiased estimator that uses only \(m\) observations:

\[ h(X_1, \dots, X_m), \quad E h(X_1, \dots, X_m) = \theta \]

In a sample of size \(n\), there are many subsets of size \(m\). Instead of choosing just one subset, we average over all such subsets:

\[ U_n = \binom{n}{m}^{-1} \sum_{1 \le i_1 < \dots < i_m \le n} h(X_{i_1}, \dots, X_{i_m}) \]

Intuitive explanation: Given an unordered sample, averaging the naive estimator over all possible relabelings removes the artificial randomness introduced by choosing a particular subsample. This typically reduces variance while maintaining unbiasedness.

---

1.3 Example: Sample variance

Variance can be written as a two-sample functional:

\[ \sigma^2 = \frac{1}{2} E(X_1 - X_2)^2 \]

Thus, the unbiased sample variance can be expressed as:

\[ \binom{n}{2}^{-1} \sum_{1 \le i < j \le n} \frac{(X_i - X_j)^2}{2} = \frac{1}{n-1} \sum_{i=1}^n (X_i - \bar{X}_n)^2 \]

• Our commonly used formula for sample variance is not an ad hoc formula.
• It is actually the complete average of the unbiased estimator \(\frac{(X_1 - X_2)^2}{2}\) based on two observations.

---

2. The Principles of Mathematical Statistics Behind U-statistics

The original reason for introducing U-statistics was not just "stability through averaging"; it is a classic construction in mathematical statistics.

2.1 Starting Point: Estimable functional

If there exists a measurable function \(h\) such that:

\[ \theta(P) = E_P h(X_1, \dots, X_m) \]

where \(X_1, \dots, X_m \stackrel{iid}{\sim} P\), then the parameter \(\theta = \theta(P)\) is called an estimable functional of degree \(m\). In this case, \(h(X_1, \dots, X_m)\) is the naive unbiased estimator of \(\theta\) based on only \(m\) observations.

• If \(m=1\), the most natural estimator is the sample mean of \(h(X_i)\).
• If \(m \ge 2\), the sample contains many equally valid \(m\)-subsamples.
• The U-statistic is essentially the Rao-Blackwellized version of the naive estimator, removing the arbitrariness of subsample selection.

2.2 Examples of Estimable Functionals

Degree	Functional \(\theta(P)\)	Unbiased kernel \(h\)	Interpretation
1	\(\mu = EX\)	\(h(x) = x\)	Many nonlinear parameters are essentially expectations, but expectations based on several independent copies.
1	\(EX^r\)	\(h(x) = x^r\)	U-statistics are the natural unbiased extension of sample means for such functionals.
2	\(\mu^2\)	\(h(x_1, x_2) = x_1 x_2\)
2	\(\sigma^2\)	\(h(x_1, x_2) = (x_1 - x_2)^2 / 2\)
2	\(F(t)^2\)	\(h(x_1, x_2) = \mathbb{I}(x_1 \le t)\mathbb{I}(x_2 \le t)\)
2	\(\mathbb{P}(X < Y)\)	\(h(x, y) = \mathbb{I}(x < y)\)	Two-sample

---

3. Sufficient Statistics and the Rao-Blackwell Principle

3.1 Unordered Sample as a Sufficient Statistic

Let the order statistic (or, when ties may exist, the unordered sample/empirical measure \(P_n\)) be:

\[ T = (X_{(1)}, \dots, X_{(n)}) \]

• For i.i.d. samples from any distribution \(P\), the unordered sample \(T\) is sufficient for \(P\).
• Equivalently, given \(T\), the remaining randomness is just the random assignment of labels to the observations.
• This conditional label distribution is free of \(P\): all label permutations are equally likely (accounting for multiplicities if ties exist).

3.2 Rao-Blackwell Principle

If \(A\) is an unbiased estimator, then the conditional expectation \(E(A|T)\) remains unbiased, and:

\[ Var\{E(A|T)\} \le Var(A) \]

Thus, conditioning on the unordered sample removes label noise without changing the target of estimation.

---

4. Key Identity: Conditional Expectation Constructs the U-statistic

Start from the naive unbiased estimator:

\[ A = h(X_1, \dots, X_m), \quad E A = \theta \]

Given the unordered sample \(T\), the first \(m\) labels are drawn uniformly without replacement from \(\{1, \dots, n\}\). Therefore:

\[ E\{h(X_1, \dots, X_m) | T\} = \frac{(n-m)!}{n!} \sum_{(i_1, \dots, i_m): \text{distinct}} h(X_{i_1}, \dots, X_{i_m}) \]

\[ = \binom{n}{m}^{-1} \sum_{1 \le i_1 < \dots < i_m \le n} h^{sym}(X_{i_1}, \dots, X_{i_m}) \]

If the kernel \(h\) is symmetric, then this is exactly the U-statistic:

\[ U_n = \binom{n}{m}^{-1} \sum_{1 \le i_1 < \dots < i_m \le n} h(X_{i_1}, \dots, X_{i_m}) \]

4.1 Implications of the Rao-Blackwell Construction

The identity above provides a finite-sample explanation of why "complete averaging" is the canonical estimator.

1. Unbiasedness:

   \[ E U_n = E\{E(A|T)\} = E A = \theta \]

2. Variance reduction relative to a single subsample:

   \[ Var(U_n) = Var\{E(A|T)\} \le Var(A) \]

3. Connection to UMVU theory: In parametric models, if \(T\) is complete and sufficient, then by the Lehmann-Scheffé theorem, the same conditional expectation is the uniformly minimum variance unbiased estimator (UMVU).

What remains nontrivial: The terms in the sum of \(U_n\) are dependent due to overlap between different subsamples. The subsequent sections of this chapter develop projection and overlap tools to quantify this dependence.

---

5. In-depth Classic Examples

5.1 Example: Deriving sample variance via Rao-Blackwellization

For \(\theta = \sigma^2\), the unbiased estimator based on two observations is:

\[ A = \frac{(X_1 - X_2)^2}{2}, \quad E A = \frac{1}{2} E(X_1 - X_2)^2 = \sigma^2 \]

Conditioning on the unordered sample \(T\) yields:

\[ E(A|T) = \binom{n}{2}^{-1} \sum_{1 \le i < j \le n} \frac{(X_i - X_j)^2}{2} = \frac{1}{n-1} \sum_{i=1}^n (X_i - \bar{X}_n)^2 \]

Thus, the familiar unbiased sample variance is the Rao-Blackwellized version of the naive two-point estimator.

Note: The formula with denominator \(n-1\) is not an empirical correction trick; it is a natural consequence of averaging over all data pairs.

5.2 Example: Removing the diagonal bias

Fix \(t \in \mathbb{R}\) and let \(p = F(t)\). The parameter \(p^2\) has the following unbiased two-sample kernel:

\[ h(x_1, x_2) = \mathbb{I}(x_1 \le t)\mathbb{I}(x_2 \le t) \]

The corresponding U-statistic is:

\[ U_n(t) = \frac{1}{n(n-1)} \sum_{i \ne j} \mathbb{I}(X_i \le t)\mathbb{I}(X_j \le t) \]

If we let \(N_t = \sum_{i=1}^n \mathbb{I}(X_i \le t)\), then:

\[ U_n(t) = \frac{N_t(N_t - 1)}{n(n-1)}, \quad E U_n(t) = p^2 \]

In contrast, the traditional plug-in estimator includes the diagonal terms and satisfies:

\[ F_n(t)^2 = (N_t / n)^2 \]

\[ E F_n(t)^2 = p^2 + \frac{p(1-p)}{n} \]

(with a bias of \(O(1/n)\)).

---

6. From Intuition to Asymptotic Theory

The Rao-Blackwell picture explains the construction of U-statistics; the projection picture will explain their asymptotic properties.

• Reveals how the conditional expectation of the kernel changes with one observation (first-order effect):

  \[ h_1(x) - \theta = E\{h(x, X_2, \dots, X_m)\} - \theta \]

  If the variance of this first-order effect is positive, then many weakly dependent overlapping terms sum to a normal limit:

  \[ \sqrt{n}(U_n - \theta) \approx \frac{m}{\sqrt{n}} \sum_{i=1}^n \{h_1(X_i) - \theta\} \]

• If the first-order effect is zero, the statistic is degenerate, and higher-order interactions determine its convergence rate and limiting distribution.

Summary: U-statistics emerge from sufficiency and Rao-Blackwellization, but their analysis relies primarily on Hoeffding's projection.

---

7. Formal Definitions: Symmetric Kernels and U-statistics

Assume \(X_1, \dots, X_n \stackrel{iid}{\sim} P\) on a measurable space \((\mathcal{X}, \mathcal{A})\), and fix \(m < n\).

Definition 9.1 (Symmetric kernel)

A measurable function \(h: \mathcal{X}^m \rightarrow \mathbb{R}\) is called a symmetric kernel of order \(m\) if for any permutation \(\pi\) of \(\{1, \dots, m\}\),

\[ h(x_1, \dots, x_m) = h(x_{\pi(1)}, \dots, x_{\pi(m)}) \]

If \(h\) is not symmetric, it can be replaced by its symmetrization:

\[ h^{sym}(x_1, \dots, x_m) = \frac{1}{m!} \sum_{\pi} h(x_{\pi(1)}, \dots, x_{\pi(m)}) \]

If the original statistic averages over unordered subsets, the U-statistic remains unchanged after symmetrization.

Definition 9.2 (U-statistic)

Assume \(E|h(X_1, \dots, X_m)| < \infty\) and define:

\[ \theta = \theta(P) = E h(X_1, \dots, X_m) \]

The U-statistic based on the kernel \(h\) of order \(m\) is defined as:

\[ U_n = \binom{n}{m}^{-1} \sum_{1 \le i_1 < \dots < i_m \le n} h(X_{i_1}, \dots, X_{i_m}) \]

Clearly, \(E U_n = \theta\). The "U" stands for Unbiasedness: the expectation of each term is \(\theta\).

---

8. Relationship with Plug-in and V-statistics

The empirical distribution can be written as \(P_n = n^{-1} \sum_{i=1}^n \delta_{X_i}\). A natural plug-in estimator is the V-statistic:

\[ V_n = \int h(x_1, \dots, x_m) dP_n(x_1) \dots dP_n(x_m) = \frac{1}{n^m} \sum_{i_1, \dots, i_m = 1}^n h(X_{i_1}, \dots, X_{i_m}) \]

• \(V_n\) includes repeated indices, so it may be biased for finite \(n\).
• \(U_n\) removes repeated indices and is strictly unbiased.
• For fixed \(m\) and regular kernels, the difference between \(U_n\) and \(V_n\) is typically \(O_p(n^{-1})\), but this difference can be important when dealing with degenerate limits.

9. Core Examples in Modern and Classical Statistics

9.1 Rank Example: Kendall's tau

Example 9.3 (Kendall's tau)

For bivariate data \(Z_i = (X_i, Y_i)\), the parameter of interest is:

\[ \tau = E[\text{sign}\{(X_1 - X_2)(Y_1 - Y_2)\}] \]

The corresponding kernel is:

\[ h(z_1, z_2) = \text{sign}\{(x_1 - x_2)(y_1 - y_2)\} \]

The resulting U-statistic estimator is:

\[ \hat{\tau} = \binom{n}{2}^{-1} \sum_{i < j} h(Z_i, Z_j) \]

It is often used to measure monotone association between variables.

9.2 Classic Test: Mann-Whitney and AUC

Example 9.4 (Mann-Whitney parameter and AUC)

For two independent samples \(X_1, \dots, X_n \sim P\) and \(Y_1, \dots, Y_N \sim Q\), the parameter is defined as:

\[ \theta = \mathbb{P}(X > Y) + \frac{1}{2}\mathbb{P}(X = Y) \]

This parameter can be estimated by a two-sample U-statistic:

\[ U_{n,N} = \frac{1}{nN} \sum_{i=1}^n \sum_{j=1}^N \left\{ \mathbb{I}(X_i > Y_j) + \frac{1}{2}\mathbb{I}(X_i = Y_j) \right\} \]

In machine learning, this corresponds to the population AUC (Area Under the ROC Curve) for a scoring rule.

9.3 Kernel Two-sample Test: MMD

Let \(X, X' \sim P\) and \(Y, Y' \sim Q\) be independent, and let \(k\) be a positive definite kernel. The squared Maximum Mean Discrepancy (MMD) is defined as:

\[ \text{MMD}^2(P, Q) = E k(X, X') + E k(Y, Y') - 2 E k(X, Y) \]

For paired observations \(Z_i = (X_i, Y_i)\), its unbiased estimator is a second-order U-statistic:

\[ \widehat{\text{MMD}}_u^2 = \binom{n}{2}^{-1} \sum_{i < j} h(Z_i, Z_j) \]

where the symmetric kernel is:

\[ h(z_i, z_j) = k(x_i, x_j) + k(y_i, y_j) - k(x_i, y_j) - k(x_j, y_i) \]

• Property: Under the null hypothesis \(H_0: P = Q\), the first-order projection of this kernel is zero. Therefore, the statistic is degenerate, and its null limiting distribution is a weighted chi-square type.

9.4 Kernel Independence Test: HSIC

Let \(Z = (X, Y)\), and let \(k\) and \(l\) be kernels on the spaces of \(X\) and \(Y\), respectively. The Hilbert-Schmidt Independence Criterion (HSIC) satisfies: for characteristic kernels,

\[ \text{HSIC}(P_{XY}, k, l) = 0 \quad \text{if and only if } X \text{ and } Y \text{ are independent} \]

• The unbiased empirical HSIC is a U-statistic of order 4.
• Under the independence assumption, it is degenerate: its first-order projection vanishes.
• This explains why its null distribution is not a simple normal limit; in practice, spectral methods, permutation tests, or wild-bootstrap are used for approximation.

Key takeaway: Degenerate U-statistics are not theoretical curiosities; they are at the absolute core of modern kernel tests.

---

10. Conditional Projections and Hoeffding's Variance Formula

To quantify the dependence among cross-terms in a U-statistic, we introduce conditional projection tools.

10.1 Conditional Projections

Assume the kernel has finite second moment: \(E h^2(X_1, \dots, X_m) < \infty\). For \(k = 0, 1, \dots, m\), define the conditional expectation projection:

• For \(k=0\):

\[ h_0 = \theta \]

• For \(1 \le k \le m\):

\[ h_k(x_1, \dots, x_k) = E\{h(x_1, \dots, x_k, X_{k+1}, \dots, X_m)\} \]

Note that \(h_m = h\), and the expectation satisfies:

\[ E h_k(X_1, \dots, X_k) = \theta \]

Next, define the centered projection:

\[ \tilde{h}_k(x_1, \dots, x_k) = h_k(x_1, \dots, x_k) - \theta \]

and the corresponding projection variance:

\[ \xi_k = Var\{h_k(X_1, \dots, X_k)\} \]

10.2 Monotonicity of the Projection Variances

By the tower property of conditional expectation:

\[ h_k(X_1, \dots, X_k) = E\{h_{k+1}(X_1, \dots, X_{k+1}) | X_1, \dots, X_k\} \]

Applying Jensen's inequality yields:

\[ \xi_k \le \xi_{k+1} \]

where \(\xi_0 = 0\) and \(\xi_m = Var\{h(X_1, \dots, X_m)\}\).

• Intuition: For \(k = 0, 1, \dots, m-1\), the projection variance \(\xi_k\) measures how much of the total variation of the kernel is already explained by knowing \(k\) of its \(m\) arguments.

10.3 Hoeffding's Variance Formula

Theorem 9.5 (Hoeffding's variance formula)

If \(E h^2(X_1, \dots, X_m) < \infty\), then the exact variance of the U-statistic is:

\[ Var(U_n) = \binom{n}{m}^{-1} \sum_{k=1}^m \binom{m}{k} \binom{n-m}{m-k} \xi_k \]

Moreover, it satisfies the following important properties:

• 1. Upper and lower bounds:

\[ \frac{m^2}{n} \xi_1 \le Var(U_n) \le \frac{m}{n} \xi_m \]

• 2. Monotonicity in sample size:

\[ (n+1)Var(U_{n+1}) \le n Var(U_n) \]

• 3. Asymptotic variance under degeneracy: If there exists an integer \(r\) such that \(\xi_1 = \dots = \xi_{r-1} = 0\) and \(\xi_r > 0\), then:

\[ Var(U_n) = \frac{r! \binom{m}{r}^2 \xi_r}{n^r} + O(n^{-(r+1)}) \]

Proof of Theorem 9.5 (click to expand)

Step 1: Computing covariance by overlap

Let \(\tilde{h} = h - \theta\) be the centered kernel. If index subsets \(I\) and \(J\) have exactly \(k\) common elements (i.e., \(|I \cap J| = k\)), then conditioning on those \(k\) common observations yields:

\[ E\{\tilde{h}(X_I)\tilde{h}(X_J)\} = E \left[ E\{\tilde{h}(X_I) | X_{I \cap J}\} E\{\tilde{h}(X_J) | X_{I \cap J}\} \right] \]

By the definition of projections, this equals:

\[ = E\{\tilde{h}_k(X_1, \dots, X_k)^2\} = \xi_k \]

This is the most crucial step: the covariance depends only on the number \(k\) of shared indices between the two subsets.

Step 2: Counting overlaps

Fix a particular subset \(I\). We need to count how many subsets \(J\) of size \(m\) share exactly \(k\) elements with \(I\). Combinatorially, this is equivalent to choosing \(k\) elements from the \(m\) elements of \(I\), and \(m-k\) elements from the \(n-m\) elements not in \(I\):

\[ \binom{m}{k}\binom{n-m}{m-k} \]

Expanding the variance as a double sum:

\[ Var(U_n) = \binom{n}{m}^{-2} \sum_{I} \sum_{J} Cov\{h(X_I), h(X_J)\} \]

Grouping terms:

\[ = \binom{n}{m}^{-2} \sum_{I} \sum_{k=1}^m \binom{m}{k}\binom{n-m}{m-k} \xi_k \]

The outer sum over \(I\) has \(\binom{n}{m}\) terms, hence:

\[ = \binom{n}{m}^{-1} \sum_{k=1}^m \binom{m}{k}\binom{n-m}{m-k} \xi_k \]

(Note: when \(k=0\), the two subsets are completely independent, covariance is 0, and the corresponding term vanishes.) This completes the proof. \(\square\)

10.4 Rates: Why Degeneracy Matters

Analyzing the coefficients of \(\xi_k\) in the variance formula, we can perform an asymptotic expansion:

\[ \binom{n}{m}^{-1}\binom{m}{k}\binom{n-m}{m-k} = \binom{m}{k}^2 k! n^{-k} + O(n^{-(k+1)}) \]

Thus, the first non-zero projection variance determines the stochastic order of the U-statistic.

If \(\xi_1 = \dots = \xi_{r-1} = 0\) and \(\xi_r > 0\), then the fluctuation is:

\[ U_n - \theta = O_p(n^{-r/2}) \]

• When \(r = 1\): The U-statistic is non-degenerate, with \(\sqrt{n}\) rate and normal limit distribution.
• When \(r = 2\): The U-statistic is degenerate of order 2, with a faster convergence rate (\(n^{-1}\)), and the limit distribution is non-Gaussian (typically a weighted sum of infinitely many chi-square random variables).

11. Asymptotic Properties of U-Statistics

In the asymptotic theory of U-statistics, the main challenge is: when \(m > 1\), the U-statistic \(U_n\) is not a simple sum of independent random variables (even though the original sample \(\{X_i\}\) is independent, different subsamples overlap). This prevents direct application of the classical central limit theorem (CLT) for independent random variables.

Solution: Find the projection of \(U_n\) onto the individual observations \(X_1, \dots, X_n\). Specifically, by computing the conditional expectations \(E(U_n|X_i)\) (\(i=1, \dots, n\)), we construct a new statistic:

\[ \tilde{U}_n = EU_n + \sum_{i=1}^n \{E(U_n|X_i) - EU_n\} \]

Since \(X_i\) are independent, \(\tilde{U}_n\) is a sum of i.i.d. random variables, and the CLT can be applied directly. If we can show that the residual term \(U_n - \tilde{U}_n\) is asymptotically negligible, then by Slutsky's theorem, the asymptotic normality of \(U_n\) follows.

11.1 Definition and Lemma for Projection of U-statistics

Definition 9.6 (Projection)

Let \(U_n\) be a U-statistic based on the sample \(\{X_1, \dots, X_n\}\). The projection of \(U_n\) onto \(\{X_1, \dots, X_n\}\) is defined as:

\[ \tilde{U}_n = EU_n + \sum_{i=1}^n \{E(U_n|X_i) - EU_n\} := \theta + \sum_{i=1}^n \{\varphi_n(X_i) - \theta\} \quad \text{--- (9.1)} \]

where \(\varphi_n(X_i) = E(U_n|X_i)\).

If \(\{X_i\}\) are i.i.d. (or independent), then the sequence \(\{\varphi_n(X_i)\}\) is also i.i.d. (or independent). Clearly, by properties of conditional expectation, \(E\tilde{U}_n = \theta\) (if \(h = h_m\), then equals \(EU_n\)).

Based on the covariance property \(cov(U_n, \tilde{U}_n) = var(\tilde{U}_n)\) (see Shao p179), we obtain the following key lemma regarding the variance of the projection error:

Lemma 9.7

Let \(U_n\) be a U-statistic with \(var(U_n) < \infty\) for each \(n\). Then:

\[ E(U_n - \tilde{U}_n)^2 = var(U_n - \tilde{U}_n) = var(U_n) - var(\tilde{U}_n) \]

11.2 Asymptotic Distribution Theorem for U-statistics

Theorem 9.8 (Limit distribution of U-statistics)

Let \(U_n\) be a U-statistic based on i.i.d. sample \(\{X_i\}_{i=1}^n\), and assume \(Eh^2(X_1, \dots, X_m) < \infty\).

• (i) Non-degenerate case: If the first-order projection variance \(\xi_1 = var(\tilde{h}_1(X)) > 0\), then:

\[ \sqrt{n}(U_n - EU_n) \xrightarrow{d} N(0, m^2\xi_1) \]

• (ii) First-order degenerate case: If \(\xi_1 = 0\) but \(\xi_2 > 0\), then:

\[ n(U_n - EU_n) \xrightarrow{d} \frac{m(m-1)}{2} \sum_{j=1}^\infty \lambda_j(\chi_{1,j}^2 - 1) \]

where \(\{\chi_{1,j}^2\}_{j \ge 1}\) are i.i.d. \(\chi_1^2\) random variables, and \(\lambda_j\) are constants (eigenvalues) satisfying \(\sum_{j=1}^\infty \lambda_j^2 = \xi_2\).

---

11.3 Proof of Theorem 9.8 (i) (Non-degenerate case)

Proof of Theorem 9.8 (i) (click to expand)

First, compute the conditional expectation \(E(U_n|X_1)\):

\[ E(U_n|X_1) = \binom{n}{m}^{-1} \sum_{I} E(h(X_{i_1}, \dots, X_{i_m})|X_1) \]

Split it into two parts:

\[ = \binom{n}{m}^{-1} \left\{ \sum_{I_1} E(h(X_{i_1}, \dots, X_{i_m})|X_1) + \sum_{I_2} \theta \right\} \]

where \(I_1\) consists of all combinations \((i_1, \dots, i_m)\) that contain index \(1\), and \(I_2\) consists of the other combinations not containing \(1\). By combinatorial counting:

\[ |I_1| = \binom{n-1}{m-1}, \quad |I_2| = \binom{n-1}{m} \]

Substituting:

\[ E(U_n|X_1) = \frac{m!(n-m)!}{n!} \left[ \frac{(n-1)!}{(m-1)!(n-m)!} h_1(X_1) + \frac{(n-1)!}{m!(n-m-1)!} \theta \right] \]

After simplification:

\[ = \frac{m}{n} h_1(X_1) + \frac{n-m}{n} \theta \]

Next, construct the projection statistic \(\tilde{U}_n\):

\[ \tilde{U}_n = \theta + \sum_{i=1}^n \left\{ \frac{m}{n} h_1(X_i) + \frac{n-m}{n} \theta - \theta \right\} \]

Simplify:

\[ = \theta + \frac{m}{n} \sum_{i=1}^n \{h_1(X_i) - \theta\} = \theta + \frac{m}{n} \sum_{i=1}^n \tilde{h}_1(X_i) \]

By the CLT for i.i.d. random variables, since \(E\tilde{h}_1^2(X_1) < \infty\):

\[ \sqrt{n}(\tilde{U}_n - \theta) \xrightarrow{d} N(0, m^2\xi_1) \]

provided \(\xi_1 > 0\) (because \(var(\tilde{U}_n) = m^2\xi_1/n\)).

On the other hand, applying Lemma 9.7:

\[ E(U_n - \tilde{U}_n)^2 = var(U_n) - var(\tilde{U}_n) \]

Using the expansion of \(var(U_n)\) from Theorem 9.5:

\[ = \frac{m^2\xi_1}{n} + O(n^{-2}) - \frac{m^2\xi_1}{n} = O(n^{-2}) \]

By Chebyshev's inequality, for any \(\epsilon > 0\):

\[ P(\sqrt{n}|U_n - \tilde{U}_n| > \epsilon) \le \frac{n E(U_n - \tilde{U}_n)^2}{\epsilon^2} = O(n^{-1}) \rightarrow 0 \]

thus \(\sqrt{n}(U_n - \tilde{U}_n) = o_p(1)\). Finally, using the algebraic identity:

\[ \sqrt{n}(U_n - \theta) = \sqrt{n}(\tilde{U}_n - \theta) + \sqrt{n}(U_n - \tilde{U}_n) \]

Applying Slutsky's theorem:

\[ = \sqrt{n}(\tilde{U}_n - \theta) + o_p(1) \xrightarrow{d} N(0, m^2\xi_1) \]

This completes the proof. \(\square\)

---

11.4 Proof of Theorem 9.8 (ii) (Degenerate case)

Degenerate U-statistics correspond to \(\xi_1 = 0\). In this case, the scaling factor becomes \(n\) instead of \(\sqrt{n}\), and the limiting distribution is a linear combination of infinite chi-square variables.

Proof of Theorem 9.8 (ii) (click to expand)

We now prove the degenerate U-statistic theorem 9.8(ii). Our goal is to show:

\[ n(\hat{U}_n - \theta) := \frac{m(m-1)}{n-1} \sum_{1 \le i < j \le n} \tilde{h}_2(X_i, X_j) \xrightarrow{d} \frac{m(m-1)}{2} Y \]

where \(Y = \sum_{j=1}^\infty \lambda_j(W_j^2 - 1)\), and \(W_1^2, W_2^2, \dots\) are independent \(\chi_1^2\) random variables. Let:

\[ T_n = \frac{1}{n} \sum_{i \ne j} \tilde{h}_2(X_i, X_j) \]

Then:

\[ n(\hat{U}_n - \theta) = \frac{m(m-1)}{2} \frac{n}{n-1} T_n \]

Therefore, the goal reduces to proving \(T_n \xrightarrow{d} Y\). We will use characteristic functions to prove this, i.e., we need to show for any \(x\):

\[ E_F\{e^{ixT_n}\} \rightarrow E\{e^{ixY}\}, \quad n \rightarrow \infty \quad \text{--- (9.2)} \]

We will use a special representation of \(\tilde{h}_2(x, y)\). Let \(\{\phi_j(\cdot)\}\) be orthonormal eigenfunctions associated with eigenvalues \(\{\lambda_j\}\) corresponding to \(\tilde{h}_2\). That is, they satisfy:

\[ E_F\{\phi_j(X)\phi_k(X)\} = \begin{cases} 1, & j = k \\ 0, & j \ne k \end{cases} \]

and \(\tilde{h}_2(x, y)\) can be expressed as the mean square limit of \(\sum_{k=1}^K \lambda_k \phi_k(x) \phi_k(y)\) as \(K \rightarrow \infty\). That is:

\[ \lim_{K \rightarrow \infty} E_F\left\{ \left[ \tilde{h}_2(X_1, X_2) - \sum_{k=1}^K \lambda_k \phi_k(X_1) \phi_k(X_2) \right]^2 \right\} = 0 \]

In the mean square sense we write:

\[ \tilde{h}_2(x, y) = \sum_{k=1}^\infty \lambda_k \phi_k(x) \phi_k(y) \quad \text{--- (9.3)} \]

and correspondingly:

\[ \tilde{h}_1(x) = \sum_{k=1}^\infty \lambda_k \phi_k(x) E_F\{\phi_k(X)\} \quad \text{--- (9.4)} \]

Since the degeneracy condition \(\xi_1 = 0\) holds, we must have for all \(k\):

\[ E_F\{\phi_k(X)\} = 0 \quad \text{--- (9.5)} \]

Moreover, by orthogonality:

\[ E_F\left\{ \left[ \tilde{h}_2(X_1, X_2) - \sum_{k=1}^K \lambda_k \phi_k(X_1) \phi_k(X_2) \right]^2 \right\} = E_F\{\tilde{h}_2^2(X_1, X_2)\} - \sum_{k=1}^K \lambda_k^2 \]

which implies that the sum of squares of eigenvalues converges:

\[ \sum_{k=1}^\infty \lambda_k^2 = E_F\{\tilde{h}_2^2(X_1, X_2)\} < \infty \]

Substituting the representation into \(T_n\) yields:

\[ T_n = \frac{1}{n} \sum_{i \ne j} \sum_{k=1}^\infty \lambda_k \phi_k(X_i) \phi_k(X_j) \]

Now truncate to the first \(K\) terms and define \(T_{nK}\):

\[ T_{nK} = \frac{1}{n} \sum_{i \ne j} \sum_{k=1}^K \lambda_k \phi_k(X_i) \phi_k(X_j) \]

Using the inequality \(|e^{iz} - 1| \le |z|\) for complex numbers, we can bound the truncation error of the characteristic function:

\[ |E\{e^{ixT_n}\} - E\{e^{ixT_{nK}}\}| \le E|e^{ixT_n} - e^{ixT_{nK}}| \le |x| E|T_n - T_{nK}| \le |x| [E(T_n - T_{nK})^2]^{1/2} \quad \text{--- (9.6)} \]

Observe that \(T_n - T_{nK}\) is itself a U-statistic:

\[ T_n - T_{nK} = \frac{2}{n} \binom{n}{2} U_{nK} \]

where:

\[ U_{nK} = \binom{n}{2}^{-1} \sum_{i < j} g_K(X_i, X_j) \]

with the truncated kernel:

\[ g_K(x, y) = \tilde{h}_2(x, y) - \sum_{k=1}^K \lambda_k \phi_k(x) \phi_k(y) \]

It can be verified that this truncated kernel satisfies:

\[ E_F\{g_K(X_1, X_2)\} = 0 \]

\[ E_F\{g_K^2(X_1, X_2)\} = \sum_{k=K+1}^\infty \lambda_k^2 \]

\[ E_F\{g_K(x, X)\} = 0 \]

Hence \(E(U_{nK}) = 0\), and by Theorem 9.5:

\[ E\{U_{nK}^2\} = \binom{n}{2}^{-1} \sum_{k=K+1}^\infty \lambda_k^2 \]

Therefore:

\[ E(T_n - T_{nK})^2 = (n-1)^2 \binom{n}{2}^{-1} \sum_{k=K+1}^\infty \lambda_k^2 \le 2 \sum_{k=K+1}^\infty \lambda_k^2 \quad \text{--- (9.7)} \]

Now fix \(x\) and let \(\epsilon > 0\). Choose and fix \(K\) large enough so that:

\[ |x| \left( 2 \sum_{k=K+1}^\infty \lambda_k^2 \right)^{1/2} < \epsilon \]

Combining (9.6) and (9.7), we have established:

\[ |E\{e^{ixT_n}\} - E\{e^{ixT_{nK}}\}| < \epsilon, \quad \text{for all } n \quad \text{--- (9.8)} \]

Next we prove:

\[ T_{nK} \Rightarrow Y_K = \sum_{k=1}^K \lambda_k (W_k^2 - 1) \quad \text{--- (9.9)} \]

We can write \(T_{nK}\) as:

\[ T_{nK} = \sum_{k=1}^K \lambda_k (W_{kn}^2 - Z_{kn}) \]

where \(W_{kn} = n^{-1/2} \sum_{i=1}^n \phi_k(X_i)\) and \(Z_{kn} = n^{-1} \sum_{i=1}^n \phi_k^2(X_i)\). From the earlier conditions, for all \(k\) and \(n\), \(E(W_{kn}) = 0\) and:

\[ Cov\{W_{jn}, W_{kn}\} = \begin{cases} 1, & j = k \\ 0, & j \ne k \end{cases} \quad \text{for all } j, k \text{ and } n \]

Thus, by the multivariate Lindeberg-Levy CLT:

\[ (W_{1n}, \dots, W_{Kn}) \xrightarrow{d} N(0, I_{K \times K}) \]

Meanwhile, because \(E_F\{\phi_k^2(X)\} = 1\), the classical strong law of large numbers (SLLN) gives:

\[ (Z_{1n}, \dots, Z_{Kn}) \xrightarrow{wp1} (1, \dots, 1) \]

This proves (9.9), i.e., for sufficiently large \(n\):

\[ |E\{e^{ixT_{nK}}\} - E\{e^{ixY_K}\}| < 2\epsilon \quad \text{--- (9.10)} \]

Finally, we prove:

\[ |E\{e^{ixY_K}\} - E\{e^{ixY}\}| < \epsilon [E(W_1^2 - 1)^2]^{1/2}, \quad \text{for all } n \quad \text{--- (9.11)} \]

To complete this step, we define the random variables \(W_1^2, W_2^2, \dots\) on a common probability space, and express \(Y\) as the mean square limit of \(Y_K\) as \(K \rightarrow \infty\). Then:

\[ |E\{e^{ixY_K}\} - E\{e^{ixY}\}| \le |x| [E(Y - Y_K)^2]^{1/2} \]

\[ \le |x| [E(W_1^2 - 1)^2]^{1/2} \left[ \sum_{k=K+1}^\infty \lambda_k^2 \right]^{1/2} \]

This yields (9.11). Combining (9.8), (9.10), and (9.11), for any \(x\), any \(\epsilon > 0\), and sufficiently large \(n\), we have:

\[ |E\{e^{ixT_n}\} - E\{e^{ixY}\}| \le \epsilon \{2 + [E(W_1^2 - 1)^2]^{1/2}\} \]

This proves \(T_n \xrightarrow{d} Y\) as \(n \rightarrow \infty\), which is the desired result of Theorem 9.8 (ii). \(\square\)

12. Degeneracy and Hypothesis Testing

Many test statistics in practical applications have the following pattern:

• Non-degenerate under the alternative hypothesis \(H_1\);

• Degenerate under the null hypothesis \(H_0\).

Classic examples:

• MMD (Maximum Mean Discrepancy): When \(P \ne Q\), it has a normal limit with \(\sqrt{n}\) rate; under \(P = Q\), it has a degenerate weighted chi-squared limiting distribution.

• HSIC (Hilbert-Schmidt Independence Criterion): When variables are dependent, it has a normal limit with \(\sqrt{n}\) rate; when variables are independent, it exhibits a degenerate limit.

• Cramer-von Mises test and integrated squared density test: Their null hypothesis limits typically come from degenerate quadratic forms.

Inference consequence:

The normal approximation that holds under a fixed alternative typically fails under the null hypothesis. Therefore, when conducting hypothesis tests, we often need to resort to Permutation, Spectral or Bootstrap calibration to obtain correct critical values.

---

13. Classical Application Examples of U-statistics

13.1 Example 1: Sample Variance

Example 1: Sample variance

Let the population satisfy \(\mu = E X\) and \(\sigma^2 = Var(X)\), and assume the fourth central moment is finite \(\mu_4 = E(X-\mu)^4 < \infty\).

Use the kernel:

\[ h(x, y) = \frac{(x-y)^2}{2} \]

The target parameter to be estimated is \(\theta = \sigma^2\).

Compute its first projection function \(h_1(x)\):

\[ h_1(x) = E \left\{ \frac{(x-X')^2}{2} \right\} = \frac{(x-\mu)^2 + \sigma^2}{2} \]

Thus we obtain the centered first projection:

\[ h_1(x) - \theta = \frac{(x-\mu)^2 - \sigma^2}{2} \]

Compute the variance of the first projection \(\xi_1\):

\[ \xi_1 = \frac{1}{4} Var\{(X-\mu)^2\} = \frac{\mu_4 - \sigma^4}{4} \]

The corresponding U-statistic is exactly the unbiased sample variance:

\[ U_n = \binom{n}{2}^{-1} \sum_{i<j} \frac{(X_i - X_j)^2}{2} = \frac{1}{n-1} \sum_{i=1}^n (X_i - \bar{X}_n)^2 \]

If \(\mu_4 > \sigma^4\), this is the non-degenerate case, and by the Central Limit Theorem (CLT) we have:

\[ \sqrt{n}(U_n - \sigma^2) \xrightarrow{d} N(0, 4\xi_1) = N(0, \mu_4 - \sigma^4) \]

Note: For a Gaussian (normal) data distribution, since \(\mu_4 = 3\sigma^4\), the asymptotic variance is \(2\sigma^4\).

13.2 Example 2: Product Kernel and Degenerate Boundary

Example 2: Product kernel

Let the kernel be \(h(x, y) = x y\). Then:

\[ \theta = (E X)^2 = \mu^2 \]

The first projection function and its variance are:

\[ h_1(x) = \mu x, \quad \xi_1 = Var\{\mu X\} = \mu^2 \sigma^2 \]

Case 1: Non-degenerate limit

• If \(\mu \ne 0\), the statistic is non-degenerate:

\[ \sqrt{n}(U_n - \mu^2) \xrightarrow{d} N(0, 4\mu^2 \sigma^2) \]

Case 2: Degenerate limit

• If \(\mu = 0\), the variance of the first projection \(\xi_1\) vanishes, and the statistic becomes degenerate.

This clearly shows that whether a U-statistic is degenerate may depend on the underlying true data distribution \(P\).

In the degenerate case \(\mu = 0\), we can explicitly write its limiting distribution:

\[ U_n = \frac{1}{n(n-1)} \sum_{i \ne j} X_i X_j \]

Since \(\bar{X}_n^2 = \frac{1}{n^2} \left\{ \sum_{i \ne j} X_i X_j + \sum_{i=1}^n X_i^2 \right\}\), we obtain:

\[ n U_n = \frac{n}{n-1} n \bar{X}_n^2 - \frac{1}{n-1} \sum_{i=1}^n X_i^2 \]

By the Central Limit Theorem and the Law of Large Numbers:

\[ n U_n \xrightarrow{d} \sigma^2(\chi_1^2 - 1) \]

This perfectly matches the limit result from second-order degenerate theory containing one non-zero eigenvalue.

13.3 Example 3: Gini Mean Difference

Example 3: Gini mean difference

For a univariate distribution, the target parameter of the Gini mean difference is:

\[ \theta = E|X_1 - X_2| \]

Its U-statistic estimator is:

\[ U_n = \binom{n}{2}^{-1} \sum_{i<j} |X_i - X_j| \]

The first projection function is:

\[ h_1(x) = E|x - X'| \]

If \(Var\{h_1(X)\} > 0\), then:

\[ \sqrt{n}(U_n - \theta) \xrightarrow{d} N(0, 4 Var\{h_1(X)\}) \]

This is an example of a robust measure of scale/dispersion, and differentiability of the kernel is not required in this process.

13.4 Example 4: Kendall's tau

Example 4: Kendall's tau

For bivariate data \(Z = (X, Y)\), define the kernel:

\[ h(z_1, z_2) = \text{sign}\{(x_1 - x_2)(y_1 - y_2)\} \]

Its U-statistic estimator is:

\[ \hat{\tau} = \binom{n}{2}^{-1} \sum_{i<j} h(Z_i, Z_j) \]

This statistic estimates:

\[ \tau = \mathbb{P}\{(X_1 - X_2)(Y_1 - Y_2) > 0\} - \mathbb{P}\{(X_1 - X_2)(Y_1 - Y_2) < 0\} \]

• It is a nonparametric measure of dependence.

• In the non-degenerate case, its asymptotic variance is determined by \(4 Var\{h_1(Z)\}\).

• Rank tests are one of the earliest and most classical origins of U-statistic theory.

---

14. Asymptotic Confidence Intervals and Hypothesis Testing

14.1 Constructing Asymptotic Confidence Intervals

In the non-degenerate case, we know:

\[ \sqrt{n}(U_n - \theta) \xrightarrow{d} N(0, m^2\xi_1) \]

Based on this, we can construct a natural confidence interval:

\[ U_n \pm z_{1-\alpha/2} \frac{m\hat{\sigma}_1}{\sqrt{n}} \]

where \(\hat{\sigma}_1^2\) is a consistent estimator of the projection variance \(\xi_1 = Var\{h_1(X)\}\).

The difficulty is that the function \(h_1(x) = E h(x, X_2, \dots, X_m)\) depends on the unknown population distribution \(P\).

14.2 Estimating the Variance of the First Projection

To estimate \(\xi_1\), we define a leave-one-in average for each observation \(i\):

\[ \hat{h}_{1,i} = \binom{n-1}{m-1}^{-1} \sum_{i \in A, |A|=m} h(X_A) \]

This is the average of the kernel over all possible subsamples that include the observation \(X_i\). It is effectively an estimator of \(h_1(X_i)\).

Then we compute the sample variance of these values:

\[ \hat{\xi}_1 = \frac{1}{n-1} \sum_{i=1}^n (\hat{h}_{1,i} - U_n)^2 \]

Under standard regularity conditions with fixed \(m\), it can be shown that:

\[ \hat{\xi}_1 \xrightarrow{p} \xi_1 \]

Therefore, the standard error estimate of the U-statistic is:

\[ \widehat{se}(U_n) = \frac{m\sqrt{\hat{\xi}_1}}{\sqrt{n}} \]

14.3 Standard Template for Hypothesis Testing

Suppose we wish to test \(H_0: \theta = \theta_0\), and we know that the statistic is non-degenerate under the null hypothesis.

We can construct the following standardized test statistic:

\[ Z_n = \frac{\sqrt{n}(U_n - \theta_0)}{m\sqrt{\hat{\xi}_1}} \xrightarrow{d} N(0, 1) \]

When \(|Z_n| > z_{1-\alpha/2}\), we reject the null hypothesis at significance level \(\alpha\).

Degeneracy Warning

If \(\xi_1 = 0\) under the null hypothesis \(H_0\), the construction of the above statistic is invalid. The correct scaling and null limiting distribution will be completely different.

This warning is an extremely important core issue in kernel two-sample tests and kernel independence tests.

---

15. Two-Sample and Higher-Order U-statistics

15.1 Two-Sample U-statistics

Many statistics are used to compare two independent samples:

\[ X_1, \dots, X_n \stackrel{iid}{\sim} P, \quad Y_1, \dots, Y_N \stackrel{iid}{\sim} Q \]

The general form of a two-sample U-statistic is:

\[ U_{n,N} = \binom{n}{r}^{-1} \binom{N}{s}^{-1} \sum_{I, J} h(X_I, Y_J) \]

Classic examples include:

• Mann-Whitney / Wilcoxon statistic;

• Unbiased MMD estimator;

• Energy distance statistics.

The same projection philosophy applies to the two-sample case, with the difference that conditional projections onto the \(X\) sample and the \(Y\) sample need to be computed separately.

15.2 AUC and Ranking Loss

Let \(S\) be the score given by a model, and \(P_+\) and \(P_-\) be the distributions of the positive and negative classes, respectively. AUC is defined as:

\[ AUC = \mathbb{P}(S_+ > S_-) + \frac{1}{2}\mathbb{P}(S_+ = S_-) \]

The empirical AUC estimator is:

\[ \widehat{AUC} = \frac{1}{n_+ n_-} \sum_{i=1}^{n_+} \sum_{j=1}^{n_-} \left\{ \mathbb{I}(S_i^+ > S_j^-) + \frac{1}{2}\mathbb{I}(S_i^+ = S_j^-) \right\} \]

This is clearly a two-sample U-statistic. Its central limit theorem can be used to compute standard errors for classifier comparisons, which explains why pairwise ranking losses are naturally closely related to U-statistic theory.

15.3 MMD: Degeneracy under the Null Hypothesis

For MMD, its second-order kernel is:

\[ h(Z_i, Z_j) = k(X_i, X_j) + k(Y_i, Y_j) - k(X_i, Y_j) - k(X_j, Y_i) \]

Under the null hypothesis \(H_0: P = Q\):

\[ E\{h(Z_i, Z_j) | Z_i\} = 0 \]

This implies \(\xi_1 = 0\). Therefore, it has a weighted chi-squared limit:

\[ n \widehat{MMD}_u^2 \xrightarrow{d} \sum_{j=1}^\infty \lambda_j (Z_j^2 - 1) \]

The eigenvalues depend on the centered kernel. Under a fixed alternative \(H_1: P \ne Q\), the first projection is typically non-zero, and then:

\[ \sqrt{n}(\widehat{MMD}_u^2 - MMD^2(P,Q)) \]

will follow an asymptotic normal distribution.

15.4 HSIC: A Higher-Order Example

The unbiased HSIC estimator can be written as a fourth-order U-statistic:

\[ \widehat{HSIC}_u = \binom{n}{4}^{-1} \sum_{1 \le i < j < q < r \le n} h(Z_i, Z_j, Z_q, Z_r) \]

Its symmetric kernel is constructed from the product of centered \(X\) and \(Y\) kernels.

• If \(X\) and \(Y\) are dependent, the first projection is non-zero, and the statistic has a \(\sqrt{n}\)-rate normal limit.

• If \(X \perp Y\) (independent), the first projection vanishes, and the null limit is degenerate.

• Since independence implies exchangeability under the null hypothesis, permutation calibration is a very natural and effective approach.

---

16. Incomplete and Parameter-Dependent U-statistics in Scalable Learning

16.1 Incomplete U-statistics for Scalable Learning

A full U-statistic requires enumeration of all \(\binom{n}{m}\) subsets, which can be computationally prohibitive for large sample sizes.

Incomplete U-statistics randomly draw \(B\) subsets \(I_1, \dots, I_B\) and define:

\[ U_{n,B}^{inc} = \frac{1}{B} \sum_{b=1}^B h(X_{I_b}) \]

• If the subsets are sampled uniformly, it remains unbiased conditional on the data.

• Its variance consists of two parts: sampling noise from the data itself and Monte Carlo noise from subset sampling.

• In modern machine learning, this approach is widely used in large-scale kernel tests, Bagging, and the optimization of pairwise/ranking objective functions.

16.2 Integrated Squared Error Statistic

In nonparametric density estimation, let the kernel density estimator (KDE) be:

\[ \hat{f}_n(x) = \frac{1}{n b_n} \sum_{i=1}^n K\left( \frac{x - X_i}{b_n} \right) = \frac{1}{n} \sum_{i=1}^n K_{b_n}(x - X_i) \]

where \(K_b(t) = b^{-1} K(t/b)\), satisfying \(b_n \rightarrow 0\), \(n b_n \rightarrow \infty\). If we wish to test goodness-of-fit \(H_0: f = f_{\theta}\), a natural statistic is:

\[ T_n = \int \{ \hat{f}_n(x) - f_{\hat{\theta}_n}(x) \}^2 dx \]

The random quadratic part of this statistic can be expressed as a U-statistic whose kernel depends on the sample size \(n\).

16.3 The n-dependent Degenerate Kernel

Let:

\[ \mu_n(y) = E K_{b_n}(y - X) \]

The dominant random quadratic term involves the following kernel:

\[ h_n(x_1, x_2) = \frac{n-1}{n} \int \{K_{b_n}(y - x_1) - \mu_n(y)\} \{K_{b_n}(y - x_2) - \mu_n(y)\} dy \]

In this case:

\[ E\{h_n(x, X_2)\} = 0 \]

Therefore, the dominant off-diagonal term is a second-order degenerate U-statistic with an n-dependent kernel.

Conclusion insight: Smooth goodness-of-fit tests typically reduce to studying degenerate quadratic U-statistics, but the kernel and variance change with the smoothing bandwidth \(b_n\).

---

17. Summary and Practical Guide

17.1 How to Analyze a New U-statistic?

If you encounter a new U-statistic in your research, you can follow these steps:

• Identify the kernel \(h\) and the target parameter \(\theta = E h(X_1, \dots, X_m)\) to be estimated.

• If the initial kernel is not symmetric, symmetrize it.

• Compute the first projection \(h_1(x)\).

• Check whether the first projection variance \(\xi_1 = Var\{h_1(X)\}\) is positive (especially under the null hypothesis \(H_0\) for hypothesis testing).

• If \(\xi_1 > 0\): Use the standard central limit theorem with \(\sqrt{n}\) rate, asymptotic variance \(m^2\xi_1\).

• If \(\xi_1 = 0\): Compute the first non-zero higher-order projection. Expect a faster convergence rate and a non-Gaussian limiting distribution.

• For practical inference, either estimate the projection variance via a consistent estimator, or use resampling/spectral methods appropriate under the null hypothesis.

17.2 Main Takeaways

• Essential construction: U-statistics arise very naturally as Rao-Blackwellizations of naive unbiased estimators from unordered samples.

• Unbiased complete averaging: They estimate expectations of functionals involving multiple observations by complete symmetric averaging over all combinations.

• Handling dependence: Although summands are dependent, this can be rigorously handled via overlap counting and conditional projection arguments.

• Hoeffding decomposition: This decomposition technique neatly separates the statistic into orthogonal interaction terms of different orders.

• Non-degenerate case: Non-degenerate U-statistics satisfy asymptotic normality with variance \(m^2\xi_1/n\).

• Degenerate case: Degenerate U-statistics have completely different convergence rates, and the limiting distribution is typically a weighted chi-squared or higher-order chaos limit.

• Practical relevance: Degeneracy is far from a theoretical "pathological case"; it is absolutely central in modern kernel testing.

💬 Comments