Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 208 / 2

Write $X_{-i}$ for all coordinates except $X_i$, let $X_i^{\prime }$ be an independent random variable with the same distribution as $X_i$, and let $Z_i^{\prime }=f(X_1,\dots ,X_i^{\prime },\dots ,X_n)$. Three equivalent forms of the Efron–Stein inequality arefor arbitrary square-integrable $Z_i$ measurable with respect to $X_{-i}$, andThe 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.

The bounded differences property with constants $c_i$ meanswhenever $x$ and $x^{\prime }$ differ only in coordinate $i$. Conditional on $X_{-i}$, the range of $Z$ is therefore at most $c_i$. The range bound on variance givesSubstitution into the Efron–Stein inequality yields

Changing $X_k$ while keeping all other coordinates fixed changes every candidate linear form by at mostThe maximum of finitely many functions obeys the same bound, so part b applies with $c_k=2{\max }_{\ell }|A_{k,\ell }|$. Therefore

Let ${\ell }^{\ast }$ be a maximizing index for the original sample. Since $Z_i^{\prime }$ is at least the value of its ${\ell }^{\ast }$th linear form,and henceThe one-sided replacement form of the Efron–Stein inequality isFor independent uniform signs, $\mathbb{E}[(X_i-X_i^{\prime }{)}^2\mid X]=2$. It follows that