概率论与数理统计 (Spring 2023)/Hoeffding's lemma: Difference between revisions
No edit summary |
No edit summary |
||
(9 intermediate revisions by the same user not shown) | |||
Line 19: | Line 19: | ||
:<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>\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>\xi\in[0,\lambda]</math>,都有: | ||
:<math>\Psi_Y''(\xi)=\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] | :<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> | -\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>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>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>\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>Z</math> 的定义,易验证: | ||
Line 31: | Line 31: | ||
:<math>\Psi_Y''(\xi)=\mathbb{E}\left[\frac{Y^2\mathrm{e}^{\xi Y}}{M_Y(\xi)}\right] | :<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> | -\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>\left|Z-\frac{a+b}{2}\right|\le\frac{b-a}{2}</math> | ||
这意味着 | 这意味着 | ||
Line 39: | Line 39: | ||
:<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> | :<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[\frac{ | 在上述证明中出现的积分,都是统一了连续测度与离散测度的抽象积分,即勒贝格-斯蒂尔杰斯积分 ([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> 即可。 |
Latest revision as of 04:43, 25 May 2023
霍夫丁引理(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] 即可。