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

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