Lema de Hoeffding

Desigualdad en la teoría de la probabilidad

En teoría de la probabilidad , el lema de Hoeffding es una desigualdad que limita la función generadora de momentos de cualquier variable aleatoria acotada , ^[1] lo que implica que dichas variables son subgaussianas . Recibe su nombre del estadístico matemático finlandés - estadounidense Wassily Hoeffding .

La demostración del lema de Hoeffding utiliza el teorema de Taylor y la desigualdad de Jensen . El lema de Hoeffding se utiliza a su vez en la demostración de la desigualdad de Hoeffding , así como en la generalización de la desigualdad de McDiarmid .

Enunciado del lema

Sea X cualquier variable aleatoria de valor real tal que casi con seguridad , es decir con probabilidad uno. Entonces, para todos , ${\displaystyle a\leq X\leq b}$ ${\displaystyle \lambda \in \mathbb {R} }$

${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq \exp {\Big (}\lambda \mathbb {E} [X]+{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )},}$

o equivalentemente,

${\displaystyle \mathbb {E} \left[e^{\lambda (X-\mathbb {E} [X])}\right]\leq \exp {\Big (}{\frac {\lambda ^{2}(b-a)^{2}}{8}}{\Big )}.}$

Prueba

La siguiente prueba es directa pero algo ad hoc. Otra prueba utiliza inclinación exponencial ; ^[2] : También existen pruebas ^{del lema 2.2  con una constante ligeramente peor utilizando simetrización. [3]}

Sin pérdida de generalidad, reemplazando por , podemos suponer , de modo que . ${\displaystyle X}$ ${\displaystyle X-\mathbb {E} [X]}$ ${\displaystyle \mathbb {E} [X]=0}$ ${\displaystyle a\leq 0\leq b}$

Como es una función convexa de , tenemos que para todo , ${\displaystyle e^{\lambda x}}$ ${\displaystyle x}$ ${\displaystyle x\in [a,b]}$

${\displaystyle e^{\lambda x}\leq {\frac {b-x}{b-a}}e^{\lambda a}+{\frac {x-a}{b-a}}e^{\lambda b}}$

Entonces,

${\displaystyle {\begin{aligned}\mathbb {E} \left[e^{\lambda X}\right]&\leq {\frac {b-\mathbb {E} [X]}{b-a}}e^{\lambda a}+{\frac {\mathbb {E} [X]-a}{b-a}}e^{\lambda b}\\&={\frac {b}{b-a}}e^{\lambda a}+{\frac {-a}{b-a}}e^{\lambda b}\\&=e^{L(\lambda (b-a))},\end{aligned}}}$

donde . Calculando las derivadas, encontramos ${\displaystyle L(h)={\frac {ha}{b-a}}+\ln(1+{\frac {a-e^{h}a}{b-a}})}$

${\displaystyle L(0)=L'(0)=0}$y . ${\displaystyle L''(h)=-{\frac {abe^{h}}{(b-ae^{h})^{2}}}}$

De la desigualdad AMGM vemos entonces que para todo , y por lo tanto, del teorema de Taylor , hay alguno tal que ${\displaystyle L''(h)\leq {\frac {1}{4}}}$ ${\displaystyle h}$ ${\displaystyle 0\leq \theta \leq 1}$

${\displaystyle L(h)=L(0)+hL'(0)+{\frac {1}{2}}h^{2}L''(h\theta )\leq {\frac {1}{8}}h^{2}.}$

De este modo, . ${\displaystyle \mathbb {E} \left[e^{\lambda X}\right]\leq e^{{\frac {1}{8}}\lambda ^{2}(b-a)^{2}}}$

Véase también

• Desigualdad de Hoeffding
• La desigualdad de Bennett

Notas

1. Pascal Massart (26 de abril de 2007). Desigualdades de concentración y selección de modelos: Ecole d'Eté de Probabilités de Saint-Flour XXXIII - 2003. Springer. pag. 21.ISBN​ 978-3-540-48503-2.
2. Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal (2013). Desigualdades de concentración: una teoría no asintótica de la independencia . Oxford University Press.
3. Romaní, Marc (1 de mayo de 2021). «Una breve demostración del lema de Hoeffding» . Consultado el 7 de septiembre de 2024 .