Inégalité de concentration

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 ${\displaystyle X}$ est une variable aléatoire réelle qu'on suppose presque sûrement positive alors

${\displaystyle \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 ${\displaystyle \Phi \colon \mathbb {R} \to \mathbb {R} }$ croissante et positive :

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

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 ${\displaystyle X}$ une variable aléatoire admettant un moment d'ordre deux alors

${\displaystyle \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 ${\displaystyle p}$ :

${\displaystyle \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}}}.}$

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 ${\displaystyle X}$ une variable aléatoire dont la fonction génératrice ${\displaystyle M_{X}(t)=\mathbb {E} [e^{tX}]}$ est finie. Alors

${\displaystyle \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ù ${\displaystyle I}$ est la transformée de Cramér définie par ${\displaystyle 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.}$

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 ${\displaystyle X_{1},\dots ,X_{n}}$ des variables i.i.d. de variance finie et tels que ${\displaystyle X_{i}\leq b}$ presque-sûrement pour tout ${\displaystyle 1\leq i\leq n}$ et ${\displaystyle b>0}$. On pose ${\displaystyle S=\textstyle \sum _{i=1}^{n}(X_{i}-\mathbb {E} [X_{i}])}$ et ${\displaystyle v=\textstyle \sum _{i=1}^{n}\mathbb {E} [X_{i}^{2}]}$. Pour tout ${\displaystyle \lambda >0}$,

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

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

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

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

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

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

${\displaystyle \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 :

${\displaystyle \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 ${\displaystyle \varepsilon }$) :

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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