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 edytuj

Niech   będzie rzeczywistą zmienną losową przyjmującą wartości w przedziale   prawie na pewno. Jeżeli   to dla wszystkich   zachodzi nierówność

 [1].

Dowód edytuj

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

 

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

Funkcja   jest wypukła, tj.

 

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

 

Niech   Definiujemy funkcję   wzorem

 

Definicja ta jest poprawna. Istotnie,

 

W konsekwencji,

 

Ze wzoru Taylora, dla każdej liczby rzeczywistej   istnieje taka liczba   w przedziale   że

 

Wynika stąd, że

 

Oznacza to, że

 

Ostatecznie

 

Przypisy edytuj

Bibliografia edytuj