= Solution
Fix every coordinate except $X_i$. As $X_i$ varies, the <longest increasing subsequence> length can change by at most one: deleting the changed term leaves a common subsequence of length at least the larger value minus one. The conditional range therefore has length at most one, so the <Popoviciu inequality on variances> gives
$$
\operatorname{Var}(Z\mid X^{(i)})\leq\frac14.
$$
The coordinatewise conditional-variance form of the <Efron–Stein inequality> now yields
$$
\operatorname{Var}(Z)
\leq\sum_{i=1}^n\mathbb E[\operatorname{Var}(Z\mid X^{(i)})]
\leq\frac n4.
$$
Back to article page
