= Solution
Let $\ell^*$ be a maximizing index for the original sample. Since $Z_i'$ is at least the value of its $\ell^*$th linear form,
$$
(Z-Z_i')_+
\leq\{(X_i-X_i')A_{i,\ell^*}\}_+,
$$
and hence
$$
(Z-Z_i')_+^2
\leq(X_i-X_i')^2A_{i,\ell^*}^2.
$$
The one-sided replacement form of the <Efron–Stein inequality> is
$$
\operatorname{Var}(Z)
\leq\sum_i\mathbb E(Z-Z_i')_+^2.
$$
For independent uniform signs, $\mathbb E[(X_i-X_i')^2\mid X]=2$. It follows that
$$
\operatorname{Var}(Z)
\leq2\mathbb E\sum_iA_{i,\ell^*}^2
\leq2\max_{1\leq\ell\leq m}\sum_iA_{i,\ell}^2.
$$
Back to article page
