霍夫丁不等式引理证明

假设X是一个随机变量,取值于[a,b]区间,且E(X)=0,那么对于任意λ> 0 ,我们有:

[E(e^{lambda x}) leqslant e^{frac{lambda^2(b-a)^2}{8}} ]


对于凸函数 f(x) 有:

[f(x) leqslant f(a) + frac{f(b)-f(a)}{b-a}(x-a) ]

(f(x)=e^{lambda x})带入有:

[e^{lambda x} leqslant e^{lambda a} + frac{e^{lambda b}-e^{lambda a}}{b-a}(x-a)\ =frac{b-x}{b-a}e^{lambda a}+ frac{x-a}{b-a}e^{lambda b},forall x in [a,b]]

将x看作取值于[a,b]的随机变量X,取期望,EX=0,有:

[E(e^{lambda X}) leqslant frac{b-EX}{b-a}e^{lambda a} + frac{EX-a}{b-a}e^{lambda b} \ = frac{b}{b-a}e^{lambda a} - frac{a}{b-a}e^{lambda b} \ = frac{-a}{b-a}e^{lambda a}(-frac{b}{a}+e^{lambda (b-a)})]

(q=-frac{a}{b-a},h=lambda(b-a)),右侧

[=qcdot e^{-qh}(frac{1}{q}-1+e^h)\ =e^{-qh}(1-q+qe^h)\ =e^{-qh+ln(1-q+qe^h)}]

(L(h)=-qh+ln(1-q+qe^h))

原命题等价于:

[E(e^{lambda X}) leqslant e^{L(h)} ]

对于L(h)

[{L}'(h)=-q+frac{qe^h}{1-q+qe^h} ]

[{L}''(h)=frac{qe^h(1-q+qe^h)-(qe^h)^2}{(1-q+qe^h)^2} ]

在0处进行泰勒展开:

[L(h)=frac{L(0)}{0!}h^0+frac{{L}'(0)}{1!}h^1+frac{{L}''(0)}{2!}h^2+o(h^2) ]

[L(0)=0\ {L}'(0)=(-q+frac{qe^h}{1-q+qe^h})|_{h=0}=0\ {L}''(0)=frac{qe^h(1-q+qe^h)-(qe^h)^2}{(1-q+qe^h)^2}|_{h=0}=q(1-q)leqslant frac{1}{4}]

带入可得:

[L(h)=frac{{L}''(0)}{2!}h^2 leqslant frac{lambda^2(b-a)^2}{8} ]

[E(e^{lambda X}) leqslant e^{frac{lambda^2(b-a)^2}{8}} ]

原文地址:https://www.cnblogs.com/vmkash/p/13852391.html