Soient
X
1
,
…
,
X
n
{\displaystyle X_{1},\dots ,X_{n}}
X
,
Z
=
f
(
X
1
,
…
,
X
n
)
{\displaystyle {\mathcal {X}},Z=f(X_{1},\dots ,X_{n})}
X
1
,
…
,
X
n
{\displaystyle X_{1},\dots ,X_{n}}
f
:
X
n
→
R
{\displaystyle f\colon {\mathcal {X}}^{n}\to \mathbb {R} }
V
a
r
(
Z
)
≤
∑
i
=
1
n
E
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
{\displaystyle \mathrm {Var} (Z)\leq \sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]}
où
E
(
i
)
{\displaystyle \mathbb {E} ^{(i)}}
espérance conditionnelle conditionnée par rapport à
X
(
i
)
=
(
X
1
,
…
,
X
i
−
1
,
X
i
+
1
,
…
X
n
)
{\displaystyle X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i+1},\dots X_{n})}
E
(
i
)
Z
=
∫
X
f
(
X
1
,
…
,
X
i
−
1
,
x
,
X
i
+
1
,
…
,
X
n
)
d
μ
i
(
x
)
{\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ù
μ
i
{\displaystyle \mu _{i}}
est la densité de
X
i
{\displaystyle X_{i}}
.
Si on pose
X
1
′
,
…
,
X
n
′
{\displaystyle X_{1}',\dots ,X_{n}'}
X
1
,
…
,
X
n
{\displaystyle X_{1},\dots ,X_{n}}
Z
i
′
=
f
(
X
1
,
…
,
X
i
−
1
,
X
i
′
,
X
i
+
1
,
…
,
X
n
)
{\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 :
∑
i
=
1
n
E
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
=
1
2
∑
i
=
1
n
E
[
(
Z
−
Z
i
′
)
2
]
=
∑
i
=
1
n
E
[
(
Z
−
Z
i
′
)
+
2
]
=
∑
i
=
1
n
E
[
(
Z
−
Z
i
′
)
−
2
]
{\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ù
x
+
=
max
(
x
,
0
)
{\displaystyle x_{+}=\max(x,0)}
et
x
−
=
max
(
−
x
,
0
)
{\displaystyle x_{-}=\max(-x,0)}
.
On peut également écrire que
∑
i
=
1
n
E
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
=
inf
Z
i
∑
i
=
1
n
E
[
(
Z
−
Z
i
)
2
]
{\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]}
X
(
i
)
{\displaystyle X^{(i)}}
Z
i
{\displaystyle Z_{i}}
L'idée de la preuve est de généraliser le cas où quand
Z
=
X
1
+
⋯
+
X
n
{\displaystyle Z=X_{1}+\dots +X_{n}}
V
a
r
(
Z
)
=
∑
i
=
1
n
V
a
r
(
X
i
)
.
{\displaystyle \mathrm {Var} (Z)=\sum _{i=1}^{n}\mathrm {Var} (X_{i}).}
[ 1]
Si on note
E
(
i
)
{\displaystyle \mathbb {E} _{(i)}}
(
X
1
,
…
,
X
i
)
{\displaystyle (X_{1},\dots ,X_{i})}
E
(
0
)
=
E
{\displaystyle \mathbb {E} _{(0)}=\mathbb {E} }
∀
1
≤
i
≤
n
,
Δ
i
=
E
(
i
)
[
Z
]
−
E
(
i
−
1
)
[
Z
]
{\displaystyle \forall 1\leq i\leq n,\qquad \Delta _{i}=\mathbb {E} _{(i)}[Z]-\mathbb {E} _{(i-1)}[Z]}
alors
Z
−
E
[
Z
]
=
∑
i
=
1
n
Δ
i
.
{\displaystyle Z-\mathbb {E} [Z]=\sum _{i=1}^{n}\Delta _{i}.}
Donc
V
a
r
(
Z
)
=
E
[
(
∑
i
=
1
n
Δ
i
)
2
]
=
∑
i
=
1
n
E
[
Δ
i
2
]
+
2
∑
i
<
j
E
[
Δ
i
Δ
j
]
.
{\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
i
<
j
,
E
(
i
)
[
Δ
j
]
=
E
(
i
)
[
E
(
j
)
[
Z
]
−
E
(
j
−
1
)
[
Z
]
]
=
E
(
i
)
[
Z
]
−
E
(
i
)
[
Z
]
=
0
{\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}
E
[
Δ
i
Δ
j
]
=
E
[
E
(
i
)
[
Δ
i
Δ
j
]
]
=
E
[
Δ
i
E
(
i
)
[
Δ
j
]
]
=
0.
{\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
V
a
r
(
Z
)
=
∑
i
=
1
n
E
[
Δ
i
2
]
{\displaystyle \mathrm {Var} (Z)=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]}
D'après le théorème de Fubini ,
E
(
i
)
[
E
(
i
)
[
Z
]
]
=
E
(
i
−
1
)
[
Z
]
{\displaystyle \mathbb {E} _{(i)}\left[\mathbb {E} ^{(i)}[Z]\right]=\mathbb {E} _{(i-1)}[Z]}
Δ
i
=
E
(
i
)
[
Z
−
E
(
i
)
[
Z
]
]
{\displaystyle \Delta _{i}=\mathbb {E} _{(i)}\left[Z-\mathbb {E} ^{(i)}[Z]\right]}
inégalité de Jensen ,
Δ
i
2
=
(
E
(
i
)
[
Z
−
E
(
i
)
[
Z
]
]
)
2
≤
E
(
i
)
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
.
{\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,
V
a
r
(
Z
)
=
∑
i
=
1
n
E
[
Δ
i
2
]
≤
∑
i
=
1
n
E
[
E
(
i
)
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
]
=
∑
i
=
1
n
E
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
{\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
V
a
r
(
i
)
{\displaystyle \mathrm {Var} ^{(i)}}
X
(
i
)
{\displaystyle X^{(i)}}
∑
i
=
1
n
E
[
(
Z
−
E
(
i
)
[
Z
]
)
2
]
=
∑
i
=
1
n
E
[
V
a
r
(
i
)
(
Z
)
]
.
{\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
X
{\displaystyle X}
Y
{\displaystyle Y}
V
a
r
(
X
)
=
1
2
E
[
(
X
−
Y
)
2
]
.
{\displaystyle \mathrm {Var} (X)={\frac {1}{2}}\mathbb {E} \left[(X-Y)^{2}\right].}
Or conditionnellement à
X
(
i
)
{\displaystyle X^{(i)}}
Z
{\displaystyle Z}
Z
i
′
{\displaystyle Z_{i}'}
V
a
r
(
i
)
(
Z
)
=
1
2
E
(
i
)
[
(
Z
−
Z
i
′
)
2
]
=
E
(
i
)
[
(
Z
−
Z
i
′
)
+
2
]
=
E
(
i
)
[
(
Z
−
Z
i
′
)
−
2
]
.
{\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
V
a
r
(
X
)
=
inf
a
∈
R
E
[
(
X
−
a
)
2
]
{\displaystyle \mathrm {Var} (X)=\inf _{a\in \mathbb {R} }\mathbb {E} [(X-a)^{2}]}
X
(
i
)
{\displaystyle X^{(i)}}
V
a
r
(
i
)
(
Z
)
=
inf
Z
i
E
(
i
)
[
(
Z
−
Z
i
)
2
]
.
{\displaystyle \mathrm {Var} ^{(i)}(Z)=\inf _{Z_{i}}\mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right].}
modifier
Une fonction
f
:
X
n
→
R
{\displaystyle f\colon {\mathcal {X}}^{n}\to \mathbb {R} }
c
1
,
…
,
c
n
{\displaystyle c_{1},\dots ,c_{n}}
∀
1
≤
i
≤
n
,
sup
x
1
,
…
,
x
n
,
x
i
′
∈
X
|
f
(
x
1
,
…
,
x
n
)
−
f
(
x
1
,
…
,
x
i
−
1
,
x
i
′
,
x
i
+
1
,
…
,
x
n
)
|
≤
c
i
{\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
f
{\displaystyle f}
c
1
,
…
,
c
n
{\displaystyle c_{1},\dots ,c_{n}}
[ 1]
V
a
r
(
i
)
(
Z
)
≤
E
(
i
)
[
(
Z
−
Z
i
)
2
]
{\displaystyle \mathrm {Var} ^{(i)}(Z)\leq \mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right]}
Z
i
=
1
2
[
sup
x
i
′
∈
X
f
(
X
1
,
…
,
X
i
−
1
,
x
i
′
,
X
i
+
1
,
…
,
X
n
)
+
inf
x
i
′
∈
X
f
(
X
1
,
…
,
X
i
−
1
,
x
i
′
,
X
i
+
1
,
…
,
X
n
)
]
{\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]}
V
a
r
(
Z
)
≤
1
4
∑
i
=
1
n
c
i
2
.
{\displaystyle \mathrm {Var} (Z)\leq {\frac {1}{4}}\sum _{i=1}^{n}c_{i}^{2}.}
On dit qu'une fonction positive
f
:
X
n
→
[
0
,
∞
)
{\displaystyle f:{\mathcal {X}}^{n}\to [0,\infty )}
f
i
:
X
n
−
1
→
R
{\displaystyle f_{i}:{\mathcal {X}}^{n-1}\to \mathbb {R} }
x
1
,
…
,
x
n
∈
X
{\displaystyle x_{1},\dots ,x_{n}\in {\mathcal {X}}}
i
=
1
,
…
,
n
{\displaystyle i=1,\dots ,n}
0
≤
f
(
x
1
,
…
,
x
n
)
−
f
i
(
x
1
,
…
,
x
i
−
1
,
x
i
+
1
,
…
,
x
n
)
≤
1
{\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
∑
i
=
1
n
(
f
(
x
1
,
…
,
x
n
)
−
f
i
(
x
1
,
…
,
x
i
−
1
,
x
i
+
1
,
…
,
x
n
)
)
≤
f
(
x
1
,
…
,
x
n
)
.
{\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
f
{\displaystyle f}
V
a
r
(
f
(
X
1
,
…
,
X
n
)
)
≤
E
[
f
(
X
1
,
…
,
X
n
)
]
{\displaystyle \mathrm {Var} (f(X_{1},\dots ,X_{n}))\leq \mathbb {E} [f(X_{1},\dots ,X_{n})]}
↑ a et b (en) Stéphane Boucheron, Gabor Lugosi et Pascal Massart, Concentration inequalities: A Nonasymptotic Theory of Independence , OUP Oxford, 496 p. (ISBN 019876765X 
![{\displaystyle \mathrm {Var} (Z)\leq \sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e8b33315bc1e2f4bff72b0e0519f369f00bdcaf)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b1edfc8f7e0288e5fb61633b5bc01790e1c45ae)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40778b2483d481f05352c96802fc34edc70f7f36)
![{\displaystyle \forall 1\leq i\leq n,\qquad \Delta _{i}=\mathbb {E} _{(i)}[Z]-\mathbb {E} _{(i-1)}[Z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c798a15f3ab720ac9ace4e609b4454089d50c4)
![{\displaystyle Z-\mathbb {E} [Z]=\sum _{i=1}^{n}\Delta _{i}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb0094963831d832b3f07c3a4daf352c61bcfe1c)
![{\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}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc6f17b34e0db37ea131dc86b984b7ca02cf302d)
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18063dc8a030de4910199925f8f41c7993ca4c3f)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4770069a801e787a67e49aad3740b21cd612418c)
![{\displaystyle \mathrm {Var} (Z)=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5595b28a774ffbf5abb80eb9fa5a1c387e4f4eb)
![{\displaystyle \mathbb {E} _{(i)}\left[\mathbb {E} ^{(i)}[Z]\right]=\mathbb {E} _{(i-1)}[Z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e885e522d48d35ea9431d26bd155e8a7b3517517)
![{\displaystyle \Delta _{i}=\mathbb {E} _{(i)}\left[Z-\mathbb {E} ^{(i)}[Z]\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7aec048da807715e4707849c7d5fb120ae6d2ba9)
![{\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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d22f67661e88e177ae56a882b4cea5bcb3d8ba2e)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f2b924da9b3571b1d138d54630684c42634c3b3)
![{\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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04d136eb9b2c8dfa85bb36a82185394d197d1d12)
![{\displaystyle \mathrm {Var} (X)={\frac {1}{2}}\mathbb {E} \left[(X-Y)^{2}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e9b772049afa292a52428e9d09acf1ff5c7a2c0)
![{\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].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b572441585649f43c1b90cb761ee51f574519bcc)
![{\displaystyle \mathrm {Var} (X)=\inf _{a\in \mathbb {R} }\mathbb {E} [(X-a)^{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fb6409f066794a19d43c4c58a11103e8d917b84)
![{\displaystyle \mathrm {Var} ^{(i)}(Z)=\inf _{Z_{i}}\mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/847cbf523b5c540e1b3bca6d30097274437db35e)
![{\displaystyle \mathrm {Var} ^{(i)}(Z)\leq \mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f7359aaa5cb3ad7e8bcb2925040c2902284d044)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c128c12b4cfeb02cd8ab68e44b3019409feb684)
![{\displaystyle \mathrm {Var} (f(X_{1},\dots ,X_{n}))\leq \mathbb {E} [f(X_{1},\dots ,X_{n})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edd7299d9ff95cc5f4d838ef143b24198fb7e23b)
