= Increasing-subsequence certificate concentration
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\leq a\})\geq(\ell-a)/\sqrt\ell$. Thus for $0\leq a<b$,
$$
\Pr(L\leq a)\Pr(L\geq b)\leq e^{-(b-a)^2/(4b)}.
$$
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 EL}$. A random permutation is represented by the ranks of independent continuous variables; arbitrary dependent sequences need not obey this conclusion.
Back to article page
