概率论与数理统计 (Spring 2023)/Hoeffding's lemma

From TCS Wiki
Revision as of 04:42, 25 May 2023 by Etone (talk | contribs)
Jump to navigation Jump to search

霍夫丁引理(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],给出了其矩生成函数 (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 \mathrm{e}^{\xi Y}\right]\cdot \mathbb{E}\left[\mathrm{e}^{\xi Y}\right]^{-1}=\mathbb{E}\left[Z\right] }[/math][math]\displaystyle{ \mathbb{E}\left[Y^2\cdot \mathrm{e}^{\xi Y}\right]\cdot \mathbb{E}\left[\mathrm{e}^{\xi Y}\right]^{-1}=\mathbb{E}\left[Z^2\right] }[/math] 即可。