Talagrand concentration inequality for certifiable functions

For a nonnegative integer-valued certifiable function $Z=f(X)$ of independent random variables, suppose changing one coordinate changes $f$ by at most $L>0$ and a value $f(x)\ge b$ has a certificate involving at most $rb$ coordinates, with $r>0$. Then for $0\le a<b$,For a high-value input $x$, every low-value input must disagree with its certificate on at least $(b-a)/L$ coordinates: replacing its certificate positions by those of $x$ would change the low value by less than $b-a$ but force a value at least $b$. Uniform weights $1/\sqrt{rb}$ on certificate positions therefore give Talagrand convex distance at least $(b-a)/(L\sqrt{rb})$ from the low-value event. Apply Talagrand's convex distance inequality to that event.

The bound is useful when one of the two events has known nonnegligible probability, for example at a median. A certificate alone supplies no coordinate-change constant $L$; both hypotheses are used in the proof. The two-threshold concentration for certifiable functions article develops the resulting mean-median comparison.

Suppose an integer-valued certifiable function is $L$-Lipschitz under one-coordinate changes and a value at least $b$ has a certificate of at most $rb$ coordinates. Any input with value at most $a<b$ must differ on at least $(b-a)/L$ certificate positions. Equal weights on those positions bound its Talagrand convex distance from the low-value event. Applying Talagrand's convex distance inequality gives the displayed product bound. For $0\le Z\le D$, median tails integrate to $|\mathbb{E}Z-\mathrm{med}Z|=O(L\sqrt{rD})$, and deviations of order $D$ have exponentially small probability.

For the longest increasing subsequence length $L$ on a product space of independent coordinates, a witness of length $\ell$ uses only $\ell$ coordinates. Any point with subsequence length at most $a$ must differ on at least $\ell -a$ witness positions. Weights $1/\sqrt{\ell }$ on those positions show $d_T(x,\{L\le a\})\ge (\ell -a)/\sqrt{\ell }$. Thus for $0\le a<b$,At a median $m$, this gives upper tail $2e^{-t^2/[4(m+t)]}$ and lower tail $2e^{-t^2/(4m)}$. Integrating the tails places the mean within $O(\sqrt{m}+1)$ of the median, so the natural concentration scale near the mean is $\sqrt{\mathbb{E}L}$. A random permutation is represented by the ranks of independent continuous variables; arbitrary dependent sequences need not obey this conclusion.