I have been studying about tail bounds and I read the following claim:
A variable $\xi \sim N(0, 1)$ satisfies the following tail bound for $t \geq 1$:
$ \mathbb{P}(\xi \geq t) \leq e^{-t^2/2} $
We also know that if $\mathbf{x} \sim N(0, \text{Id}_n)$ (where $\text{Id}_n$ is the identity matrix belonging in $\mathbb{R}^{n\times n}$) the distribution of its squared Euclidean norm $\|\mathbf{x}\|^2$ is called $\chi^2$-distribution, that has the following tail bound for $t \geq 1$:
$ \mathbb{P}(\|\mathbf{x}\|^2 \geq t\cdot n) \leq e^{-t\cdot n/10}$
However somewhere else I have seen the following tail bound for the $\chi^2$-distribution:$ \mathbb{P}(\|\mathbf{x}\|^2 \geq t\cdot 2n) \leq e^{-t\cdot n/10}$
Which of two tail bounds for the $\chi^2$-distribution is correct and can we prove that using the Gaussian tail bound that I gave in the beginning?
Best Answer
One can verify the latter version of the bound using Lemma 1 from [Laurent & Massart, 2000], which states that a $\chi^2(n)$ variable $Z$ satisfies
$$ \mathbb{P}(Z \geq n + 2\sqrt{nx} + 2x) \leq e^{-x}. $$
We can write $2tn = n + (2t - 1)n$, so setting $x = tn/10$ we recover
$$ \mathbb{P}\left(\|x\|_2^2 \geq n + 2n\left(\sqrt{t/10} + t/10\right)\right) \leq \exp(-tn/10). $$
It suffices to show that $2t - 1 \geq 2 \left(\sqrt{t/10} + t/10 \right)$. Since $t \geq 1$, we can just show that $2 t - 1 \geq 2 \cdot \frac{2t}{10} \geq 2 \left(\sqrt{t/10} + t/10\right)$, which is true $\forall t \geq 1$ - the claim follows.