= Chi-squared concentration inequality
{title2=$\mathbb P(V-n\geq2\sqrt{nx}+2x)\leq e^{-x}$}
For $V\sim\chi_n^2$ and $x>0$, the upper tail is at most $e^{-x}$ above $n+2\sqrt{nx}+2x$, and the lower tail is at most $e^{-x}$ below $n-2\sqrt{nx}$. Indeed $\log\mathbb E e^{s(V-n)}=-ns-(n/2)\log(1-2s)\leq ns^2/(1-2s)$ for $0<s<1/2$. The <Chernoff bound> with $s=\sqrt{x/n}/(1+2\sqrt{x/n})$ proves the upper estimate. For the lower estimate, $\log\mathbb E e^{-s(V-n)}\leq ns^2$ for $s>0$, and optimization gives the result. The lower threshold can be negative; the <chi-squared Chernoff lower-tail bound> provides an always-positive alternative.
Back to article page
