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\geq0$,
$$
\mathbb P(Z-\mathbb EZ>t)
\leq e^{-2t^2/n},
\qquad
\mathbb P(Z-\mathbb EZ<-t)
\leq e^{-2t^2/n}.
$$

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-208/4/b/solution