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 $𝖤X=0,$ to dla wszystkich $\lambda \in ℝ$ zachodzi nierówność

$𝖤\left[e^{\lambda X}\right]⩽\exp \left(\frac{{\lambda }^2(b-a{)}^2}{8}\right)$Szablon:Odn.

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,

$𝖯(X=0)=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}⩽\frac{b-x}{b-a}{e}^{sa}+\frac{x-a}{b-a}{e}^{sb}(x\in [a,b]).$

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

$\begin{array}{cc}𝖤\left[e^{sX}\right]& ⩽\frac{b-𝖤(X)}{b-a}{e}^{sa}+\frac{𝖤(X)-a}{b-a}{e}^{sb}\\ & =\frac{b}{b-a}{e}^{sa}+\frac{-a}{b-a}{e}^{sb}& & 𝖤(X)=0\\ & =(-\frac{a}{b-a})e^{sa}(-\frac{b}{a}+e^{sb-sa})\\ & =(-\frac{a}{b-a})e^{sa}(-\frac{b-a+a}{a}+e^{s(b-a)})\\ & =(-\frac{a}{b-a})e^{sa}(-\frac{b-a}{a}-1+e^{s(b-a)})\\ & =(1-\theta +\theta e^{s(b-a)})e^{-s\theta (b-a)}& & \theta =-\frac{a}{b-a}>0\end{array}$

Niech $u=s(b-a).$ Definiujemy funkcję $\phi :ℝ\to ℝ$ wzorem

$\phi (u)=-\theta u+\log (1-\theta +\theta e^u)(u\in ℝ).$

Definicja ta jest poprawna. Istotnie,

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

W konsekwencji,

$𝖤\left[e^{sX}\right]⩽e^{\phi (u)}.$

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

$\phi (u)=\phi (0)+u{\phi }^{\prime }(0)+\frac{1}{2}{u}^2{\phi }^{″}(v).$

Wynika stąd, że

$\begin{array}{cc}\phi (0)& =0\\ {\phi }^{\prime }(0)& =-\theta +{\frac{\theta e^u}{1-\theta +\theta e^u}|}_{u=0}\\ & =0\\ {\phi }^{″}(v)& =\frac{\theta e^v(1-\theta +\theta e^v)-{\theta }^2{e}^{2v}}{{(1-\theta +\theta e^v)}^2}\\ & =\frac{\theta e^v}{1-\theta +\theta e^v}(1-\frac{\theta e^v}{1-\theta +\theta e^v})\\ & =t(1-t)& & t=\frac{\theta e^v}{1-\theta +\theta e^v}\\ & ⩽\frac{1}{4}& & t>0\end{array}$

Oznacza to, że

$\phi (u)⩽0+u\cdot 0+\frac{1}{2}{u}^2\cdot \frac{1}{4}=\frac{1}{8}{u}^2=\frac{1}{8}{s}^2(b-a{)}^2.$

Ostatecznie

$𝖤\left[e^{sX}\right]⩽\exp (\frac{1}{8}{s}^2(b-a{)}^2).$

Bibliografia

• Szablon:Cytuj książkę