Talagrand concentration inequality for certifiable functions

This is an application of Talagrand's concentration inequality to certifiable functions. Talagrand's product-space inequality gives sub-Gaussian-type concentration for a bounded-differences, certifiable function, with a variance scale controlled by the certificate size.

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.