Inégalité d'Efron-Stein

En théorie des probabilités, l'inégalité d'Efron-Stein permet de borner la variance d'une fonction générale de variables aléatoires indépendantes. Cette inégalité peut être couplée avec d'autres inégalités de concentration classiques, comme l'inégalité de Bienaymé-Tchebychev.

Énoncé

Soient $X_1,\dots ,X_n$ des variables aléatoires indépendantes à valeurs dans un espace $𝒳,Z=f(X_1,\dots ,X_n)$ une fonction générale des $X_1,\dots ,X_n$ avec $f:{𝒳}^n\to ℝ$ alors

$\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \sum _{i=1}^n𝔼[(Z-{𝔼}^{(i)}[Z]{)}^2]$

où ${𝔼}^{(i)}$ désigne l'espérance conditionnelle conditionnée par rapport à $X^{(i)}=(X_1,\dots ,X_{i-1},X_{i+1},\dots X_n)$, c'est-à-dire

${𝔼}^{(i)}Z=\underset{𝒳}{\int }f(X_1,\dots ,X_{i-1},x,X_{i+1},\dots ,X_n)\mathrm{d}{\mu }_i(x)$ où ${\mu }_i$ est la densité de $X_i$.

Si on pose ${X_1}^{\prime },\dots ,{X_n}^{\prime }$ des copies indépendantes des $X_1,\dots ,X_n$ et que l'on pose

${Z_i}^{\prime }=f(X_1,\dots ,X_{i-1},{X_i}^{\prime },X_{i+1},\dots ,X_n)$,

alors le membre de droite de cette inégalité peut également s'écrire :

$\sum _{i=1}^n𝔼[(Z-{𝔼}^{(i)}[Z]{)}^2]=\frac{1}{2}\sum _{i=1}^n𝔼[(Z-{Z_i}^{\prime }{)}^2]=\sum _{i=1}^n𝔼[(Z-{Z_i}^{\prime }{)}_{+}^2]=\sum _{i=1}^n𝔼[(Z-{Z_i}^{\prime }{)}_{-}^2]$ où $x_{+}=\max (x,0)$ et $x_{-}=\max (-x,0)$.

On peut également écrire que $\sum _{i=1}^n𝔼[(Z-{𝔼}^{(i)}[Z]{)}^2]=\underset{Z_i}{\inf }\sum _{i=1}^n𝔼[(Z-Z_i{)}^2]$ où l'infimum est pris sur l'ensemble des $X^{(i)}$-mesurable et les variables $Z_i$ admettant un moment d'ordre deux.

Démonstration

L'idée de la preuve est de généraliser le cas où quand $Z=X_1+\dots +X_n$, on a $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\sum _{i=1}^n\mathrm{V}\mathrm{a}\mathrm{r}(X_i).$

Si on note ${𝔼}_{(i)}$ l'espérance conditionnelle conditionnée par rapport à $(X_1,\dots ,X_i)$ (avec la convention ${𝔼}_{(0)}=𝔼$ et que l'on pose

$\mathrm{\forall }1\le i\le n,{\mathrm{\Delta }}_i={𝔼}_{(i)}[Z]-{𝔼}_{(i-1)}[Z]$

alors $Z-𝔼[Z]=\sum _{i=1}^n{\mathrm{\Delta }}_i.$

Donc $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=𝔼\left[{\left(\sum _{i=1}^n{\mathrm{\Delta }}_i\right)}^2\right]=\sum _{i=1}^n𝔼[{\mathrm{\Delta }}_i^2]+2\sum _{i<j}𝔼[{\mathrm{\Delta }}_i{\mathrm{\Delta }}_j].$

Or, si $i<j,{𝔼}_{(i)}[{\mathrm{\Delta }}_j]={𝔼}_{(i)}[{𝔼}_{(j)}[Z]-{𝔼}_{\mathbb{(}𝕛\mathbb{-}\mathrm{𝟙}\mathbb{)}}[Z]]={𝔼}_{(i)}[Z]-{𝔼}_{(i)}[Z]=0$ donc

$𝔼[{\mathrm{\Delta }}_i{\mathrm{\Delta }}_j]=𝔼[{𝔼}_{(i)}[{\mathrm{\Delta }}_i{\mathrm{\Delta }}_j]]=𝔼[{\mathrm{\Delta }}_i{𝔼}_{(i)}[{\mathrm{\Delta }}_j]]=0.$

On a donc à présent que $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\sum _{i=1}^n𝔼[{\mathrm{\Delta }}_i^2]$.

D'après le théorème de Fubini, ${𝔼}_{(i)}[{𝔼}^{(i)}[Z]]={𝔼}_{(i-1)}[Z]$, d'où ${\mathrm{\Delta }}_i={𝔼}_{(i)}[Z-{𝔼}^{(i)}[Z]]$. D'après l'inégalité de Jensen,

${\mathrm{\Delta }}_i^2={\left({𝔼}_{(i)}[Z-{𝔼}^{(i)}[Z]]\right)}^2\le {𝔼}_{(i)}\left[{(Z-{𝔼}^{(i)}[Z])}^2\right].$

Finalement, $\mathrm{V}\mathrm{a}\mathrm{r}(Z)=\sum _{i=1}^n𝔼[{\mathrm{\Delta }}_i^2]\le \sum _{i=1}^n𝔼\left[{𝔼}_{(i)}\left[{(Z-{𝔼}^{(i)}[Z])}^2\right]\right]=\sum _{i=1}^n𝔼\left[{(Z-{𝔼}^{(i)}[Z])}^2\right]$.

Démontrons maintenant l'égalité des termes pour le membre de droite de l'inégalité d'Efron-Stein. Si on note ${\mathrm{V}\mathrm{a}\mathrm{r}}^{(i)}$ la variance conditionnelle conditionnée par rapport à $X^{(i)}$ alors

$\sum _{i=1}^n𝔼[(Z-{𝔼}^{(i)}[Z]{)}^2]=\sum _{i=1}^n𝔼[{\mathrm{V}\mathrm{a}\mathrm{r}}^{(i)}(Z)].$

En utilisant le fait que si $X$ et $Y$ sont des variables aléatoires réelles indépendantes et identiquement distribuées alors $\mathrm{V}\mathrm{a}\mathrm{r}(X)=\frac{1}{2}𝔼[(X-Y{)}^2].$

Or conditionnellement à $X^{(i)}$, les variables $Z$ et ${Z_i}^{\prime }$ sont indépendantes et identiquement distribuées d'où

${\mathrm{V}\mathrm{a}\mathrm{r}}^{(i)}(Z)=\frac{1}{2}{𝔼}^{(i)}[(Z-{Z_i}^{\prime }{)}^2]={𝔼}^{(i)}[(Z-{Z_i}^{\prime }{)}_{+}^2]={𝔼}^{(i)}[(Z-{Z_i}^{\prime }{)}_{-}^2].$

La dernière égalité vient du fait que l'on puisse écrire que $\mathrm{V}\mathrm{a}\mathrm{r}(X)=\underset{a\in ℝ}{\inf }𝔼[(X-a{)}^2]$. Donc conditionnellement à $X^{(i)}$, on peut écrire que

${\mathrm{V}\mathrm{a}\mathrm{r}}^{(i)}(Z)=\underset{Z_i}{\inf }{𝔼}^{(i)}[(Z-Z_i{)}^2].$

Applications

Fonctions avec différences bornées

Une fonction $f:{𝒳}^n\to ℝ$ possède la propriété de différences bornées s'il existe des constantes positives $c_1,\dots ,c_n$tels que

$\mathrm{\forall }1\le i\le n,\underset{x_1,\dots ,x_n,{x_i}^{\prime }\in 𝒳}{\sup }|f(x_1,\dots ,x_n)-f(x_1,\dots ,x_{i-1},{x_i}^{\prime },x_{i+1},\dots ,x_n)|\le c_i$

Si une fonction $f$ vérifie cette propriété avec les constantes $c_1,\dots ,c_n$, alors d'après l'inégalité d'Efron-Stein et parce que ${\mathrm{V}\mathrm{a}\mathrm{r}}^{(i)}(Z)\le {𝔼}^{(i)}[(Z-Z_i{)}^2]$ pour $Z_i=\frac{1}{2}[\underset{{x_i}^{\prime }\in 𝒳}{\sup }f(X_1,\dots ,X_{i-1},{x_i}^{\prime },X_{i+1},\dots ,X_n)+\underset{{x_i}^{\prime }\in 𝒳}{\inf }f(X_1,\dots ,X_{i-1},{x_i}^{\prime },X_{i+1},\dots ,X_n)]$, on a

$\mathrm{V}\mathrm{a}\mathrm{r}(Z)\le \frac{1}{4}\sum _{i=1}^n{c}_i^2.$

Fonctions auto-bornées

On dit qu'une fonction positive $f:{𝒳}^n\to [0,\mathrm{\infty })$ est auto-bornée s'il existe des fonctions $f_i:{𝒳}^{n-1}\to ℝ$ tels que pour tout $x_1,\dots ,x_n\in 𝒳$ et tout $i=1,\dots ,n$,

$0\le f(x_1,\dots ,x_n)-f_i(x_1,\dots ,x_{i-1},x_{i+1},\dots ,x_n)\le 1$

et

$\sum _{i=1}^n(f(x_1,\dots ,x_n)-f_i(x_1,\dots ,x_{i-1},x_{i+1},\dots ,x_n))\le f(x_1,\dots ,x_n).$

D'après l'inégalité d'Efron-Stein, toute fonction $f$ auto-bornée vérifie $\mathrm{V}\mathrm{a}\mathrm{r}(f(X_1,\dots ,X_n))\le 𝔼[f(X_1,\dots ,X_n)]$.