数据科学基础 (Fall 2024)/Hoeffding's lemma
霍夫丁引理（Hoeffding's lemma）在霍夫丁不等式（Hoeffding's inequality）的证明中，扮演着关键角色。该引理陈述如下：
霍夫丁引理 - 若随机变量 [math]\displaystyle{ Y }[/math] 满足 [math]\displaystyle{ \mathbb{E}[Y]=0 }[/math] 且存在实数 [math]\displaystyle{ a,b\in\mathbb{R} }[/math] 使得几乎必然地 (a.s.) [math]\displaystyle{ a\le Y\le b }[/math]，则对于任意 [math]\displaystyle{ \lambda\in\mathbb{R} }[/math]，都有
- [math]\displaystyle{ \mathbb{E}[\mathrm{e}^{\lambda Y}]\le\mathrm{e}^{{\lambda^2(b-a)^2}/{8}} }[/math]
- 若随机变量 [math]\displaystyle{ Y }[/math] 满足 [math]\displaystyle{ \mathbb{E}[Y]=0 }[/math] 且存在实数 [math]\displaystyle{ a,b\in\mathbb{R} }[/math] 使得几乎必然地 (a.s.) [math]\displaystyle{ a\le Y\le b }[/math]，则对于任意 [math]\displaystyle{ \lambda\in\mathbb{R} }[/math]，都有
简而言之，霍夫丁引理对 中心化 且 值域受限 的任意随机变量 [math]\displaystyle{ Y }[/math]，给出了其矩生成函数 (MGF) [math]\displaystyle{ M_Y(\lambda)=\mathbb{E}[\mathrm{e}^{\lambda Y}] }[/math] 的上界。
霍夫丁引理有若干证明。我们这里给出一个结合了分析与概率法的证明。
首先，为方便起见，我们引入一个记号 [math]\displaystyle{ \Psi_Y(\lambda) }[/math] 表示对数矩生成函数 (log-MGF)，即：
- [math]\displaystyle{ \Psi_Y(\lambda)=\ln M_Y(\lambda)=\ln \mathbb{E}[\mathrm{e}^{\lambda Y}] }[/math]
则霍夫丁引理等价于证明：
- [math]\displaystyle{ \Psi_Y(\lambda)\le \frac{\lambda^2(b-a)^2}{8} }[/math]
Proof. 我们希望对 [math]\displaystyle{ \Psi_Y(\lambda) }[/math] 在 [math]\displaystyle{ \lambda=0 }[/math] 处进行二阶泰勒展开。这需要验证 [math]\displaystyle{ \Psi_Y(\lambda) }[/math] 的二阶可导性。 首先容易验证：
- [math]\displaystyle{ \Psi_Y(0)=\ln \mathbb{E}\left[\mathrm{e}^{0\cdot Y}\right]=0 }[/math]
- [math]\displaystyle{ \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]\displaystyle{ \xi\in[0,\lambda] }[/math]，都有：
- [math]\displaystyle{ \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]\displaystyle{ M_Y(\xi)=\mathbb{E}[\mathrm{e}^{\xi Y}] }[/math]。因此，定义新的随机变量 [math]\displaystyle{ Z }[/math]，使得其具有如下的累积分布函数（CDF）：
- [math]\displaystyle{ 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]\displaystyle{ \mathbb{E}\left[\mathrm{e}^{\xi Y}\right]=\int_{a}^b\mathrm{e}^{\xi y}\,\mathrm{d}F_{Y}(y) }[/math]，则该 [math]\displaystyle{ F_Z }[/math] 满足 [math]\displaystyle{ 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]\displaystyle{ F_Z }[/math] 为一良定义的累积分布函数，且仍几乎必然有 [math]\displaystyle{ a\le Z\le b }[/math]。
而且，根据对 [math]\displaystyle{ Z }[/math] 的定义，易验证：
- [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ a\le Z\le b }[/math] 的任意随机变量，总是有：
- [math]\displaystyle{ \left|Z-\frac{a+b}{2}\right|\le\frac{b-a}{2} }[/math]
这意味着
- [math]\displaystyle{ \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]\displaystyle{ \xi\in[0,\lambda] }[/math]，使得
- [math]\displaystyle{ \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]
- [math]\displaystyle{ \square }[/math]
在上述证明中出现的积分，都是统一了连续测度与离散测度的抽象积分，即勒贝格-斯蒂尔杰斯积分 (Riemann–Stieltjes integral)。如若对此记号感到不适，仍可分别针对连续和离散情况的 [math]\displaystyle{ Y }[/math] 自然地构造相应的新随机变量 [math]\displaystyle{ Z }[/math]，使之总是满足 [math]\displaystyle{ \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]\displaystyle{ \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] 即可。