Annexe F — Inégalités de concentration

En probabilités, les inégalités de concentration caractérisent la concentration de la moyenne empirique autour de l’espérance, c’est-à-dire de la véritable moyenne.

F.1 Inégalité de Markov

L’inégalité de Markov relie la probabilité d’observer des valeurs de grande amplitude à la moyenne de l’amplitude : pour toute variable aléatoire Z, \forall t>0,\quad P(|Z|\geq t) \leq \frac{\mathbb{E}|Z|}{t}

Preuve

Pour une variable aléatoire continue Z\in\mathbb{R}, et tout t>0, \begin{align*} \mathbb{E}|Z| & = \int_{\mathbb{R}} |z|\, p_Z(z)\, dz \\ & = \int_{|z|< t} |z|\, p_Z(z)\, dz + \int_{|z|\geq t} |z|\, p_Z(z)\, dz \\ & \geq \int_{|z| \geq t} |z|\, p_Z(z)\, dz & \text{(car la premierère intégrale est positive)} \\ & \geq \int_{|z| \geq t} t\, p_Z(z)\, dz = t \int_{|z| \geq t} p_Z(z)\, dz & \text{(car } |z|\geq t ) \\ & \geq t P(|Z| \geq t ) \end{align*}

F.2 Inégalité de Bienaymé-Chebyshev

L’inégalité de Bienaymé-Chebyshev relie la distance entre une variable aléatoire et son espérance à sa variance : \forall t>0,\quad P(|Z - \mathbb{E}Z | \geq t) \leq \frac{Var ( Z )}{t^2}

Preuve

Pour toute variable aléatoire Z : P(|Z - \mathbb{E}Z | \geq t) = P((Z - \mathbb{E}Z)^2 \geq t^2) L’inégalité de Markov appliquée à la variable Z' = (Z - \mathbb{E}Z)^2 avec la constante t^2 donne P((Z - \mathbb{E}Z)^2 \geq t^2) \leq \frac{\mathbb{E}(Z - \mathbb{E}Z)^2 }{t^2} = \frac{Var ( Z )}{t^2}

F.3 Inégalité de Chebyshev pour les moyennes

Pour n variables Z_i, indépendantes et identiquement distribuées comme Z (des copies indépendantes de Z), P\left\{ \left|\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z \right| \geq t\right\} \leq \frac{Var(Z)}{nt^2}

Preuve

En appliquant l’inégalité de Bienaymé-Chebyshev à la variable \frac{1}{n}\sum_{i=1}^n Z_i, nous avons P\left\{ \left|\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^n Z_i\right]\right| \geq t\right\} \leq \frac{Var (\frac{1}{n}\sum_{i=1}^n Z_i )}{t^2} , où la linéarité de l’espérance conduit à \mathbb{E}\left[\frac{1}{n}\sum_{i=1}^n Z_i\right] = \frac{1}{n}\sum_{i=1}^n \mathbb{E}Z_i = \frac{1}{n}\sum_{i=1}^n \mathbb{E}Z = \mathbb{E}Z car les Z_i sont identiquement distrubées et partagent l’espérance de Z. Puisque les Z_i sont indépendantes, la variance se calcule comme Var\left(\frac{1}{n}\sum_{i=1}^n Z_i\right) =\frac{1}{n^2} \sum_{i=1}^n Var(Z_i) = \frac{1}{n^2}\sum_{i=1}^n Var(Z) = \frac{Var(Z)}{n}, ce qui conclut la preuve.

F.4 Borne de Chernoff

Pour toute variable aléatoire Z, \forall t>0,\ s> 0, \quad P(Z \geq t) \leq \frac{\mathbb{E}e^{sZ} }{e^{st}} Cette borne est au cœur de la méthode de Chernoff qui consiste ensuite à trouver une valeur de s qui minimise le membre de droite.

Preuve

Puisque l’exponentielle est strictement croissante et que s est positif, P(Z \geq t) = P(e^{sZ} \geq e^{st} ) Le reste est une conséquence directe de l’inégalité de Markov appliquée à la variable positive e^{sZ} avec la constante e^{st}.

F.5 Inégalité de Hoeffding

Pour n variables Z_i, indépendantes et identiquement distribuées comme la variable bornée Z\in[a,b] (des copies indépendantes de Z), pour tout \epsilon > 0, P\left\{ \frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z \geq \epsilon \right\} \leq \exp\left(\frac{-2n\epsilon^2}{(b-a)^2}\right), P\left\{\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z \leq - \epsilon \right\} \leq \exp\left(\frac{-2n\epsilon^2}{(b-a)^2}\right), P\left\{\left|\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z\right| \geq \epsilon \right\} \leq 2\exp\left(\frac{-2n\epsilon^2}{(b-a)^2}\right).

Preuve

Etape 1 :

Montrons tout d’abord que, pour une variable bornée Z\in[a,b] et centrée, c’est-à-dire telle que \mathbb{E}Z = 0, \mathbb{E}e^{sZ} \leq e^{s^2(b-a)^2/8}

Pour tout z\in[a,b], écrit comme z = \lambda a + (1-\lambda)b, la convexité de l’exponentielle implique que e^z \leq \lambda e^a + (1-\lambda) e^b. Un raisonnement similaire appliqué à sz \in[sa,sb] avec \lambda=(b-z)/(b-a) conduit à e^{sz} \leq \frac{b-z}{b-a} e^{sa} + \left(1-\frac{b-z}{b-a}\right) e^{sb} = \frac{b-z}{b-a} e^{sa} + \frac{z-a}{b-a} e^{sb} Ainsi, \begin{align*} \mathbb{E}e^{sZ} &\leq \mathbb{E}\left[ \frac{b-Z}{b-a} e^{sa} + \frac{Z-a}{b-a} e^{sb} \right] \\ & \leq \frac{b}{b-a} e^{sa} - \frac{a}{b-a} e^{sb} + \mathbb{E}Z \left( \frac{-1}{b-a} e^{sa} + \frac{1}{b-a} e^{sb} \right) & \text{(par linéarité de l'espérance)}\\ & \leq \frac{b}{b-a} e^{sa} - \frac{a}{b-a} e^{sb} & \text{(car } \mathbb{E}Z = 0) \end{align*} Définissons c=\frac{-a}{b-a}, u=s(b-a) et f(u) = -cu + \log(1-c +ce^u). Alors, a=-c(b-a), b = (1-c)(b-a) et \begin{align*} \mathbb{E}e^{sZ} &\leq (1 - c) e^{sa} + c e^{sb} = (1 - c) e^{-c s (b-a)} + c e^{(1-c)s(b-a)} \\ & \leq (1 - c + c e^{s(b-a)}) e^{-c s (b-a)} = (1 - c + c e^{u}) e^{-c u} \\ & \leq e^{f(u)} \end{align*} Nous avons f(0)=0 et la dérivée \begin{align*} f^\prime(u) &= -c + \frac{ce^u}{1-c+ce^u} = -c + \frac{c}{(1-c)e^{-u} + c} \end{align*} qui vaut aussi zéro en u=0. La dérivée seconde est bornée par f^{\prime\prime}(u) = \frac{c (1-c)e^{-u} }{( (1-c)e^{-u} + c)^2} = \frac{\alpha\beta} {(\alpha+\beta)^2} \leq \frac{1}{4} puisque (\alpha+\beta)^2 - 4\alpha\beta = (\alpha-\beta)^2 \geq 0. Ainsi, le développement de Taylor de f en 0 donne, pour un certain \theta\in[0,u], f(u) = f(0) + u f^\prime(0) + \frac{u^2}{2}f^{\prime\prime}(\theta) \leq \frac{u^2}{8} = \frac{s^2(b-a)^2}{8}

Etape 2 :

Nous pouvons maintenant appliquer la borne de Chernoff à la variable \sum_{i=1}^n \left(Z_i - \mathbb{E}Z\right) : \begin{align*} P\left\{ \sum_{i=1}^n (Z_i - \mathbb{E}Z) \geq t\right\} &\leq e^{-st}\mathbb{E}\left[ e^{s \sum_{i=1}^n (Z_i - \mathbb{E}Z) } \right] = e^{-st}\mathbb{E}\left[ \prod_{i=1}^n e^{s (Z_i - \mathbb{E}Z)} \right] \end{align*} Grâce à l’indépendance des Z_i, l’espérance peut être insérée dans le produit : \begin{align*} P\left\{ \sum_{i=1}^n (Z_i - \mathbb{E}Z) \geq t\right\} &\leq e^{-st} \prod_{i=1}^n \mathbb{E}\left[e^{s (Z_i - \mathbb{E}Z)} \right] \end{align*} Utilisons maintenant le résultat de l’Etape 1 pour les variables ( Z_i - \mathbb{E}Z ), bornées par a_i - \mathbb{E}Z \leq Z_i - \mathbb{E}Z \leq b_i - \mathbb{E}Z et centrées car \mathbb{E}\left[ Z_i - \mathbb{E}Z \right] = \mathbb{E}Z_i - \mathbb{E}[ \mathbb{E}Z ] = \mathbb{E}Z - \mathbb{E}Z = 0 . Cela donne \mathbb{E}\left[e^{s (Z_i - \mathbb{E}Z)} \right] \leq e^{s^2(b_i-a_i)^2/8} La borne de Chernoff devient alors : \begin{align*} P\left\{ \sum_{i=1}^n (Z_i - \mathbb{E}Z) \geq t\right\} &\leq e^{-st} \prod_{i=1}^n e^{s^2(b_i-a_i)^2/8} \\&= \exp\left( -st + \frac{s^2\sum_{i=1}^n (b_i-a_i)^2}{8} \right) \end{align*} Si l’on choisit s= 4t / \sum_{i=1}^n (b_i-a_i)^2, nous obtenons \begin{align*} P\left\{ \sum_{i=1}^n (Z_i - \mathbb{E}Z) \geq t\right\} &\leq \exp\left( \frac{-4t^2}{\sum_{i=1}^n (b_i-a_i)^2} + \frac{16t^2}{8\sum_{i=1}^n (b_i-a_i)^2} \right) \\&= \exp\left( \frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right) \end{align*}

Etape 3 :

La version de l’inégalité de Hoeffding impliquant la moyenne plutôt que la somme (la première des trois présentées ci-dessus) s’obtient ensuite ainsi : \begin{align*} P\left\{ \frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z \geq \frac{t}{n}\right\} &= P\left\{ \frac{1}{n}\sum_{i=1}^n (Z_i - \mathbb{E}Z) \geq \frac{t}{n}\right\} \\ & = P\left\{ \sum_{i=1}^n (Z_i - \mathbb{E}Z) \geq t\right\} \\ & \leq \exp\left( \frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right) \end{align*} en choisissant t=n\epsilon avec a_i=a and b_i=b.

Etape 4 :

La seconde des trois inégalités est obtenue de manière similaire en considérant la variable \sum_{i=1}^n \left(\mathbb{E}Z - Z_i\right) au lieu de \sum_{i=1}^n \left(Z_i - \mathbb{E}Z\right). En utilisant les bornes \mathbb{E}Z - b_i \leq \mathbb{E}Z - Z_i \leq \mathbb{E}Z - a_i cela conduit au même type de résultat : P\left\{ \mathbb{E}Z -\frac{1}{n}\sum_{i=1}^n Z_i \geq \epsilon \right\} \leq \exp\left(\frac{-2n\epsilon^2}{(b-a)^2}\right) à partir duquel nous pouvons déduire : P\left\{ \frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z \leq -\epsilon \right\} = P\left\{ \mathbb{E}Z -\frac{1}{n}\sum_{i=1}^n Z_i \geq \epsilon \right\} \leq \exp\left(\frac{-2n\epsilon^2}{(b-a)^2}\right).

Enfin, la troisième inégalité impliquant la valeur absolue est une conséquence directe des deux précédentes et de la borne de l’union (Équation B.1) : \begin{align*} P\left\{\left|\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z\right| > \epsilon \right\} &= P\left\{ \left\{\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z > \epsilon\right\} \cup \left\{\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z < - \epsilon\right\} \right\} \\ & \leq P\left\{ \frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z > \epsilon\right\} + P\left\{\frac{1}{n}\sum_{i=1}^n Z_i - \mathbb{E}Z < - \epsilon\right\} \\ & \leq 2\exp\left(\frac{-2n\epsilon^2}{(b-a)^2}\right). \end{align*}

F.6 Inégalité des différences bornées

L’inégalité des différences bornées (ou de McDiarmid), borne la probabilité d’observer une grande différence entre une fonction de plusieurs variables et son espérance lorsque l’effet d’une variation d’une seule variable sur la fonction est borné.

Pour une fonction f: \mathcal{Z}^n \rightarrow \mathbb{R} de n variables telle que pour des constantes non négatives c_i\geq 0, i=1,\dots,n, \sup_{(z_1,\dots, z_n) \in \mathcal{Z}^n, z_i^\prime \in \mathcal{Z}} |f(z_1,\dots, z_n) - f(z_1, \dots,z_{i-1}, z_i^\prime, z_{i+1}, \dots, z_n)| \leq c_i,\quad i=1,\dots, n, soit valide et n variables aléatoires Z_i indépendantes (mais pas nécessairement identiquement distribuées), P\left\{ f(Z_1,\dots, Z_n) - \mathbb{E}f(Z_1,\dots, Z_n) \geq \epsilon \right\} \leq \exp\left(\frac{-2\epsilon^2}{\sum_{i=1}^n c_i^2}\right), P\left\{ \mathbb{E}f(Z_1,\dots, Z_n) - f(Z_1,\dots, Z_n) \geq \epsilon \right\} \leq \exp\left(\frac{-2\epsilon^2}{\sum_{i=1}^n c_i^2}\right), et P\left\{ \left|f(Z_1,\dots, Z_n) - \mathbb{E}f(Z_1,\dots, Z_n) \right| \geq \epsilon \right\} \leq 2\exp\left(\frac{-2\epsilon^2}{\sum_{i=1}^n c_i^2}\right).