= Solution
Let $Z_i$ be the longest increasing subsequence length after deleting coordinate $i$. Then $0\leq Z-Z_i\leq1$. Choose one longest increasing subsequence $I$ of length $Z$. If deleting $i$ reduces the optimum, then $i$ must belong to $I$; consequently at most $Z$ coordinates can satisfy $Z-Z_i=1$. Hence
$$
\sum_{i=1}^n(Z-Z_i)^2\leq Z,
$$
so $Z$ is a <weakly self-bounding function>. The <variance bound for a weakly self-bounding function> gives
$$
\operatorname{Var}(Z)leq\mathbb EZ.
$$
Back to article page
