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 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
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
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 numerów stron w książce