Inégalités de concentration

Que dit l'inégalité de Markov pour une variable aléatoire positive $X$ ?

L'inégalité de Markov énonce $P(X\geq a)\leq E[X]/a$ pour $X\geq0$ et $a>0$. C'est une majoration, pas une égalité, et elle ne fait intervenir que l'espérance (pas la variance, contrairement à Bienaymé-Tchebychev).

Vrai ou faux : l'inégalité de Bienaymé-Tchebychev nécessite que $X$ admette une variance finie.

Vrai. La démonstration applique Markov à $(X-E[X])^2$, dont l'espérance est précisément $\text{Var}(X)$ ; il faut donc que cette variance soit finie pour que la borne ait un sens.

Soit $X\sim\mathcal{E}(2)$ (exponentielle de paramètre $\lambda=2$, $E[X]=1/2$). Quelle borne de Markov obtient-on pour $P(X\geq5)$ ?

Markov donne $P(X\geq a)\leq E[X]/a = (1/2)/5 = 0{,}1$.

Soit $X$ telle que $E[X]=10$ et $\text{Var}(X)=4$. Quelle borne de Bienaymé-Tchebychev obtient-on pour $P(|X-10|\geq4)$ ?

$P(|X-E[X]|\geq\varepsilon)\leq\sigma^2/\varepsilon^2 = 4/16 = 0{,}25$.

Vrai ou faux : pour toute variable aléatoire $X$ de carré intégrable, $E[X]^2\leq E[X^2]$.

Vrai. C'est l'inégalité de Jensen appliquée à la fonction convexe $\varphi(x)=x^2$, équivalente à $\text{Var}(X)=E[X^2]-E[X]^2\geq0$.

On lance $n=10\,000$ fois une pièce équilibrée. Soit $S_n$ le nombre de faces, $E[S_n]=5000$, $\text{Var}(S_n)=2500$. Quelle borne de Tchebychev obtient-on pour $P(|S_n-5000|\geq100)$ ?

$\text{Var}(S_n)=np(1-p)=10000\times0{,}5\times0{,}5=2500$. La borne donne $2500/100^2=2500/10000=0{,}25$.

Pourquoi l'inégalité de Markov, appliquée directement à $X\sim\mathcal{E}(\lambda)$, donne-t-elle une borne nettement plus grossière que la valeur exacte $P(X\geq a)=e^{-\lambda a}$ ?

L'inégalité de Markov est une borne universelle, valable pour n'importe quelle variable positive ayant la même espérance — elle ne « voit » que ce seul moment. Or la loi exponentielle décroît très vite (exponentiellement), alors que la borne de Markov ne décroît qu'en $1/a$ (polynomialement). L'écart entre $1/(\lambda a)$ et $e^{-\lambda a}$ illustre que les bornes générales (valables pour toute une classe de lois) sont nécessairement moins précises qu'un calcul exact exploitant la forme particulière de la loi.

Soit $X$ de loi uniforme sur $[0,1]$. Calculer la borne de Tchebychev pour $P(|X-1/2|\geq1/4)$ et comparer à la valeur exacte.

Pour $X\sim\mathcal{U}[0,1]$, $\text{Var}(X)=\dfrac{1}{12}$. La borne de Tchebychev donne $P(|X-1/2|\geq1/4)\leq\dfrac{1/12}{(1/4)^2}=\dfrac{1/12}{1/16}=\dfrac{16}{12}=\dfrac{4}{3}>1$ : la borne est triviale (toujours vraie, sans aucune information utile, puisqu'une probabilité est toujours $\leq1$).

La valeur exacte se calcule directement : $P(|X-1/2|\geq1/4)=P(X\leq1/4)+P(X\geq3/4)=\dfrac14+\dfrac14=\dfrac12$.

Cela illustre une limite réelle de Tchebychev : pour des écarts modestes par rapport à l'écart-type, la borne peut être inutile ; elle devient pertinente surtout pour des grandes déviations.

Vrai ou faux : si $\rho(X,Y)$ désigne le coefficient de corrélation de $X$ et $Y$, alors $\rho(X,Y)=\pm1$ si et seulement si $Y$ est une fonction affine de $X$ presque sûrement.

Vrai. C'est le cas d'égalité dans Cauchy-Schwarz appliqué à $X-E[X]$ et $Y-E[Y]$ : l'égalité $|\text{Cov}(X,Y)|=\sigma_X\sigma_Y$ équivaut à la proportionnalité presque sûre de $X-E[X]$ et $Y-E[Y]$, c'est-à-dire $Y=aX+b$ pour des constantes $a,b$.

Soit $X_1,\dots,X_n$ i.i.d. de loi $\mathcal{E}(1)$ et $\overline{X_n}=\frac1n\sum X_i$. À partir de quel $n$ la borne de Tchebychev garantit-elle $P(|\overline{X_n}-1|\geq0{,}1)\leq0{,}05$ ?

$\text{Var}(\overline{X_n})=1/n$. La borne est $\dfrac{1/n}{0{,}01}=\dfrac{100}{n}$. On veut $\dfrac{100}{n}\leq0{,}05$, soit $n\geq100/0{,}05=2000$.

Démontrer l'inégalité de Cauchy-Schwarz probabiliste $|E[XY]|\leq\sqrt{E[X^2]}\sqrt{E[Y^2]}$ en étudiant le polynôme $t\mapsto E[(X+tY)^2]$.

Pour tout réel $t$, $(X+tY)^2\geq0$ presque sûrement, donc en prenant l'espérance (linéarité) :

Si $E[Y^2]=0$ alors $Y=0$ presque sûrement et l'inégalité est triviale ($0\leq0$). Sinon $P$ est un polynôme du second degré en $t$, à coefficient dominant $E[Y^2]>0$, qui est toujours positif ou nul : son discriminant doit être négatif ou nul :

D'où $E[XY]^2\leq E[X^2]\,E[Y^2]$, et en prenant la racine carrée (les deux membres sont positifs) :

Démontrer l'inégalité de Jensen $\varphi(E[X])\leq E[\varphi(X)]$ pour $\varphi$ convexe et dérivable, en utilisant la propriété $\varphi(x)\geq\varphi(m)+\varphi'(m)(x-m)$ (tangente sous le graphe en tout point $m$).

Propriété de convexité utilisée : pour une fonction $\varphi$ convexe et dérivable, le graphe est toujours au-dessus de n'importe quelle tangente : pour tout $m$ et tout $x$,

Application : posons $m=E[X]$ (un réel fixe) et appliquons l'inégalité ci-dessus en $x=X(\omega)$ pour chaque issue $\omega$ — c'est une inégalité presque sûre entre variables aléatoires :

Passage à l'espérance (qui préserve les inégalités, et $\varphi(E[X])$, $\varphi'(E[X])$ sont des constantes) :

D'où $\varphi(E[X])\leq E[\varphi(X)]$. $\square$

Soit $X\geq0$ d'espérance $E[X]=\mu$. Démontrer que pour tout $a>\mu$, $P(X\geq a)\leq\dfrac{\mu}{a}$, puis donner un exemple de loi pour laquelle cette borne est atteinte exactement (égalité).

L'inégalité $P(X\geq a)\leq\mu/a$ est l'inégalité de Markov elle-même (cf. §1), valable pour tout $a>0$ dès que $X\geq0$ et $E[X]=\mu<\infty$.

Cas d'égalité : prenons $X$ qui ne prend que deux valeurs, $0$ et $a$, avec $P(X=a)=p$ et $P(X=0)=1-p$. Alors $E[X]=ap$. Pour avoir $E[X]=\mu$, on choisit $p=\mu/a$ (valeur licite si $\mu\leq a$, donc en particulier pour $a>\mu$ avec $p<1$). Dans ce cas :

Soit $X$ une variable aléatoire bornée, $0\leq X\leq M$, avec $E[X]=\mu$. Montrer que $\text{Var}(X)\leq\mu(M-\mu)$.

Idée clé : comme $0\leq X\leq M$ presque sûrement, on a $(M-X)\cdot X\geq0$ presque sûrement (produit de deux quantités positives), donc $E\big[(M-X)X\big]\geq0$.

En développant :

Or $\text{Var}(X)=E[X^2]-\mu^2$, donc :

C'est une borne classique (parfois appelée inégalité de Popoviciu dans un cas voisin) utile pour majorer la variance de variables bornées sans connaître leur loi exacte — par exemple pour les variables de Bernoulli ($M=1$), elle redonne exactement $\text{Var}(X)=p(1-p)\leq p(1-p)$ (égalité).

Vrai ou faux : si $X_n \to X$ en probabilité et que $(X_n)$ est bornée par une constante $M$ pour tout $n$, alors $E[X_n]\to E[X]$.

Vrai. C'est une conséquence du théorème de convergence dominée (ou de sa version pour la convergence en probabilité) : la convergence en probabilité d'une suite uniformément bornée entraîne la convergence des espérances. Sans l'hypothèse de bornitude (ou domination), ce résultat est faux en général — un contre-exemple classique est une suite de variables prenant la valeur $n$ avec probabilité $1/n$ et $0$ sinon : $X_n\to0$ en probabilité mais $E[X_n]=1$ pour tout $n$, ne convergeant pas vers $E[0]=0$.