= Convex-chain median concentration
{title2=$\mathbb P(L_n\geq m+t)\leq2e^{-t^2/(4(m+t))},\quad\mathbb P(L_n\leq m-t)\leq2e^{-t^2/(4m)}$}
Let $m$ be an integer <median> for the <longest convex chain> length of independent uniform points in a <triangle>. If $L_n(x)\geq a$, fix a certificate of $a$ coordinates. Every configuration with $L_n\leq b$ must disagree with at least $a-b$ of those coordinates; equal weights $1/\sqrt a$ prove <Talagrand convex distance> separation at least $(a-b)/\sqrt a$. <Talagrand's convex distance inequality> then gives $\mathbb P(L_n\geq a)\mathbb P(L_n\leq b)\leq e^{-(a-b)^2/(4a)}$. Set $b=m$, then $a=m$, in the two respective applications to obtain the displayed tails for positive integer $t$. The exact chain-counting bound gives $m\leq Cn^{1/3}$. Hence any interval centred at $m$ with length $\omega(n)n^{1/6}$, where $\omega(n)\to\infty$, contains $L_n$ <with high probability>. No upper restriction on the growth of $\omega$ is required.
Back to article page
