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

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 givesThe coordinatewise conditional-variance form of the Efron–Stein inequality now yields

Replacing one input coordinate changes the longest increasing subsequence length by at most one, so $Z=L(X)$ has the bounded differences property with $c_i=1$. The two-sided McDiarmid inequality gives, for $t\ge 0$,

Let $Z_i$ be the longest increasing subsequence length after deleting coordinate $i$. Then $0\le Z-Z_i\le 1$. 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$. Henceso $Z$ is a weakly self-bounding function. The variance bound for a weakly self-bounding function gives

The coordinate-deletion functions from part c show that $Z$ is weakly self-bounding. Its negative centered moment-generating function therefore satisfies the lower-tail concentration for a weakly self-bounding function estimateApplying the Chernoff bound, for every $\lambda \ge 0$,The exponent is minimized at $\lambda =t/\mathbb{E}Z$, giving