Inégalité de Hoeffding
L'inégalité de Hoeffding est une version renforcée de l'inégalité de Tchebychev pour les suites de variables aléatoires de Bernoulli.
Théorème : Soit $(X_n)$ une suite de variables aléatoires de Bernoulli indépendantes
et d'espérance $p$. Alors, pour tout $\varepsilon>0$, notant $S_n=X_1+\dots+X_n$, on a
$$P\left(\frac{S_n}n-p\geq\varepsilon\right)\leq \exp(-2n\varepsilon^2).$$
Cette inégalité est beaucoup plus forte, pour les grandes valeurs de $n$, que l'inégalité de Tchebychev, car la décroissance est exponentielle au lieu d'être polynomiale. Elle peut être généralisée à des variables aléatoires pour lesquelles on contrôle bien l'ensemble des valeurs prises.
Théorème : Soit $(X_n)$ une suite de variables aléatoires indépendantes.
Soient $(a_n)$ et $(b_n)$ deux suites de nombres réels telles que, pour tout entier $n$, on a
$P(a_n\leq X_n\leq b_n)=1$. Alors, notant $S_n=X_1+\dots+X_n$, pour tout $t>0$ et tout $n\in\mathbb N$, on a
$$P\big(\big|S_n-E(S_n)\big|\geq t\big)\leq 2\exp\left(-\frac{2t^2}{\sum_{k=1}^n (b_k-a_k)^2}\right).$$
Consulter aussi
Recherche alphabétique
Recherche thématique