Inégalité de Hoeffding

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Énoncé[modifier | modifier le code]

Inégalité de Hoeffding — Soit une suite  \ (X_k)_{1\le k\le n}\ de variables aléatoires réelles indépendantes vérifiant, pour deux suites  \ (a_k)_{1\le k\le n},\  \ (b_k)_{1\le k\le n}\ de nombres réels tels que  \ a_k<b_k,\

\forall k,\qquad \mathbb{P}(a_k\le X_k\le b_k)=1.

On pose

S_n=X_1+X_2+\dots+X_n.

Alors, pour tout  \ t>0,\

\begin{array}{rl}
\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{array}
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[modifier | modifier le code]

Supposons que

 \mathbb{P}(X_k=1)=1-\mathbb{P}(X_k=0)=p.

Alors  \ S_n\ suit la loi binomiale de paramètres n et p. L'inégalité de Bienaymé-Tchebychev et l'inégalité Hoeffding donnent respectivement

\begin{array}{rl}
\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{array}

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  \ x\ suffisamment grand.

Démonstration[modifier | modifier le code]

Inégalité préliminaire[modifier | modifier le code]

La démonstration fait usage de la proposition suivante :

Proposition —  Soit  \ Y\ une variable aléatoire réelle bornée et centrée (vérifiant  \ \mathbb{E}[Y]=0\ ). Soit  \ c,\, d \ deux nombres réels tels que  \ c<d\ et tels que  \ \mathbb{P}(c\le Y\le d)=1.\ Alors, pour tout réel  \ s>0,\

\mathbb{E}\left[e^{sY}\right]\le\exp\left(s^2(d-c)^2/8\right).

Par convexité de la fonction  \ x\rightarrow e^{sx},\ on a, pour  \ c\le Y(\omega)\le d,\

 e^{sY(\omega)}\le \frac{d-Y(\omega)}{d-c}\ e^{sc}\ +\ \frac{Y(\omega)-c}{d-c}\ e^{sd}.

En passant à l'espérance, puisque  \ \mathbb{P}(c\le Y\le d)=1,\ on en déduit que

 \mathbb{E}[e^{sY}]\le f(s)=\frac{d}{d-c}\ e^{sc}\ +\ \frac{-c}{d-c}\ e^{sd}.

On pose

\begin{array}{rl}
(d-c)s&=u
\\
\ln(f(s))&=\psi(u),
\\
\frac{-c}{d-c}&=p,\quad 1-p=\frac{d}{d-c}.
\end{array}

Il suit que


\psi(u)\,=\,-pu+\ln\left(1-p+pe^{u}\right).

On remarque alors que  \ \psi(0)=\psi^{\prime}(0)=0.\ De plus

 \psi^{\prime\prime}(u)=\frac{\left(1-p\right)pe^{u}}{\left(1-p+pe^{u}\right)^2}=\frac{\alpha\beta}{(\alpha+\beta)^2}\le\frac14.

Alors, en vertu de la formule de Taylor-Lagrange,

 \psi(u)=\psi(0)+\psi^{\prime}(0)u+\psi^{\prime\prime}(\theta u)\frac{u^2}2\le\frac{u^2}8.

Démonstration de l'inégalité de Hoeffding[modifier | modifier le code]

On applique ensuite l'inégalité de Markov. Pour cela, on pose:

\begin{array}{rl}
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{array}

et on remarque que

\begin{array}{rl}
\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{array}

Pour tout  \ s>0,\ on a donc, en vertu d'un corollaire de l'inégalité de Markov, de l'indépendance des  \ X_{i},\ et donc des  \ Y_{i},\ et de la proposition précédente :

\begin{array}{rl}
\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{array}

L'inégalité est en particulier vraie pour


s_{0}
=
\frac{4t}{\sum_{i=1}^n(b_i-a_i)^2},

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  \ Y_{i}\ par  \ Y^{\prime}_{i}=\mathbb{E}[X_{i}]-X_{i},\ et  \ S_{n}-\mathbb{E}[S_{n}]\ par  \ \mathbb{E}[S_{n}]-S_{n},\ dans le calcul précédent, en posant

\begin{array}{rl}
c^{\prime}_{i}&=\mathbb{E}[X_{i}]-b_{i},
\\
d^{\prime}_{i}&=\mathbb{E}[X_{i}]-a_{i},
\end{array}

et en remarquant que

\begin{array}{rl}
\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{array}

La troisième inégalité est une conséquence directe des deux premières.

Voir aussi[modifier | modifier le code]

Pages liées[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • 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