1. 简介

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

2. 定义

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

E(eλX)≤exp⁡(λη+λ2(b−a)28)\begin{array}{c} E(e^{\lambda \boldsymbol{X}}) \leq \exp{(\lambda \eta + \frac{\lambda^2(b-a)^2}{8})} \end{array}

证明

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

eλx≤b−xb−aeλa+x−ab−aeλb(∀a≤x≤b)\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}

从而可以推出

E(eλX)≤b−E(X)b−aeλa+E(X−a)b−aeλb\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=λ(b−a)h = \lambda (b-a)，p=−ab−ap = \frac{-a}{b-a}，L(h)=−hp+ln⁡(1−p+peh)L(h) = -hp + \ln{(1-p+pe^h)}，由于 E(X)=0E(\boldsymbol{X}) = 0，则有

b−E(X)b−aeλa+E(X)−ab−aeλb=eL(h)\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)L(h) 对 hh 求导，并利用均值不等式可求得

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

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

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

从而可得

L(h)=12h2L′′(h)≤18h2=18λ2(b−a)2\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}

最终可证得

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

附录

参考资料：