1. 简介

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

2. 定义

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

$$\begin{array}{c} E(e^{\lambda \boldsymbol{X}}) \leq \exp{(\lambda \eta + \frac{\lambda^2(b-a)^2}{8})} \end{array}$$

证明

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

$$\begin{array}{cc} e^{\lambda x} \leq \frac{b-x}{b-a} e^{\lambda a} + \frac{x-a}{b-a} e^{\lambda b} & (\forall a \leq x \leq b) \end{array}$$

从而可以推出

$$\begin{array}{c} E(e^{\lambda \boldsymbol{X}}) \leq \frac{b-E(\boldsymbol{X})}{b-a} e^{\lambda a} + \frac{E(\boldsymbol{X}-a)}{b-a} e^{\lambda b} \end{array}$$

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

$$\begin{array}{c} \frac{b-E(\boldsymbol{X})}{b-a} e^{\lambda a} + \frac{E(\boldsymbol{X})-a}{b-a} e^{\lambda b} = e^{L(h)} \end{array}$$

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

$$\begin{array}{c} L(0) = L^{'}(0) = 0 \\ \forall h, L^{''}(h) \leq \frac{1}{4} \end{array}$$

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

$$\begin{array}{c} L(h) = L(0) + \frac{L^{'}(0)}{1!}h + \frac{L^{''}(h)}{2!}h^2 \end{array}$$

从而可得

$$\begin{array}{c} L(h) = \frac{1}{2} h^2 L^{''}(h) \leq \frac{1}{8} h^2 = \frac{1}{8} \lambda^2 (b-a)^2 \end{array}$$

最终可证得

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

附录

参考资料：

• Hoeffding's lemma