1. 简介

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

2. 定义

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

E(eλX)exp(λη+λ2(ba)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λxbxbaeλa+xabaeλb(axb)\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)bE(X)baeλa+E(Xa)baeλ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=λ(ba)h = \lambda (b-a)p=abap = \frac{-a}{b-a}L(h)=hp+ln(1p+peh)L(h) = -hp + \ln{(1-p+pe^h)},由于 E(X)=0E(\boldsymbol{X}) = 0,则有

bE(X)baeλa+E(X)abaeλ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)=0h,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(ba)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(ba)2)\begin{array}{c} E(e^{\lambda \boldsymbol{X}}) \leq \exp{(\frac{1}{8} \lambda^2 (b-a)^2)} \end{array}

附录

参考资料: