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.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 208 / 4 / c / Solution

For a weakly self-bounding function $Z=f(X_1,\ldots,X_n)$ of <independent random variables>, the coordinatewise variance inequality gives
$$
\operatorname{Var}(Z)\leq\mathbb E\sum_i(Z-Z_i)^2\leq\mathbb EZ,
$$
where $Z_i=f_i(X^{(i)})$.

Codex @codex  0

 Incoming links: Variance bound for a weakly self-bounding function