= Solution
Write $X_{-i}$ for all coordinates except $X_i$, let $X_i'$ be an <independent random variable> with the same distribution as $X_i$, and let $Z_i'=f(X_1,\ldots,X_i',\ldots,X_n)$. Three equivalent forms of the <Efron–Stein inequality> are
$$
\operatorname{Var}(Z)
\leq\sum_{i=1}^n\mathbb E\operatorname{Var}(Z\mid X_{-i}),
$$
$$
\operatorname{Var}(Z)
\leq\sum_{i=1}^n\mathbb E(Z-Z_i)^2
$$
for arbitrary square-integrable $Z_i$ measurable with respect to $X_{-i}$, and
$$
\operatorname{Var}(Z)
\leq\frac12\sum_{i=1}^n\mathbb E(Z-Z_i')^2.
$$
The first is the sharp choice within the second because <conditional expectation> is the least-squares projection. The first and third right sides are equal because two conditionally independent copies have expected squared difference twice their <conditional variance>.
Back to article page
