View source for 数据科学基础 (Fall 2024)/Hoeffding's lemma

霍夫丁引理（Hoeffding's lemma）在霍夫丁不等式（[https://en.wikipedia.org/wiki/Hoeffding%27s_inequality Hoeffding's inequality]）的证明中，扮演着关键角色。该引理陈述如下：
{{Theorem|霍夫丁引理|
:若随机变量 <math>Y</math> 满足 <math>\mathbb{E}[Y]=0</math> 且存在实数 <math>a,b\in\mathbb{R}</math> 使得几乎必然地 (a.s.) <math>a\le Y\le b</math>，则对于任意 <math>\lambda\in\mathbb{R}</math>，都有
::<math>\mathbb{E}[\mathrm{e}^{\lambda Y}]\le\mathrm{e}^{{\lambda^2(b-a)^2}/{8}}</math>
}}
简而言之，霍夫丁引理对 '''中心化''' 且 '''值域受限''' 的任意随机变量 <math>Y</math>，给出了其'''矩生成函数''' (MGF) <math>M_Y(\lambda)=\mathbb{E}[\mathrm{e}^{\lambda Y}]</math> 的上界。

霍夫丁引理有若干证明。我们这里给出一个结合了分析与概率法的证明。

首先，为方便起见，我们引入一个记号 <math>\Psi_Y(\lambda)</math> 表示'''对数矩生成函数''' (log-MGF)，即：
: <math>\Psi_Y(\lambda)=\ln M_Y(\lambda)=\ln \mathbb{E}[\mathrm{e}^{\lambda Y}]</math>
则霍夫丁引理等价于证明： 
:<math>\Psi_Y(\lambda)\le \frac{\lambda^2(b-a)^2}{8}</math>

{{Proof|
我们希望对 <math>\Psi_Y(\lambda)</math> 在 <math>\lambda=0</math> 处进行二阶泰勒展开。这需要验证 <math>\Psi_Y(\lambda)</math> 的二阶可导性。
首先容易验证：
:<math>\Psi_Y(0)=\ln \mathbb{E}\left[\mathrm{e}^{0\cdot Y}\right]=0</math>
:<math>\Psi'_Y(0)=\frac{M'_Y(0)}{M_Y(0)}=\frac{\mathbb{E}\left[Y\mathrm{e}^{0\cdot Y}\right]}{\mathbb{E}\left[\mathrm{e}^{0\cdot Y}\right]}=\mathbb{E}[Y]=0</math>
另一方面，对于任意 <math>\xi\in[0,\lambda]</math>，都有：
:<math>\Psi_Y''(\xi)=\left(\frac{M'_Y(\xi)}{M_Y(\xi)}\right)'=\frac{M_Y''(\xi)}{M_Y(\xi)}-\frac{M_Y'(\xi)^2}{M_Y(\xi)^2}=\mathbb{E}\left[\frac{Y^2\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right]
-\mathbb{E}\left[\frac{Y\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right]^2</math>
注意到 <math>M_Y(\xi)=\mathbb{E}[\mathrm{e}^{\xi Y}]</math>。因此，定义新的随机变量 <math>Z</math>，使得其具有如下的累积分布函数（CDF）：
:<math>F_Z(z)=\int_{a}^z\frac{\mathrm{e}^{\xi y}}{M_{Y}(\xi)} \,\mathrm{d}F_Y(y)=\int_{a}^z\frac{\mathrm{e}^{\xi y}}{\mathbb{E}\left[\mathrm{e}^{\xi Y}\right]} \,\mathrm{d}F_Y(y)</math>
由于 <math>\mathbb{E}\left[\mathrm{e}^{\xi Y}\right]=\int_{a}^b\mathrm{e}^{\xi y}\,\mathrm{d}F_{Y}(y)</math>，则该 <math>F_Z</math> 满足 <math>F_Z(b)=\int_{a}^b\frac{\mathrm{e}^{\xi y}}{\mathbb{E}\left[\mathrm{e}^{\xi Y}\right]} \,\mathrm{d}F_Y(y)=1</math>。因此，<math>F_Z</math> 为一良定义的累积分布函数，且仍几乎必然有 <math>a\le Z\le b</math>。

而且，根据对 <math>Z</math> 的定义，易验证：
:<math>\mathbb{E}\left[\frac{Y\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right]=\int_{a}^by\cdot \frac{\mathrm{e}^{\xi y}}{M_Y(\xi)}\,\mathrm{d}F_Y(y)=\mathbb{E}\left[Z\right]</math>
:<math>\mathbb{E}\left[\frac{Y^2\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right]=\int_{a}^by^2\cdot \frac{\mathrm{e}^{\xi y}}{M_Y(\xi)}\,\mathrm{d}F_Y(y)=\mathbb{E}\left[Z^2\right]</math>
因此：
:<math>\Psi_Y''(\xi)=\mathbb{E}\left[\frac{Y^2\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right]
-\mathbb{E}\left[\frac{Y\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right]^2=\mathbb{E}\left[Z^2\right]-\mathbb{E}\left[Z\right]^2=\mathbf{Var}\left[Z\right]</math>
然而，对于几乎必然满足 <math>a\le Z\le b</math> 的任意随机变量，总是有：
:<math>\left|Z-\frac{a+b}{2}\right|\le\frac{b-a}{2}</math>
这意味着
:<math>\mathbf{Var}\left[Z\right]=\mathbf{Var}\left[Z-\frac{a+b}{2}\right]\le \mathbb{E}\left[\left(Z-\frac{a+b}{2}\right)^2\right]\le\frac{(b-a)^2}{4}</math>

至此，我们可以应用泰勒中值定理，存在中值 <math>\xi\in[0,\lambda]</math>，使得
:<math>\Psi_Y(\lambda)=\Psi_Y(0)+\lambda \Psi_Y'(0)+\frac{\lambda^2}{2}\Psi''_Y(\xi)=\frac{\lambda^2}{2}\mathbf{Var}\left[Z\right]\le \frac{\lambda^2(b-a)^2}{8}</math>
}}
在上述证明中出现的积分，都是统一了连续测度与离散测度的抽象积分，即勒贝格-斯蒂尔杰斯积分 ([https://en.wikipedia.org/wiki/Riemann%E2%80%93Stieltjes_integral Riemann–Stieltjes integral])。如若对此记号感到不适，仍可分别针对连续和离散情况的 <math>Y</math> 自然地构造相应的新随机变量 <math>Z</math>，使之总是满足 <math>\mathbb{E}\left[Y\cdot \frac{\mathrm{e}^{\xi Y}}{\mathbb{E}\left[\mathrm{e}^{\xi Y}\right]}\right]=\mathbb{E}\left[Z\right]</math> 与 <math>\mathbb{E}\left[Y^2\cdot \frac{\mathrm{e}^{\xi Y}}{\mathbb{E}\left[\mathrm{e}^{\xi Y}\right]}\right]=\mathbb{E}\left[Z^2\right]</math> 即可。