固定阶 U 统计量的 Hoeffding 分解

形式陈述

令 $m\ge1$ 固定， $n\ge m$ ， $X_1,\ldots,X_n$ IID来自 $P$ 。设 $h$ 为实值可测对称 $m$ 元核且 $Eh(X_1,\ldots,X_m)^2<\infty$ ，目标为 $\theta=Eh$ ，完整U统计量为

U_{n,m}=\binom nm^{-1}\sum_{I\subset[n],\,|I|=m}h(X_I).

核的参数按索引升序排列；由于对称性，次序不影响结果。固定 $m$ 很重要：以下渐近阶的常数依赖 $m$ ，不能未经控制推广到 $m=m_n\to\infty$ 。

对 $0\le s\le m$ ，定义 $g_s(x_1,\ldots,x_s)=E[h(x_1,\ldots,x_s,X_{s+1},\ldots,X_m)]$ ，其中 $g_0=\theta$ 。对每个 $s$ 元输入，令

h_s(x_1,\ldots,x_s) =\sum_{A\subseteq[s]}(-1)^{s-|A|}g_{|A|}(x_A).

$s=0$ 时 $h_0=\theta$ 。条件期望的 $L^2$ 收缩与有限求和保证各 $h_s\in L^2$ 。对称性保证这些版本可以选为对称；等式均按 $P$ 的相应乘积测度几乎处处理解。

容斥为何给出退化且完整的分解

先固定一个 $s\ge1$ ，对最后一个坐标积分。把子集 $A\subseteq[s]$ 成对分为不含 $s$ 的 $B$ 与包含 $s$ 的 $B\cup\{s\}$ 。IID乘积结构使后者积分后变成 $g_{|B|}(x_B)$ ，其符号与前者相反，逐对消去。因此

E[h_s(X_1,\ldots,X_s)\mid X_1,\ldots,X_{s-1}]=0.

同理可对任一坐标积分为零，进而条件于任一真子集时均值也为零；这称为canonical或完全退化的 $s$ 阶核。

再把 $\sum_{A\subseteq[m]}h_{|A|}(x_A)$ 展开。固定一个子集 $B$ 的 $g_{|B|}(x_B)$ ，其系数为

\sum_{A:B\subseteq A\subseteq[m]}(-1)^{|A|-|B|} =(1-1)^{m-|B|}.

只有 $B=[m]$ 留下系数1，所以

h(x_1,\ldots,x_m)=\theta+\sum_{s=1}^m\sum_{|A|=s}h_s(x_A).

将它放进所有 $m$ 子集的平均中，一个固定 $s$ 子集在 $\binom{n-s}{m-s}$ 个大子集中出现。组合恒等式

\frac{\binom{n-s}{m-s}}{\binom nm}=\frac{\binom ms}{\binom ns}

给出精确分解

U_{n,m}-\theta=\sum_{s=1}^m\binom ms U_{n,s}(h_s),\qquad U_{n,s}(h_s)=\binom ns^{-1}\sum_{|A|=s}h_s(X_A).

正交性与精确方差

两个不同索引集合 $A,B$ 上的canonical项 $h_{|A|}(X_A)$ 、 $h_{|B|}(X_B)$ 不相关：在对称差中选一个只属于一方的坐标，给定其余所有坐标，另一方不变，前者按退化性质积分为零。不同阶的集合必不相同，同阶不同集合也如此。它们一般不独立，但零协方差已经足以使用协方差展开计算方差。

记 $\sigma_s^2=Eh_s(X_1,\ldots,X_s)^2$ ，则

\operatorname{Var}(U_{n,m}) =\sum_{s=1}^m\frac{\binom ms^2}{\binom ns}\sigma_s^2,\qquad \operatorname{Var}(h)=\sum_{s=1}^m\binom ms\sigma_s^2.

设第一个非零投影为 $r$ ，即 $\sigma_1^2=\cdots=\sigma_{r-1}^2=0$ 、 $\sigma_r^2>0$ ，称 $r$ 为退化秩。固定核与固定阶下，

n^r\operatorname{Var}(U_{n,m})\longrightarrow \binom mr^2 r!\,\sigma_r^2.

这确定方差尺度，却没有自动确定极限分布。 $r=1$ 时，一阶IID和主导，其余方差为 $O(n^{-2})$ ，故由CLT与Slutsky得到 $\sqrt n(U_{n,m}-\theta)\Rightarrow N(0,m^2\sigma_1^2)$ 。 $r\ge2$ 时需新的极限机制，不能把 $n^{r/2}$ 尺度误读成正态保证。

直觉

单个观测解释的一阶效应、只有成对出现才显现的二阶交互、必须三个一起出现才显现的三阶交互，要依次剥离。直接使用 $g_s-\theta$ 会把低阶效应重复放进高阶，只有容斥才把每一部分净化为“缺任一坐标便平均为零”。

二阶旧页已经完整证明共享一个索引的协方差、一阶投影和二阶余项。本页复用其思想，但新增任意子集的容斥与组合重数，并实际解决三阶退化任务；不是把旧证明中的2机械改成 $m$ 。

例子与边界

同一个三元核同时含三种尺度

令 $X$ 等概率取 $\pm1$ ，取

h(x,y,z)=a(x+y+z)+b(xy+xz+yz)+cxyz.

由于 $EX=0$ 、 $EX^2=1$ ， $\theta=0$ ，各canonical投影为 $h_1(x)=ax$ 、 $h_2(x,y)=bxy$ 、 $h_3(x,y,z)=cxyz$ 。例如 $g_2(x,y)=a(x+y)+bxy$ ，只有减去两个 $g_1$ 才留下真正二阶项。精确方差为

\operatorname{Var}(U_{n,3}) =\frac{9a^2}{n}+\frac{9b^2}{\binom n2}+\frac{c^2}{\binom n3}.

$n=6,(a,b,c)=(1,2,3)$ 时为 $3/2+12/5+9/20=87/20$ 。单核方差为 $3a^2+3b^2+c^2=24$ ；把20个三元核行当IID会算成 $24/20=6/5$ ，明显少算。改变 $a,b,c$ 会改变首个非零投影： $a=0,b\ne0$ 时为二阶尺度， $a=b=0,c\ne0$ 时为三阶尺度。

三阶退化：Hermite多项式而非正态

取 $h(x,y,z)=xyz$ ，仍用Rademacher输入。目标零，前两阶投影都为零， $h_3=h$ ，故

\operatorname{Var}(U_{n,3})=\binom n3^{-1}.

令 $S_n=\sum_iX_i$ 。展开 $S_n^3$ ，三索引互异的项计六次，两索引相同的项合计 $3(n-1)S_n$ ，三者相同的项为 $S_n$ 。因此

U_{n,3}=\frac{S_n^3-(3n-2)S_n}{n(n-1)(n-2)}.

例如 $n=5$ 、样本 $(-1,-1,1,1,1)$ 时， $S_n=1$ ，统计量为 $-12/60=-1/5$ 。枚举全部32个等概率样本，可验证均值0、方差 $1/10$ 。这里10个三元核值两两不相关，却依然不是相互独立。

IID CLT给 $S_n/\sqrt n\Rightarrow Z\sim N(0,1)$ ，上述恒等式与连续映射给

n^{3/2}U_{n,3}\Rightarrow Z^3-3Z.

极限均值0、方差 $15-18+9=6$ ，与 $n^3/\binom n3\to6$ 一致。它虽关于零对称，也不是正态：四阶矩为3348，而方差6的正态四阶矩为108。对称与有限方差都不足以恢复正态误差条。

退化取决于分布，不只是核表达式

一般IID输入均值为 $\mu$ ，核仍是 $xyz$ ，目标为 $\mu^3$ 。写 $A_i=X_i-\mu$ 后，投影为

h_1(x)=\mu^2(x-\mu),\quad h_2(x,y)=\mu(x-\mu)(y-\mu),\quad h_3(x,y,z)=(x-\mu)(y-\mu)(z-\mu).

当 $\operatorname{Var}(X)>0$ ， $\mu\ne0$ 时为秩1； $\mu=0$ 时为秩3。不能因为某份数据的样本均值接近零，就把总体投影宣布为严格退化。参数随 $n$ 趋零时的过渡尺度也不由固定参数CLT统一覆盖。

推论与应用

先找投影秩，再谈昂贵核预算

完整三元核通常需 $\binom n3$ 次求值，但上面的特殊乘积核可由 $S_n$ 的恒等式降为线性时间。遇到昂贵一般核，应先检查代数化简；如果确需只计算部分子集，不完全U统计量会再引入计算抽样误差。

这时退化秩具有实际成本意义：若完整统计量方差为 $n^{-r}$ 阶，而有放回抽 $B$ 个子集引入 $B^{-1}$ 阶误差，要保留原方差阶至少需要 $B$ 达到 $n^r$ 量级。非退化核常见的线性计算预算不能无条件搬到三阶退化核。精确公式与不放回修正见该页。

适用范围检查

这里的 $g_s,h_s$ 是总体分布下的理论投影，通常未知；用数据估计它们需另做一致性与标准误分析。本文给精确分解和尺度，不交付任意阶退化核的通用学生化算法，也不保证所有核都有可计算的闭式投影。

条件独立是正交证明的关键。样本来自时间序列、只交换而不独立，或把若干来自同一外层情境的输出当作独立 $X_i$ ，都可能破坏“积分一个独有坐标便为零”的步骤。多样本U统计量还要分组计算重数，不能直接用 $\binom nm$ 替代；MMD原页保留其两样本结构。

自测：若 $h(x_1,\ldots,x_m)=m^{-1}\sum_jx_j$ ，则 $h_1(x)=(x-EX)/m$ 、其余投影为零，完整U恰为样本均值，方差为 $\operatorname{Var}(X)/n$ 。若 $h=\prod_jX_j$ 且 $EX=0,EX^2=1$ ，只有第 $m$ 阶投影非零，方差为 $1/\binom nm$ ；但极限分布还需单独推导，不能由这个方差公式直接命名。

参考资料

Peter Bartlett，Theoretical Statistics, Lecture 7，2013，slides 2–3一般阶核及方差，slides 10–16 Hájek投影与非退化极限。本文的全部阶数容斥、canonical正交与三阶多项式极限在正文独立展开。
Wassily Hoeffding，A Class of Statistics with Asymptotically Normal Distribution，Annals of Mathematical Statistics 19(3)，1948，293–325，U统计量原始出处；不声称本次已核阅原文全文。
A. W. van der Vaart，Asymptotic Statistics，Cambridge University Press，1998，Chapter 12，进一步的U统计量理论；本页以写出的条件与证明为责任边界。

形式陈述 ​

容斥为何给出退化且完整的分解 ​

正交性与精确方差 ​

同一个三元核同时含三种尺度 ​

三阶退化：Hermite多项式而非正态 ​

退化取决于分布，不只是核表达式 ​

先找投影秩，再谈昂贵核预算 ​

适用范围检查 ​

反向链接