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 {\displaystyle X} będzie rzeczywistą zmienną losową przyjmującą wartości w przedziale [ a , b ] {\displaystyle [a,b]} prawie na pewno. Jeżeli E X = 0 , {\displaystyle {\mathsf {E}}X=0,} to dla wszystkich λ ∈ R {\displaystyle \lambda \in \mathbb {R} } zachodzi nierówność

E [ e λ X ] ⩽ exp ⁡ ( λ 2 ( b − a ) 2 8 ) {\displaystyle {\mathsf {E}}\left[e^{\lambda X}\right]\leqslant \exp \left({\frac {\lambda ^{2}(b-a)^{2}}{8}}\right)} [1].

Dowód

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

P ( X = 0 ) = 1 , {\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 a {\displaystyle a} jest ujemna, a b {\displaystyle b} jest dodatnia.

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

e s x ⩽ b − x b − a e s a + x − a b − a e s b ( x ∈ [ a , b ] ) . {\displaystyle 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

E [ e s X ] ⩽ b − E ( X ) b − a e s a + E ( X ) − a b − a e s b = b b − a e s a + − a b − a e s b E ( X ) = 0 = ( − a b − a ) e s a ( − b a + e s b − s a ) = ( − a b − a ) e s a ( − b − a + a a + e s ( b − a ) ) = ( − a b − a ) e s a ( − b − a a − 1 + e s ( b − a ) ) = ( 1 − θ + θ e s ( b − a ) ) e − s θ ( b − a ) θ = − a b − a > 0 {\displaystyle {\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 ) . {\displaystyle u=s(b-a).} Definiujemy funkcję φ : R → R {\displaystyle \varphi \colon \mathbb {R} \to \mathbb {R} } wzorem

φ ( u ) = − θ u + log ⁡ ( 1 − θ + θ e u ) ( u ∈ R ) . {\displaystyle \varphi (u)=-\theta u+\log \left(1-\theta +\theta e^{u}\right)\quad (u\in \mathbb {R} ).}

Definicja ta jest poprawna. Istotnie,

1 − θ + θ e u = θ ( 1 θ − 1 + e u ) = θ ( − b a + e u ) > 0 θ > 0 , b a < 0 {\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,

E [ e s X ] ⩽ e φ ( u ) . {\displaystyle {\mathsf {E}}\left[e^{sX}\right]\leqslant e^{\varphi (u)}.}

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

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

Wynika stąd, że

φ ( 0 ) = 0 φ ′ ( 0 ) = − θ + θ e u 1 − θ + θ e u | u = 0 = 0 φ ″ ( v ) = θ e v ( 1 − θ + θ e v ) − θ 2 e 2 v ( 1 − θ + θ e v ) 2 = θ e v 1 − θ + θ e v ( 1 − θ e v 1 − θ + θ e v ) = t ( 1 − t ) t = θ e v 1 − θ + θ e v ⩽ 1 4 t > 0 {\displaystyle {\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

φ ( u ) ⩽ 0 + u ⋅ 0 + 1 2 u 2 ⋅ 1 4 = 1 8 u 2 = 1 8 s 2 ( b − a ) 2 . {\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

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

Przypisy

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.