U-statistics are the canonical unbiased estimators of parameters expressible as expectations of fixed-order kernels. Their Hoeffding decomposition is an orthogonal analysis-of-variance expansion: the first nonzero projection determines the rate and limit law. V-statistics include repeated indices and are natural plug-in functionals, but their diagonal terms can create bias.
Kernels and symmetrization
Definition. Let \(X_1,\ldots,X_n\) be i.i.d. \(P\), and let \(h:\mathcal X^m\to\mathbb R\) be symmetric with \[ \theta=Ph:=\mathbb E h(X_1,\ldots,X_m). \] The U-statistic generated by \(h\) is \[ U_nh=\binom nm^{-1} \sum_{1\le i_1\lt\cdots\lt i_m\le n} h(X_{i_1},\ldots,X_{i_m}). \]
Unbiasedness. If \(P|h|\lt\infty\), then \[ \mathbb E(U_nh)=\theta. \]
Proof. Every summand has the same expectation \(\theta\) by identical distribution and independence. Averaging \(\binom nm\) such expectations leaves \(\theta\).
A nonsymmetric kernel can be replaced by \[ h^{\mathrm{sym}}(x_1,\ldots,x_m) =\frac1{m!}\sum_{\pi\in S_m} h(x_{\pi(1)},\ldots,x_{\pi(m)}), \] without changing its expectation or the associated average over unordered subsets.
Example (variance). Since \[ \frac12\mathbb E(X_1-X_2)^2 =\operatorname{Var}(X), \] the kernel \(h(x,y)=(x-y)^2/2\) generates \[ U_nh =\frac1{n-1}\sum_{i=1}^n(X_i-\bar X)^2, \] the unbiased sample variance.
Hoeffding projections
Definition. For \(c=0,\ldots,m\), define \[ h_c(x_1,\ldots,x_c) =\mathbb E\{h(x_1,\ldots,x_c,X_{c+1},\ldots,X_m)\}. \] Set \(\pi_0h=\theta\), and recursively define the canonical projections \[ \pi_ch(x_1,\ldots,x_c) =h_c(x_1,\ldots,x_c) -\sum_{A\subsetneq\{1,\ldots,c\}} \pi_{|A|}h(x_A). \]
Degeneracy and orthogonality. For \(c\ge1\), \[ \mathbb E\{\pi_ch(X_1,\ldots,X_c)\mid X_1,\ldots,X_{c-1}\}=0. \] Canonical components based on different index sets are orthogonal in \(L^2\).
Proof. Conditional expectation of the recursive inclusion-exclusion formula cancels every term involving the last coordinate with its corresponding lower-order projection. For orthogonality, if two index sets differ, condition on all variables except one appearing in only one component; conditional degeneracy makes the product expectation zero.
Hoeffding decomposition. If \(h\in L^2(P^m)\), then \[ U_nh-\theta =\sum_{c=1}^m\binom mc U_n^{(c)}(\pi_ch), \] where \(U_n^{(c)}\) is the order-\(c\) U-statistic. The summands are mutually orthogonal, and \[ \operatorname{Var}(U_nh) =\sum_{c=1}^m \binom mc^2\binom nc^{-1} P^c(\pi_ch)^2. \]
Proof. The kernel identity \[ h(x_1,\ldots,x_m) =\theta+\sum_{\varnothing\ne A\subseteq[m]} \pi_{|A|}h(x_A) \] follows from Möbius inversion on subsets. Average it over all \(m\)-subsets of the sample. Each fixed \(c\)-subset occurs in \(\binom{n-c}{m-c}\) of them, and \[ \frac{\binom{n-c}{m-c}}{\binom nm} =\frac{\binom mc}{\binom nc}, \] giving the decomposition. Orthogonality was proved above. An order-\(c\) canonical U-statistic has variance \(\binom nc^{-1}P^c(\pi_ch)^2\), because covariance between distinct index subsets vanishes; summing yields the formula.
Nondegenerate central limit theorem
The first projection is \[ \phi(x)=\pi_1h(x) =\mathbb E\{h(x,X_2,\ldots,X_m)\}-\theta. \]
H?jek projection theorem. If \(h\in L^2(P^m)\) and \[ \zeta_1=P\phi^2>0, \] then \[ U_nh-\theta =\frac mn\sum_{i=1}^n\phi(X_i) +R_n,\qquad \mathbb E R_n^2=O(n^{-2}), \] and consequently \[ \sqrt n(U_nh-\theta) \rightsquigarrow N(0,m^2\zeta_1). \]
Proof. The \(c=1\) term in the Hoeffding decomposition is \(mP_n\phi\). The exact variance formula shows that the sum over \(c\ge2\) has variance \[ \sum_{c=2}^mO(n^{-c})=O(n^{-2}). \] Thus \(\sqrt nR_n\to_{L^2}0\). The ordinary central limit theorem applies to \(mP_n\phi\), and Slutsky completes the proof.
Degenerate order-two limits
Spectral limit for a canonical kernel. Let \(m=2\), \(Ph(x,X_2)=0\) for \(P\)-almost every \(x\), and \(h\in L^2(P^2)\). Define the Hilbert-Schmidt operator \[ (Kf)(x)=\int h(x,y)f(y)\,P(\mathrm{d}y). \] If \(\{\lambda_j\}\) are its nonzero eigenvalues, then \[ nU_nh \rightsquigarrow \sum_{j=1}^{\infty}\lambda_j(Z_j^2-1), \] where \(Z_j\) are independent \(N(0,1)\), with convergence of the series in \(L^2\).
Proof outline. The spectral theorem gives \[ h(x,y)=\sum_j\lambda_je_j(x)e_j(y) \] in \(L^2(P^2)\), where \(Pe_j=0\) and \(Pe_je_k=\delta_{jk}\). For a finite-rank truncation, \[ nU_nh =\frac{n}{n-1}\sum_j\lambda_j \left[ \left\{\frac1{\sqrt n}\sum_i e_j(X_i)\right\}^2 -\frac1n\sum_i e_j(X_i)^2 \right]. \] The multivariate CLT and law of large numbers give the finite sum of \(\lambda_j(Z_j^2-1)\). Hilbert-Schmidt summability \(\sum_j\lambda_j^2\lt\infty\) controls the truncated tail in \(L^2\).
This non-Gaussian limit is common in kernel independence tests, maximum mean discrepancy under the null, and quadratic goodness-of-fit statistics. Bootstrapping a degenerate statistic requires a scheme that reproduces its degeneracy.
V-statistics and diagonal terms
Definition. The V-statistic generated by \(h\) is \[ V_nh=P_n^mh =\frac1{n^m}\sum_{i_1,\ldots,i_m=1}^n h(X_{i_1},\ldots,X_{i_m}). \] It includes tuples with repeated indices.
Order-two relation. For a symmetric order-two kernel, \[ V_nh =\frac{n-1}{n}U_nh +\frac1{n^2}\sum_{i=1}^nh(X_i,X_i). \] If \(P|h(X,X)|\lt\infty\), then \(V_nh-U_nh=O_p(n^{-1})\).
Proof. Split the double sum into \(i\ne j\) and \(i=j\). The off-diagonal sum is \(n(n-1)U_nh\), while the diagonal sum is \(\sum_ih(X_i,X_i)\). Divide by \(n^2\). The law of large numbers bounds the diagonal average.
For nondegenerate kernels the \(O_p(n^{-1})\) difference is negligible at the \(\sqrt n\) scale. For degenerate kernels, whose natural scale is \(n\), the diagonal contribution can alter the limit and must be retained.
Estimating the asymptotic variance
Estimate the first projection by \[ \hat\phi_i =\binom{n-1}{m-1}^{-1} \sum_{\substack{I\ni i\\|I|=m}}h(X_I)-U_nh. \] Then \[ \hat\sigma^2 =\frac{m^2}{n}\sum_{i=1}^n (\hat\phi_i-\bar{\hat\phi})^2 \] is consistent for \(m^2P\phi^2\) under standard moments. This is the infinitesimal-jackknife form of the U-statistic variance estimator.