霍夫丁引理

1. 简介

在概率论中，霍夫丁引理是一个不等式，它限制了任何有界随机变量的矩生成函数。

2. 定义

设 X是具有期望值 E(\boldsymbol{X}) = \eta的任一实值随机变量，使得 a \leq \boldsymbol{X} \leq b依概率 1 成立，则对任意 \lambda \in \boldsymbol{R}，有如下不等式成立：

证明 不妨假设\eta = 0（否则可以重新定义 \tilde{\boldsymbol{X}} \triangleq \boldsymbol{X} - \eta，则 \tilde{\boldsymbol{X}} 的期望值 \tilde{\eta} = 0，然后对 \tilde{\boldsymbol{X}} 进行如下证明，最后再反推回 \boldsymbol{X}）。 由于 e^{\lambda x}是关于 x 的下凸函数，因此有

从而可以推出

令h = \lambda (b-a)，p = \frac{-a}{b-a}​，L(h) = -hp + \ln{(1-p+pe^h)}，由于 E(\boldsymbol{X}) = 0，则有

将 L(h)对 h 求导，并利用均值不等式可求得

由泰勒展开公式，L(h) 可写成

从而可得

最终可证得 \begin{array}{c} E(e^{\lambda \boldsymbol{X}}) \leq \exp{(\frac{1}{8} \lambda^2 (b-a)^2)} \end{array}

附录

参考资料：

• Hoeffding’s lemma