Лемма Хёффдинга

В вероятностей теории лемма Хеффдинга — это неравенство , которое ограничивает производящую момент функцию любой ограниченной случайной величины . Он назван в честь финско - американского математического статистика Василия Хеффдинга .

Доказательство леммы Хеффдинга использует теорему Тейлора и неравенство Йенсена . Лемма Хёффдинга сама используется при доказательстве неравенства Мак-Диармида .

Утверждение леммы

Пусть X — любая действительная случайная величина такая, что $a\leq X\leq b$ почти наверняка , т.е. с вероятностью единица. Тогда для всех $\lambda \in \mathbb {R}$,

$\mathbb {E} \left[e^{\lambda X}\right]\leq \exp {\Big (}\lambda \mathbb {E} [X]+{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )},$

или эквивалентно,

$\mathbb {E} \left[e^{\lambda (X-\mathbb {E} [X])}\right]\leq \exp {\Big (}{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )}.$

Доказательство

Без ограничения общности, заменив $X$ к $X-\mathbb {E} [X]$, мы можем предположить $\mathbb {E} [X]=0$, так что $a\leq 0\leq b$.

С $e^{\lambda x}$ является выпуклой функцией $x$, у нас это есть для всех $x\in [a,b]$,

$e^{\lambda x}\leq {\frac {b-x}{b-a}}e^{\lambda a}+{\frac {x-a}{b-a}}e^{\lambda b}$

Так,

${\begin{aligned}\mathbb {E} \left[e^{\lambda X}\right]&\leq {\frac {b-\mathbb {E} [X]}{b-a}}e^{\lambda a}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{\lambda b}\\&={\frac {b}{b-a}}e^{\lambda a}+{\frac {-a}{b-a}}e^{\lambda b}\\&=e^{L(\lambda (b-a))},\end{aligned}}$

где $L(h)={\frac {ha}{b-a}}+\ln(1+{\frac {a-e^{h}a}{b-a}})$. Вычислив производные, находим

$L(0)=L'(0)=0$ и $L''(h)=-{\frac {abe^{h}}{(b-ae^{h})^{2}}}$.

Таким образом, из неравенства AMGM мы видим, что $L''(h)\leq {\frac {1}{4}}$ для всех $h$, и, таким образом, по теореме Тейлора существует некоторый $0\leq \theta \leq 1$ такой, что

$L(h)=L(0)+hL'(0)+{\frac {1}{2}}h^{2}L''(h\theta )\leq {\frac {1}{8}}h^{2}.$

Таким образом, $\mathbb {E} \left[e^{\lambda X}\right]\leq e^{{\frac {1}{8}}\lambda ^{2}(b-a)^{2}}$.

См. также

• Неравенство Хефдинга
• Неравенство Беннета