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

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