Inégalité de concentration

Dans la théorie des probabilités, les inégalités de concentration fournissent des bornes sur la probabilité qu'une variable aléatoire dévie d'une certaine valeur (généralement l'espérance de cette variable aléatoire). Par exemple, la loi des grands nombres établit qu'une moyenne de variables aléatoires i.i.d. est, sous réserve de vérifier certaines conditions, proche de leur espérance commune. Certains résultats récents vont plus loin, en montrant que ce comportement est également vérifié par d'autres fonctions de variables aléatoires indépendantes.

Inégalités basiques

Inégalité de Markov

Cette inégalité indique la probabilité qu'une variable aléatoire à valeurs positives dépasse une certaine valeur, autrement dit elle permet de majorer la queue d'une loi de probabilité. En particulier, la probabilité qu'elle dépasse des valeurs de plus en plus grandes est de plus en plus faible. Si $X$ est une variable aléatoire réelle qu'on suppose presque sûrement positive alors

$\forall \lambda >0,\quad \mathbb {P} (X\geq \lambda )\leq {\frac {1}{\lambda }}\mathbb {E} [X].$

Ce résultat possède un corollaire qui généralise ce résultat à toute fonction $\Phi \colon \mathbb {R} \to \mathbb {R}$ croissante et positive :

$\forall \lambda \in \mathbb {R} ,\mathbb {P} (X\geq \lambda )\leq {\frac {1}{\Phi (\lambda )}}\mathbb {E} [\Phi (X)].$

Inégalité de Bienaymé-Tchebychev

Cette inégalité indique comment une variable dévie de sa moyenne. En particulier, la probabilité qu'une variable aléatoire dévie d'une valeur de plus en plus grande de sa moyenne est de plus en plus faible. On la démontre grâce à l'inégalité de Markov. Soit $X$ une variable aléatoire admettant un moment d'ordre deux alors

$\forall \lambda >0,\quad \mathbb {P} \left(|X-\mathbb {E} [X]|\geq \lambda \right)\leq {\frac {\mathrm {Var} (X)}{\lambda ^{2}}}.$

On peut généraliser cela à une variable aléatoire admettant un moment d'ordre $p$ :

$\forall \lambda >0,\quad \mathbb {P} \left(|X-\mathbb {E} [X]|\geq \lambda \right)\leq {\frac {\mathbb {E} [|X-\mathbb {E} [X]|^{p}]}{\lambda ^{p}}}.$

Inégalité de Chernoff

Cette inégalité permet de majorer la queue d'une loi de probabilité au même titre que l'inégalité de Markov. Elle ressemble à cette dernière mais donne une borne exponentielle.

Soit $X$ une variable aléatoire dont la fonction génératrice $M_{X}(t)=\mathbb {E} [e^{tX}]$ est finie. Alors

$\forall \lambda \geq 0,\quad \mathbb {P} (X\geq \lambda )\leq e^{-I(\lambda )}\quad \mathrm {et} \quad \mathbb {P} (X\leq -\lambda )\leq e^{-I(-\lambda )}$

où $I$ est la transformée de Cramér définie par $I(x)=\left\lbrace {\begin{array}{l}\sup _{t\geq 0}xt-\log(M_{X}(t))\quad {\textrm {si}}\quad x>0\\\sup _{t\leq 0}-xt-\log(M_{X}(t))\quad {\textrm {si}}\quad x\leq 0\end{array}}\right.$

Inégalité de Bennett

Cette inégalité majore la fonction génératrice des cumulants d'une somme de variables aléatoires indépendantes majorées centrées et majore en conséquence d'après l'inégalité de Chernoff la probabilité que cette somme dévie avec une quantité donnée. Soient $X_{1},\dots ,X_{n}$ des variables i.i.d. de variance finie et tels que $X_{i}\leq b$ presque-sûrement pour tout $1\leq i\leq n$ et $b>0$. On pose $S=\textstyle \sum _{i=1}^{n}(X_{i}-\mathbb {E} [X_{i}])$ et $v=\textstyle \sum _{i=1}^{n}\mathbb {E} [X_{i}^{2}]$. Pour tout $\lambda >0$,

$\log(\mathbb {E} e^{\lambda S})\leq n\log \left(1+{\frac {v}{nb^{2}}}\phi (b\lambda )\right)\leq {\frac {v}{b^{2}}}\phi (b\lambda ).$

où $\phi (u)=e^{u}-u-1$ pour $u\in \mathbb {R}$. En appliquant l'inégalité de Chernoff on obtient en particulier que pour tout $t>0$,

$\mathbb {P} (S\geq t)\leq \exp \left(-{\frac {v}{b^{2}}}h\left({\frac {bt}{v}}\right)\right).$

où $h(u)=(1+u)\log(1+u)-u$ pour $u>0$.

Inégalités de la variance

Inégalité d'Efron-Stein

Cette inégalité borne la variance d'une fonction générale d'une variable aléatoire. Soient $X_{1},\dots ,X_{n},X_{1}',\dots ,X_{n}'$ des variables indépendantes (pas nécessairement identiquement distribuées) et tels que $X_{i}\sim X_{i}'$ pour tout $1\leq i\leq n$. En posant $X=(X_{1},\dots ,X_{n})$ et $X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})$ alors

$\mathrm {Var} (f(X))\leq {\frac {1}{2}}\sum _{i=1}^{n}\mathbb {E} [(f(X)-f(X^{(i)}))^{2}].$

Inégalités du processus empirique

Inégalité DKW

Cette inégalité borne la probabilité que la fonction de répartition empirique diffère uniformément de la fonction de répartition de la variable aléatoire étudiée.

Soient $X_{1},\dots ,X_{n}$ des variables i.i.d. de fonction de répartition $F$. On note $F_{n}$ la fonction de répartition empirique basée sur l'échantillon $X_{1},\dots ,X_{n}$, c'est-à-dire

$\forall t\in \mathbb {R} ,\qquad F_{n}(t)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq t\}}.$

Alors l'inégalité d'un côté est donnée par :

$\mathbb {P} \left(\sup _{t\in \mathbb {R} }(F_{n}(t)-F(t))>\varepsilon \right)\leq e^{-2n\varepsilon ^{2}},\qquad \forall \varepsilon \geq {\sqrt {{\frac {1}{2n}}\ln 2}}$

Cette inégalité a pour conséquence l'inégalité des deux côtés suivante (qui n'a pas de conditions sur $\varepsilon$) :

$\mathbb {P} \left(\sup _{t\in \mathbb {R} }|F_{n}(t)-F(t)|>\varepsilon \right)\leq 2e^{-2n\varepsilon ^{2}},\qquad \forall \varepsilon >0$

Inégalité de Borell

Cette inégalité donne une borne exponentielle pour la concentration d'un processus stochastique gaussien. Soit $X$ un processus gaussien stochastique séparable indexé par un espace semi-métrique $(T,d)$. On note $||X||$ le supremum $\sup _{t\in T}|X_{t}|$ et on suppose que le processus est centré, i.e. $\mathbb {E} [X_{t}]=0$ pour tout $t\in T$. On note $\sigma ^{2}(X)=\sup _{t\in T}\mathrm {Var} (X_{t})$ le supremum de la variance du processus et $M(X)$ la médiane de la variable $X$. Pour tout $t>0$,

${\begin{aligned}P(|\ ||X||-M(X)|\geq t)&\leq \exp \left(-{\frac {t^{2}}{2\sigma ^{2}(X)}}\right)\\P(|\ ||X||-\mathbb {E} [X]|\geq t)&\leq 2\exp \left(-{\frac {t^{2}}{2\sigma ^{2}(X)}}\right)\\P(||X||\geq t)&\leq 2\exp \left(-{\frac {t^{2}}{8\mathbb {E} [||X||^{2}]}}\right)\end{aligned}}$

Inégalité de Bousquet

L'inégalité de Bousquet donne la concentration du processus empirique indexé par des classes de fonctions bornées. Soient $X_{1,s},\dots ,X_{n,s}$ des variables aléatoires réelles i.i.d. indexés par $s\in T$. On suppose que les variables sont centrées et majorées par 1, i.e. $\mathbb {E} [X_{i,s}]=0$ et $|X_{i,s}|\leq 1$ pour tout $i=1,\dots ,n$ et $s\in T$. On note $Z=\textstyle \sup _{s\in T}\sum _{i=1}^{n}X_{i,s}$. Alors pour tout $\lambda ,t\geq 0$,

${\begin{aligned}\log \mathbb {E} e^{\lambda (Z-\mathbb {E} Z)}&\leq v\phi (\lambda )\\\mathbb {P} (Z\geq \mathbb {E} Z+t)&\leq e^{-vh(t/v)}\end{aligned}}$

où $\phi (u)=e^{u}-u-1,h(u)=(1+u)\log(1+u)-u$ pour $u\geq -1$, $v=2\mathbb {E} Z+\sigma ^{2}$ avec $\sigma ^{2}=\textstyle \sup _{s\in T}\sum _{i=1}^{n}\mathbb {E} X_{i,s}^{2}$. En optimisant la fonction $h$, on obtient en particulier

$\mathbb {P} (Z\geq \mathbb {E} Z+t)\leq \exp \left(-{\frac {t^{2}}{2(v+t/3)}}\right)$

Inégalité de Talagrand

Cette inégalité donne également une borne exponentielle pour la concentration du processus empirique indexé par des classes de fonctions. Soient $X_{1},\dots ,X_{n}$ des variables i.i.d. à valeurs dans un espace ${\mathcal {X}}$, une fonction $f:{\mathcal {X}}\to \mathbb {R}$ une fonction mesurable, et le processus empirique $\alpha _{n}(f)={\frac {1}{\sqrt {n}}}\sum _{i=1}^{n}(f(X_{i})-\mathbb {E} [f(X_{i})])$. Si ${\mathcal {F}}$ est une classe de fonctions mesurables définies sur ${\mathcal {X}}$ à valeurs réelles vérifiant certaines conditions d'entropie métrique alors pour tout $t>0$,

$\mathbb {P} (||\alpha _{n}||_{\mathcal {F}}>t)\leq C(\nu )t^{\nu }\exp(-2t^{2}),$

où $\nu \geq 1,C(\nu )>0$ et $||\alpha _{n}||_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}|\alpha _{n}(f)|$.