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.

Soient ${\displaystyle X_{1},\dots ,X_{n}}$ des variables aléatoires indépendantes à valeurs dans un espace ${\displaystyle {\mathcal {X}},Z=f(X_{1},\dots ,X_{n})}$ une fonction générale des ${\displaystyle X_{1},\dots ,X_{n}}$ avec ${\displaystyle f\colon {\mathcal {X}}^{n}\to \mathbb {R} }$ alors

${\displaystyle \mathrm {Var} (Z)\leq \sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]}$

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

${\displaystyle \mathbb {E} ^{(i)}Z=\int _{\mathcal {X}}f(X_{1},\dots ,X_{i-1},x,X_{i+1},\dots ,X_{n})\mathrm {d} \mu _{i}(x)}$ où ${\displaystyle \mu _{i}}$ est la densité de ${\displaystyle X_{i}}$.

Si on pose ${\displaystyle X_{1}',\dots ,X_{n}'}$ des copies indépendantes des ${\displaystyle X_{1},\dots ,X_{n}}$ et que l'on pose

${\displaystyle Z_{i}'=f(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})}$,

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

${\displaystyle \sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]={\frac {1}{2}}\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i}')^{2}\right]=\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i}')_{+}^{2}\right]=\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i}')_{-}^{2}\right]}$ où ${\displaystyle x_{+}=\max(x,0)}$ et ${\displaystyle x_{-}=\max(-x,0)}$.

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

L'idée de la preuve est de généraliser le cas où quand ${\displaystyle Z=X_{1}+\dots +X_{n}}$, on a ${\displaystyle \mathrm {Var} (Z)=\sum _{i=1}^{n}\mathrm {Var} (X_{i}).}$^[1]

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

${\displaystyle \forall 1\leq i\leq n,\qquad \Delta _{i}=\mathbb {E} _{(i)}[Z]-\mathbb {E} _{(i-1)}[Z]}$

alors ${\displaystyle Z-\mathbb {E} [Z]=\sum _{i=1}^{n}\Delta _{i}.}$

Donc ${\displaystyle \mathrm {Var} (Z)=\mathbb {E} \left[\left(\sum _{i=1}^{n}\Delta _{i}\right)^{2}\right]=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]+2\sum _{i<j}\mathbb {E} [\Delta _{i}\Delta _{j}].}$

Or, si ${\displaystyle i<j,\mathbb {E} _{(i)}[\Delta _{j}]=\mathbb {E} _{(i)}\left[\mathbb {E} _{(j)}[Z]-\mathbb {E_{(j-1)}} [Z]\right]=\mathbb {E} _{(i)}[Z]-\mathbb {E} _{(i)}[Z]=0}$ donc

${\displaystyle \mathbb {E} [\Delta _{i}\Delta _{j}]=\mathbb {E} \left[\mathbb {E} _{(i)}[\Delta _{i}\Delta _{j}]\right]=\mathbb {E} \left[\Delta _{i}\mathbb {E} _{(i)}[\Delta _{j}]\right]=0.}$

On a donc à présent que ${\displaystyle \mathrm {Var} (Z)=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]}$.

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

${\displaystyle \Delta _{i}^{2}=\left(\mathbb {E} _{(i)}\left[Z-\mathbb {E} ^{(i)}[Z]\right]\right)^{2}\leq \mathbb {E} _{(i)}\left[\left(Z-\mathbb {E} ^{(i)}[Z]\right)^{2}\right].}$

Finalement, ${\displaystyle \mathrm {Var} (Z)=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]\leq \sum _{i=1}^{n}\mathbb {E} \left[\mathbb {E} _{(i)}\left[\left(Z-\mathbb {E} ^{(i)}[Z]\right)^{2}\right]\right]=\sum _{i=1}^{n}\mathbb {E} \left[\left(Z-\mathbb {E} ^{(i)}[Z]\right)^{2}\right]}$.

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

${\displaystyle \sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]=\sum _{i=1}^{n}\mathbb {E} \left[\mathrm {Var} ^{(i)}(Z)\right].}$

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

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

${\displaystyle \mathrm {Var} ^{(i)}(Z)={\frac {1}{2}}\mathbb {E} ^{(i)}\left[(Z-Z_{i}')^{2}\right]=\mathbb {E} ^{(i)}\left[(Z-Z_{i}')_{+}^{2}\right]=\mathbb {E} ^{(i)}\left[(Z-Z_{i}')_{-}^{2}\right].}$

La dernière égalité vient du fait que l'on puisse écrire que ${\displaystyle \mathrm {Var} (X)=\inf _{a\in \mathbb {R} }\mathbb {E} [(X-a)^{2}]}$. Donc conditionnellement à ${\displaystyle X^{(i)}}$, on peut écrire que

${\displaystyle \mathrm {Var} ^{(i)}(Z)=\inf _{Z_{i}}\mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right].}$

Une fonction ${\displaystyle f\colon {\mathcal {X}}^{n}\to \mathbb {R} }$ possède la propriété de différences bornées s'il existe des constantes positives ${\displaystyle c_{1},\dots ,c_{n}}$tels que

${\displaystyle \forall 1\leq i\leq n,\qquad \sup _{x_{1},\dots ,x_{n},x_{i}'\in {\mathcal {X}}}|f(x_{1},\dots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\dots ,x_{n})|\leq c_{i}}$

Si une fonction ${\displaystyle f}$ vérifie cette propriété avec les constantes ${\displaystyle c_{1},\dots ,c_{n}}$, alors d'après l'inégalité d'Efron-Stein^[1] et parce que ${\displaystyle \mathrm {Var} ^{(i)}(Z)\leq \mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right]}$ pour ${\displaystyle Z_{i}={\frac {1}{2}}\left[\sup _{x_{i}'\in {\mathcal {X}}}f(X_{1},\dots ,X_{i-1},x_{i}',X_{i+1},\dots ,X_{n})+\inf _{x_{i}'\in {\mathcal {X}}}f(X_{1},\dots ,X_{i-1},x_{i}',X_{i+1},\dots ,X_{n})\right]}$, on a

${\displaystyle \mathrm {Var} (Z)\leq {\frac {1}{4}}\sum _{i=1}^{n}c_{i}^{2}.}$

On dit qu'une fonction positive ${\displaystyle f:{\mathcal {X}}^{n}\to [0,\infty )}$ est auto-bornée s'il existe des fonctions ${\displaystyle f_{i}:{\mathcal {X}}^{n-1}\to \mathbb {R} }$ tels que pour tout ${\displaystyle x_{1},\dots ,x_{n}\in {\mathcal {X}}}$ et tout ${\displaystyle i=1,\dots ,n}$,

${\displaystyle 0\leq f(x_{1},\dots ,x_{n})-f_{i}(x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{n})\leq 1}$

et

${\displaystyle \sum _{i=1}^{n}(f(x_{1},\dots ,x_{n})-f_{i}(x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{n}))\leq f(x_{1},\dots ,x_{n}).}$

D'après l'inégalité d'Efron-Stein, toute fonction ${\displaystyle f}$ auto-bornée vérifie ${\displaystyle \mathrm {Var} (f(X_{1},\dots ,X_{n}))\leq \mathbb {E} [f(X_{1},\dots ,X_{n})]}$.

• Portail des probabilités et de la statistique