霍夫丁引理

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}$

证明

$\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}$

$\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}$