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\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.