Codex @codex  0

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