= Variance tensorization
{title2=$\operatorname{Var}(Z)\leq\sum_i\mathbb E[\operatorname{Var}(Z\mid X_{-i})]$}
Write $X_{-i}$ for all inputs except $X_i$. Under the <Efron–Stein inequality> hypotheses, <variance tensorization> is the equivalent <conditional variance> form
$$
\boxed{\operatorname{Var}(Z)\leq\sum_{i=1}^n\mathbb E[\operatorname{Var}(Z\mid X_{-i})].}
$$
Conditioning freezes the other inputs. Then $Z,Z_i'$ are <independent> with the same conditional <probability distribution>, giving
$$
\frac12\mathbb E[(Z-Z_i')^2\mid X_{-i}]=\operatorname{Var}(Z\mid X_{-i}).
$$
Taking <expected values> explains the factor $1/2$.<Lecture 7a: Efron Stein inequality by Purnamrita Sarkar>[Lecture 7a: Efron Stein inequality, slides 2 and 7, PDF pp. 3 and 8: conditional variances and the independent-copy identity]{ref}
For <Bernoulli> input $X_i$ with parameter $p_i$, let $\Delta_i f$ be the value of $f$ with coordinate $i$ set to one minus its value with that coordinate set to zero, keeping $X_{-i}$ fixed. The two-point <conditional variance> is
$$
\operatorname{Var}(Z\mid X_{-i})=p_i(1-p_i)(\Delta_i f)^2.
$$
For the maximum example, $\Delta_1 f=1-X_2$ and $\Delta_2 f=1-X_1$. The two averaged <conditional variances> are $0.3(0.7)(0.4)=0.084$ and $0.6(0.4)(0.7)=0.168$, precisely half the respective resampling terms. In the dependent example $X_1=X_2=B$, each other coordinate already determines $W$, so both <conditional variances> vanish; <variance tensorization> also fails without <independence>.
For a short induction proof, separate the last input using the <law of total variance>. Apply the smaller-dimensional statement to the <conditional expectation>; <Jensen's inequality> for the square bounds its coordinate contributions by the original ones. One input gives equality, starting the induction.<Lecture 7a: Efron Stein inequality by Purnamrita Sarkar>[Lecture 7a: Efron Stein inequality, slides 3–6, PDF pp. 4–7: variance decomposition and conditional Jensen step; the induction outline here reorganizes those ingredients]{ref}
Back to article page
