Lemat Hoeffdinga

Lemat Hoeffdinga – w rachunku prawdopodobieństwa, twierdzenie podające górne ograniczenie funkcji generującej momenty ograniczonej zmiennej losowej o zerowej średniej. Dowód lematu Hoeffdinga wykorzystuje wzór Taylora oraz nierówność Jensena.

Twierdzenie

Niech $X$ będzie rzeczywistą zmienną losową przyjmującą wartości w przedziale $[a,b]$ prawie na pewno. Jeżeli ${\mathsf {E}}X=0,$ to dla wszystkich $\lambda \in \mathbb {R}$ zachodzi nierówność

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

Dowód

Założenie, że $X$ ma zerową wartość oczekiwaną implikuje, że liczba $a$ jest niedodatnia, a liczba $b$ nieujemna. W szczególności, jeżeli jedna z tych liczb jest 0, to $X$ przyjmuje stale wartość 0 prawie na pewno,

$\textstyle {\mathsf {P}}\left(X=0\right)=1,$

a w tym wypadku dowodzona nierówność jest prawdziwa. Bez straty ogólności można więc założyć, że liczba $a$ jest ujemna, a $b$ jest dodatnia.

Funkcja $s\mapsto e^{sx}$ jest wypukła, tj.

$e^{sx}\leqslant {\frac {b-x}{b-a}}e^{sa}+{\frac {x-a}{b-a}}e^{sb}\quad (x\in [a,b]).$

Obliczając wartość oczekiwaną obu stron powyższej nierówności, otrzymujemy

${\begin{aligned}{\mathsf {E}}\left[e^{sX}\right]&\leqslant {\frac {b-{\mathsf {E}}(X)}{b-a}}e^{sa}+{\frac {{\mathsf {E}}(X)-a}{b-a}}e^{sb}\\&={\frac {b}{b-a}}e^{sa}+{\frac {-a}{b-a}}e^{sb}&&{\mathsf {E}}(X)=0\\&=\left(-{\frac {a}{b-a}}\right)e^{sa}\left(-{\frac {b}{a}}+e^{sb-sa}\right)\\&=\left(-{\frac {a}{b-a}}\right)e^{sa}\left(-{\frac {b-a+a}{a}}+e^{s(b-a)}\right)\\&=\left(-{\frac {a}{b-a}}\right)e^{sa}\left(-{\frac {b-a}{a}}-1+e^{s(b-a)}\right)\\&=\left(1-\theta +\theta e^{s(b-a)}\right)e^{-s\theta (b-a)}&&\theta =-{\frac {a}{b-a}}>0\end{aligned}}$

Niech $u=s(b-a).$ Definiujemy funkcję $\varphi \colon \mathbb {R} \to \mathbb {R}$ wzorem

$\varphi (u)=-\theta u+\log \left(1-\theta +\theta e^{u}\right)\quad (u\in \mathbb {R} ).$

Definicja ta jest poprawna. Istotnie,

${\begin{aligned}1-\theta +\theta e^{u}&=\theta \left({\frac {1}{\theta }}-1+e^{u}\right)\\&=\theta \left(-{\frac {b}{a}}+e^{u}\right)\\&>0&&\theta >0,\quad {\frac {b}{a}}<0\end{aligned}}$

W konsekwencji,

${\mathsf {E}}\left[e^{sX}\right]\leqslant e^{\varphi (u)}.$

Ze wzoru Taylora, dla każdej liczby rzeczywistej $u$ istnieje taka liczba $v$ w przedziale $[0,u],$ że

$\varphi (u)=\varphi (0)+u\varphi '(0)+{\tfrac {1}{2}}u^{2}\varphi ''(v).$

Wynika stąd, że

${\begin{aligned}\varphi (0)&=0\\\varphi '(0)&=-\theta +\left.{\frac {\theta e^{u}}{1-\theta +\theta e^{u}}}\right|_{u=0}\\&=0\\[6pt]\varphi ''(v)&={\frac {\theta e^{v}\left(1-\theta +\theta e^{v}\right)-\theta ^{2}e^{2v}}{\left(1-\theta +\theta e^{v}\right)^{2}}}\\[6pt]&={\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\left(1-{\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\right)\\[6pt]&=t(1-t)&&t={\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\\&\leqslant {\tfrac {1}{4}}&&t>0\end{aligned}}$

Oznacza to, że

$\varphi (u)\leqslant 0+u\cdot 0+{\tfrac {1}{2}}u^{2}\cdot {\tfrac {1}{4}}={\tfrac {1}{8}}u^{2}={\tfrac {1}{8}}s^{2}(b-a)^{2}.$

Ostatecznie

${\mathsf {E}}\left[e^{sX}\right]\leqslant \exp \left({\tfrac {1}{8}}s^{2}(b-a)^{2}\right).$

Bibliografia

• Pascal Massart: Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII – 2003. Springer, 26 kwietnia 2007. ISBN 978-3-540-48503-2.brak strony w książce