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.

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

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

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

${\displaystyle \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 ${\displaystyle a}$ jest ujemna, a ${\displaystyle b}$ jest dodatnia.

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

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

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

${\displaystyle {\begin{aligned}{\mathsf {E}}\left&\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 ${\displaystyle u=s(b-a).}$ Definiujemy funkcję ${\displaystyle \varphi \colon \mathbb {R} \to \mathbb {R} }$ wzorem

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

Definicja ta jest poprawna. Istotnie,

${\displaystyle {\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,

${\displaystyle {\mathsf {E}}\left\leqslant e^{\varphi (u)}.}$

Ze wzoru Taylora, dla każdej liczby rzeczywistej ${\displaystyle u}$ istnieje taka liczba ${\displaystyle v}$ w przedziale ${\displaystyle ,}$ że

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

Wynika stąd, że

${\displaystyle {\begin{aligned}\varphi (0)&=0\\\varphi '(0)&=-\theta +\left.{\frac {\theta e^{u}}{1-\theta +\theta e^{u}}}\right|_{u=0}\\&=0\\\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}}}\\&={\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\left(1-{\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\right)\\&=t(1-t)&&t={\frac {\theta e^{v}}{1-\theta +\theta e^{v}}}\\&\leqslant {\tfrac {1}{4}}&&t>0\end{aligned}}}$

Oznacza to, że

${\displaystyle \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

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

• Pascal Massart: Concentration Inequalities and Model Selection: Ecole d’Eté de Probabilités de Saint-Flour XXXIII – 2003. Springer, 2007-04-26. ISBN 978-3-540-48503-2.