= Efron–Stein inequality
{c}
{title2=$\operatorname{Var}(Z)\leq\frac12\sum_i\mathbb E(Z-Z_i')^2$}
{wiki}
The <Efron–Stein inequality> bounds the <variance> of a complicated output by the effect of replacing one input at a time. Let $X_1,\ldots,X_n$ be mutually <independent random variables>, not necessarily identically distributed, and $Z=f(X_1,\ldots,X_n)$ for a <measurable function> $f$, with $\mathbb E Z^2<\infty$. Take $X_1',\ldots,X_n'$ with $X_i'$ having the same <probability distribution> as $X_i$, all $2n$ inputs mutually <independent>. Define
$$
Z_i'=f(X_1,\ldots,X_{i-1},X_i',X_{i+1},\ldots,X_n).
$$
Use the same <function> $f$, keeping every other input fixed. Then
$$
\boxed{\operatorname{Var}(Z)\leq\frac12\sum_{i=1}^n\mathbb E[(Z-Z_i')^2].}
$$
The <expected value> averages over both the original inputs and their replacements. An infinite right side gives a trivial bound; under the stated <square-integrable> condition every term is finite.<Lecture 7a: Efron Stein inequality by Purnamrita Sarkar>[Lecture 7a: Efron Stein inequality, slides 1–2 and 7, PDF pp. 2–3 and 8: independent inputs, conditional-variance bound and independent-copy form]{ref}
For a concrete four-state example, take <independent> <Bernoulli random variables> with $\mathbb P(X_1=1)=0.3$ and $\mathbb P(X_2=1)=0.6$, and set $Z=\max\{X_1,X_2\}$. This output records whether either input is one. The states $(0,0),(1,0),(0,1),(1,1)$ have respective <probabilities> $0.28,0.12,0.42,0.18$, so
$$
\mathbb P(Z=1)=0.72,\qquad \operatorname{Var}(Z)=0.72(1-0.72)=0.2016.
$$
Replacing $X_1$ changes $Z$ only when $X_2=0$ and $X_1'\ne X_1$. A fresh <Bernoulli> draw can repeat the old value: the replacement is not a forced flip. By <independence>, the <expected value> of the squared change is
$$
\mathbb E[(Z-Z_1')^2]=0.4\,[0.7(0.3)+0.3(0.7)]=0.168.
$$
Similarly,
$$
\mathbb E[(Z-Z_2')^2]=0.7\,[0.4(0.6)+0.6(0.4)]=0.336.
$$
Thus <Efron–Stein inequality> gives $0.2016\leq(0.168+0.336)/2=0.252$. The larger second contribution reflects both its replacement <probability> and how often the other input leaves the output sensitive to it.
\Image[/efron-stein-weighted-resampling-states.png]
{title=Four weighted states explain the <Efron–Stein inequality> resampling contributions}
{description=Original constructed model: <independent> <Bernoulli random variables> with parameters $0.3$ and $0.6$, and $Z=\max\{X_1,X_2\}$. Each node shows its joint <probability>. Directed arrow labels are joint <probabilities> of the original state and replacement value, rather than conditional transition probabilities. Only solid edges change $Z$; same-state replacements and the dashed edges contribute zero. Both directions count before the factor $1/2$.}
For the same inputs, consider instead $W=X_1+2X_2$. The <variance of a sum> of <independent random variables> gives
$$
\operatorname{Var}(W)=0.3(0.7)+4(0.6)(0.4)=1.17.
$$
Here $\mathbb E[(W-W_1')^2]=0.42$ and $\mathbb E[(W-W_2')^2]=1.92$, so the <Efron–Stein inequality> is exact: $(0.42+1.92)/2=1.17$. More generally, for $W=c+\sum_i g_i(X_i)$ with <square-integrable> summands, each contribution $\frac12\mathbb E[(W-W_i')^2]$ equals $\operatorname{Var}(g_i(X_i))$ and these <variances> add exactly.
\b[<Independence> is essential.] Let $X_1=X_2=B$ for a single <Bernoulli random variable> with parameter $1/2$, and take $W=X_1+X_2=2B$. Its <variance> is one. If each coordinate is nevertheless replaced by an <independent> draw from its marginal <Bernoulli distribution>, each squared-change <expected value> is $1/2$, giving the false proposed upper bound $1/2$. Replacement now creates off-diagonal states $(0,1)$ and $(1,0)$ that the original input never visits. The original coordinates fail the hypothesis of <Efron–Stein inequality>.
\Image[/efron-stein-variance-and-independence.png]
{title=The <Efron–Stein inequality> can be loose, exact, or inapplicable when <independence> fails}
{description=Exact enumeration in three constructed models: the four-state maximum has <variance> $0.2016$ and bound $0.252$; the weighted <sum> on the same <independent> inputs has <variance> and bound $1.17$; the dependent model $X_1=X_2=B$ has <variance> one but marginal replacement produces $0.5$, which is not a valid bound. Stacked contributions are half the squared-change <expected values>. The third panel deliberately violates the theorem's assumption.}
The attraction is local calculation: a <function> may involve many inputs, yet changing one can have a simple effect. Each half squared-change <expected value> supplies a coordinate's contribution to an upper budget for the total <variance>. Applying <Chebyshev's inequality> then bounds a <tail probability> using that budget. These contributions need not partition the actual <variance>, as the maximum example shows.
The name commemorates <Bradley Efron> and <Charles M. Stein>. Their 1981 paper https://projecteuclid.org/journals/annals-of-statistics/volume-9/issue-3/The-Jackknife-Estimate-of-Variance/10.1214/aos/1176345462.full[The Jackknife Estimate of Variance] appeared in The Annals of Statistics, volume 9, issue 3, pp. 586–596.<Bradley Efron's Profile, Stanford University>[Publications: The Jackknife Estimate of Variance, Efron and Stein, 1981, 9(3), 586–596]{ref}
Back to article page
