Efron–Stein 方差不等式

形式陈述

模拟器或学习算法的输出往往是许多独立输入的非线性函数。其完整分布难算时，可以先问：只重抽第一个输入，输出平均改变多少；再对第二个输入重复这一计算。Efron–Stein 把这些局部的平均平方变化汇成整体方差的上界。

设 $X_1,\ldots,X_n$ 相互独立，不要求同分布， $Z=f(X_1,\ldots,X_n)$ 可测且 $\mathbb EZ^2<\infty$ 。另取与整个 $X$ 独立的副本向量 $X'=(X_1',\ldots,X_n')$ ，其中 $X_i'\overset d=X_i$ ，各副本也独立。定义

Z^{(i)}=f(X_1,\ldots,X_{i-1},X_i',X_{i+1},\ldots,X_n).

只有第 $i$ 个坐标换成独立重抽值，其余输入完全保留。则

\operatorname{Var}(Z)\le \frac12\sum_{i=1}^n\mathbb E(Z-Z^{(i)})^2=:B.\tag{1}

右边是一个确定的总体方差预算，不是一份数据上看到的替换差值。随机量 $Z^{(i)}$ 与 $Z$ 通常不独立，因为二者共享 $n-1$ 个输入。

令 $X_{-i}$ 表示除了第 $i$ 项以外的全部坐标。等价的右侧写法是

B=\sum_i\mathbb E\{\operatorname{Var}(Z\mid X_{-i})\}.\tag{2}

这里的“等价”指式(1)、式(2)两个右端完全相同，不能将上界本身改成 $\operatorname{Var}(Z)=B$ 。对非线性函数，不同坐标可能重复承担同一份交互波动。

直觉

方差衡量平均平方波动。若改变一个输入几乎从不影响输出，那么它对总体波动的责任应当很小，即使某种极罕见替换能够造成一次最大跳跃。独立替换考察平均影响；有界差分考察所有可能输入上的最坏影响。这是两种不同的预算。

第一步：为什么有二分之一

给定 $X_{-i}$ ， $Z$ 与 $Z^{(i)}$ 是由独立同分布的 $X_i,X_i'$ 经同一个函数产生，因而条件独立同分布。展开平方得到

\mathbb E[(Z-Z^{(i)})^2\mid X_{-i}] =2\mathbb E[Z^2\mid X_{-i}]-2\{\mathbb E[Z\mid X_{-i}]\}^2 =2\operatorname{Var}(Z\mid X_{-i}).

再取期望，证明式(1)、式(2)右边相等。不能以它们无条件独立为理由推导这个等式；正确的是给定全部未替换坐标后的条件独立。

第二步：把逐步揭示的波动相加

令 $\mathcal F_i=\sigma(X_1,\ldots,X_i)$ ，并取 Doob 鞅 $M_i=\mathbb E[Z\mid\mathcal F_i]$ ， $M_0=\mathbb EZ$ 、 $M_n=Z$ 。记 $D_i=M_i-M_{i-1}$ 。不同鞅差正交：当 $i<j$ 时， $D_i$ 对 $\mathcal F_{j-1}$ 可测，所以

\mathbb E[D_iD_j] =\mathbb E\{D_i\mathbb E[D_j\mid\mathcal F_{j-1}]\}=0.

因此

\operatorname{Var}(Z)=\sum_i\mathbb ED_i^2.\tag{3}

令 $H_i=\mathbb E[Z\mid X_{-i}]$ 。独立坐标使

\mathbb E[H_i\mid\mathcal F_i]=\mathbb E[Z\mid\mathcal F_{i-1}].\tag{4}

可直接把这一点理解为积分顺序：先在 $H_i$ 中平均掉第 $i$ 项，再平均未来坐标 $X_{i+1},\ldots,X_n$ ，就等于一次平均全部尚未揭示的坐标；由于乘积结构，已观察的 $X_i$ 不会改变这个平均。

故 $D_i=\mathbb E[Z-H_i\mid\mathcal F_i]$ 。条件 Jensen 不等式给

\mathbb ED_i^2\le\mathbb E(Z-H_i)^2 =\mathbb E\{\operatorname{Var}(Z\mid X_{-i})\}.

对 $i$ 求和并用式(3)，就得到式(1)。证明只需要 $Z\in L^2$ 和独立输入，不要求 $f$ 可微，也不要求每个输入有有限方差。

例子与边界

两个稀有故障组成“至少一个故障”

令 $B_1,B_2$ 独立服从 Bernoulli $(p)$ ，取 $p=1/10$ ，输出

Z=\max(B_1,B_2).

$Z=1$ 的概率是 $1-(1-p)^2=19/100$ ，所以真实方差为

\operatorname{Var}(Z)=\frac{19}{100}\frac{81}{100} =\frac{1539}{10000}=0.1539.

替换第一个坐标时，输出改变恰好要求 $B_2=0$ 且 $B_1\ne B_1'$ 。这两件事独立，故

\mathbb E(Z-Z^{(1)})^2=(1-p)\cdot2p(1-p) =2p(1-p)^2=0.162.

第二个坐标给同一个数。因此

B=\tfrac12(0.162+0.162)=0.162.

这是比真实方差略大的有效预算。逐项最坏变化都是1；若只从条件范围宽度推导方差上界，则至多得到 $1/4+1/4=1/2$ 。两份预算相比，Efron–Stein 保留了“另一个部件已经故障时，替换本部件没有影响”的概率结构。

更一般地， $n$ 个独立 Bernoulli $(p)$ 的最大值满足

B=np(1-p)^n,\qquad \operatorname{Var}(Z)=(1-p)^n\{1-(1-p)^n\}.

真实方差不超过预算，等价于 $1-(1-p)^n\le np$ ，也能由“至少一次成功”的并集界理解。这里推的是总体式；把观测到的故障比例未经校准地代入 $p$ ，不会自动得到确定上界。

交互会让同一波动被重复计算

取独立公平符号 $R_1,R_2$ ，令 $Z=R_1R_2$ 。 $Z$ 仍是公平符号，所以方差为1。替换任一坐标，以概率1/2改变乘积符号，改变量的平方为4，因此每项平方替换差的期望为2。式(1)右边为2，而非1。

若改成加性输出 $Z=\sum_i g_i(X_i)$ ，只要各项平方可积，则

\frac12\mathbb E(Z-Z^{(i)})^2=\operatorname{Var}(g_i(X_i)),

独立加法的方差恰好相加，式(1)取等号。等号来自加性结构，不能只因输入独立就认为一般非线性输出也取等号。

少掉独立性，方向甚至可以反过来

令 $X_1=X_2=R$ ，其中 $R$ 为公平符号，取 $f(x_1,x_2)=(x_1+x_2)/2$ 。实际输出 $Z=R$ ，方差为1。若仍独立重抽一个边缘副本 $R'$ ，则

\mathbb E(Z-Z^{(i)})^2=\mathbb E[(R-R')^2/4]=1/2,

错误套公式会得到 $1\le1/2$ 。此时给定另一个坐标已经知道被替换坐标，重抽边缘分布不保留原条件结构，式(4)也失效。

不是一份数据上的方差估计，也不是指数界

Jackknife删除观测并重算不同样本量的统计量，主要在平滑展开条件下估计抽样方差。本页用原分布独立重抽一个坐标，对平方差取总体期望，给有限样本上界。两者都谈“单点变化”，但删除、重抽和期望的责任不同。

即使能模拟很多次独立替换，替换差的平均也只是 $B$ 的估计；要把它作为高置信上界，还须控制这次估计误差。样本上测得很小不能当成逐点或总体保证。

单有 $\operatorname{Var}(Z)\le B$ ，通过Chebyshev只能直接得到 $\Pr(|Z-\mathbb EZ|\ge t)\le B/t^2$ 。取 $n=1,f(X)=X$ 时式(1)是方差恒等式，有限方差的 Pareto 尾仍可存在；因此 Efron–Stein 方差预算本身不能产生指数尾。

推论与应用

把一次非线性输出交给可靠均值方法

假设每次独立运行一个模拟器都产生 $Z=f(X)$ ，并已证明 $B$ 是有效方差上界。若要估计 $\mathbb EZ$ ，可以用 $N$ 次相互独立的完整运行得到 $Z_1,\ldots,Z_N$ ，再把 $v=B$ 交给Catoni或MoM。这里独立单位是一次完整运行，不是一次运行中共享输入的多个替换结果。

在上述两部件例中，若已经知道 $0\le p\le0.1$ 而不知道其具体值，函数 $2p(1-p)^2$ 在该区间递增，故可取 $v=0.162$ 。Catoni 要求统计误差 $\varepsilon=0.05$ 、失败概率 $\delta=0.01$ 时，充分运行数为

N\ge\left\lceil2\log200\left(1+\frac{0.162}{0.05^2}\right)\right\rceil=698.

这个例子的输出本身有界，也可以采用有界均值方法；这里的目的，是展示方差预算如何从内部输入机制传到最终均值证书，而不是声称非线性输出必须用重尾方法。

先识别可用条件，再选择方差预算、固定样本区间或全时间检验；同名的方差并不总是同一个量 — 四种输入责任与各自输出

两道自测

$U,V$ 独立且均匀分布于 $[0,1]$ ， $Z=UV$ 。求真实方差、每项期望平方替换差和 Efron–Stein 上界。
若 $Z=n^{-1}\sum_iX_i$ ，各项独立且方差为 $\sigma_i^2$ ，式(1)给什么？若将其所有副本都错误地取为原观测本身，又会发生什么？

答案：第一题 $\mathbb EZ=1/4$ 、 $\mathbb EZ^2=1/9$ ，故方差 $7/144$ ；每项平方替换差为 $\mathbb E(U-U')^2\mathbb EV^2=(1/6)(1/3)=1/18$ ，上界为 $1/18=8/144$ 。第二题每项替换差为 $2\sigma_i^2/n^2$ ，上界恰为真实方差 $n^{-2}\sum_i\sigma_i^2$ ；若副本等于原值，差全部为零，但它们不再独立，得到的零预算没有效力。

参考资料

Stéphane Boucheron、Olivier Bousquet、Gábor Lugosi、Pascal Massart，Moment inequalities for functions of independent random variables，Annals of Probability 33(2), 2005，514–560；作者稿 §2.1 的独立替换定义、§2.2 Proposition 1 的 $1/2$ 方差界。本文仅使用其二阶结论，自行展开 Doob 鞅与条件平均证明，不把高阶矩或指数版本混入式(1)。
Stéphane Boucheron、Gábor Lugosi、Pascal Massart，Concentration Inequalities: A Nonasymptotic Theory of Independence，Oxford University Press, 2013，Chapter 3 为进一步阅读；本页核验依据为上述可公开读取的论文原文。

形式陈述 ​

第一步：为什么有二分之一 ​

第二步：把逐步揭示的波动相加 ​

两个稀有故障组成“至少一个故障” ​

交互会让同一波动被重复计算 ​

少掉独立性，方向甚至可以反过来 ​

不是一份数据上的方差估计，也不是指数界 ​

把一次非线性输出交给可靠均值方法 ​

两道自测 ​

反向链接