- Inégalité de Hoeffding
-
L’inégalité de Hoeffding est une inégalité de concentration concernant les sommes de variables aléatoires indépendantes et bornées. Il existe une version plus générale de cette inégalité, concernant une somme d'accroissements de martingales, accroissements là encore bornés : cette version plus générale est parfois connue sous le nom d'inégalité d'Azuma-Hoeffding.
Inégalité de Hoeffding — Soit une suite
de variables aléatoires réelles indépendantes vérifiant, pour deux suites 
de nombres réels tels que 
On pose
Alors, pour tout
0,\ " border="0">![\begin{align}
\mathbb{P}\left(S_n-\mathbb{E}[S_n]\ge t\right)
&\le\exp\left(-\frac{2\,t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right),
\\
\mathbb{P}\left(S_n-\mathbb{E}[S_n]\le -t\right)
&\le\exp\left(-\frac{2\,t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right),
\\
\mathbb{P}\left(\left|S_n-\mathbb{E}[S_n]\right|\ge t\right)
&\le 2\exp\left(-\frac{2\,t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right).
\end{align}](e/a2ef139e29aaa917fff0a549c5477875.png)
DémonstrationLa démonstration fait usage de la proposition suivante :
Proposition — Soit
une variable aléatoire réelle bornée et centrée (vérifiant ![\scriptstyle\ \mathbb{E}[Y]=0\](b/0fba41ddc9b26949cb29c3700232e645.png)
). Soit 
deux nombres réels tels que 
et tels que 
Alors, pour tout réel 
0,\ " border="0">![\mathbb{E}\left[e^{sY}\right]\le\exp\left(s^2(d-c)^2/8\right).](4/1b42ce8fdcad862ea6cdad76c4fab60e.png)
DémonstrationPar convexité de la fonction
on a, pour 
En passant à l'espérance, puisque
on en déduit que![\mathbb{E}[e^{sY}]\le f(s)=\frac{d}{d-c}\ e^{sc}\ +\ \frac{-c}{d-c}\ e^{sd}.](a/37af7ab4ff44fd3657fd64405a3d2199.png)
On pose
Il suit que
On remarque alors que
De plus
Alors, en vertu de la formule de Taylor-Lagrange,
On pose alors
![\begin{align}
Y_{i}&=X_{i}-\mathbb{E}[X_{i}],
\\
c_{i}&=a_{i}-\mathbb{E}[X_{i}],\quad d_{i}=b_{i}-\mathbb{E}[X_{i}],
\end{align}](4/b84862b3e4de5386af8d5ef13213c00e.png)
et on remarque que
![\begin{align}
\mathbb{P}(c_i\le Y_i\le d_i)&=1,
\\
d_{i}-c_{i}&=b_{i}-a_{i},
\\
S_{n}-\mathbb{E}[S_{n}]&=Y_{1}+Y_{2}+\dots+Y_{n}.
\end{align}](8/738a952c60a901ac27bc6743ee691b7c.png)
Pour tout
0,\ " border="0"> on a donc, en vertu d'un corollaire de l'inégalité de Markov, de l'indépendance des 
et donc des 
et de la proposition précédente :![\begin{align}
\mathbb{P}\left(S_n-\mathbb{E}[S_n]\ge t\right)
&\le\mathbb{E}\left[e^{s(S_n-\mathbb{E}[S_n])}\right]e^{-st}
\\
&=\mathbb{E}\left[e^{s(Y_{1}+Y_{2}+\dots+Y_{n})}\right]e^{-st}
\\
&=e^{-st}\ \prod_{i=1}^n\mathbb{E}\left[e^{sY_{i}}\right]
\\
&\le\exp\left(-st+\frac{s^2\ \sum_{i=1}^n(b_i-a_i)^2}8\right).
\end{align}](1/2d18ff43abd242955c41e9ffe8d7f3b3.png)
L'inégalité est en particulier vraie pour
qui réalise le minimum de la borne de droite, ce qui démontre la première inégalité. La deuxième inégalité se démontre en remplaçant
par ![\scriptstyle\ Y^{\prime}_{i}=\mathbb{E}[X_{i}]-X_{i},\](3/9631c69fb8ca0cb5ca525ad79feb0755.png)
et ![\scriptstyle\ S_{n}-\mathbb{E}[S_{n}]\](8/6e89120865df4aee4350b0a9e06f830e.png)
par ![\scriptstyle\ \mathbb{E}[S_{n}]-S_{n},\](0/e90db028d48dc4705f928d709e623582.png)
dans le calcul précédent, en posant![\begin{align}
c^{\prime}_{i}&=\mathbb{E}[X_{i}]-b_{i},
\\
d^{\prime}_{i}&=\mathbb{E}[X_{i}]-a_{i},
\end{align}](5/585450e7fa03ca649a82961cf95b6708.png)
et en remarquant que
![\begin{align}
\mathbb{P}(c^{\prime}_i\le Y^{\prime}_i\le d^{\prime}_i)&=1,
\\
d^{\prime}_{i}-c^{\prime}_{i}&=b_{i}-a_{i},
\\
\mathbb{E}[S_{n}]-S_{n}&=Y^{\prime}_{1}+Y^{\prime}_{2}+\dots+Y^{\prime}_{n}.
\end{align}](a/b1aa60b69b8eed20306fe2ef8c580628.png)
La troisième inégalité est une conséquence directe des deux premières.
Bornes pour la dispersion de la loi binomiale de paramètres n et p=0,5, obtenues respectivement à l'aide de l'inégalité de Bienaymé-Tchebychev et à l'aide de l'inégalité de Hoeffding.
Cas de la loi binomiale :Supposons que
Alors
suit la loi binomiale de paramètres n et p. Les inégalités de Bienaymé-Tchebychev et Hoeffding donnent respectivement![\begin{align}
\mathbb{P}\left(\left|S_n-\mathbb{E}[S_n]\right|\ge x\sqrt{n}\right)
&\le \frac{p(1-p)}{x^2},
\\
\mathbb{P}\left(\left|S_n-\mathbb{E}[S_n]\right|\ge x\sqrt{n}\right)
&\le 2\exp\left(-2\,x^2\right).
\end{align}](9/e69b83c87f6423dbc9f0e73c804184b5.png)
On voit que dans ce cas (et c'est assez représentatif de la situation générale) l'inégalité de Hoeffding est beaucoup plus précise pour
suffisamment grand.Voir aussi
Pages liées
Bibliographie
- C. McDiarmid, On the method of bounded differences. In Surveys in Combinatorics, London Math. Soc. Lectures Notes 141, Cambridge Univ. Press, Cambridge 1989, 148–188.
- W. Hoeffding, "Probability inequalities for sums of bounded random variables", J. Amer. Statist. Assoc. 58, 13–30, 1963
Portail des probabilités et des statistiques
Wikimedia Foundation. 2010.