What is a good lower-bound for $P(\|N(0,I_m)\| \ge \sqrt{m/\log m})$, valid for large $m$?

Question

Let $X$ be a random vector in $\mathbb R^m$ with iid entries from $N(0,1)$. The dimension $m$ might be assumed "large".

Question. What is a good lower-bound for $\mathbb P(\|X\| \ge \sqrt{m/\log m})$ ?

Answer 1

If $X = (X_1, ..., X_m)$ where $X_i$ are i.i.d $N(0,1)$, then $\|X\|^2 = \sum_{i=1}^m X_i^2 \sim \chi^2_{m}$, a $\chi^2$ distribution with $m$ degrees of freedom, and $E\|X\|^2 = m$. As $m\rightarrow\infty$, $$P(\|X\| \geq \sqrt{m/\log m})=P(\|X\|^2 \geq m/\log m)\rightarrow 1.$$ To get lower bounds you can recognize this as a large deviations problem: for some $\alpha \in (0,1)$ and $m \geq 3$, $$P(\|X\|^2 \geq m/\log m) \geq P(\|X\|^2\geq m \alpha),$$ and by Cramer's theorem, $$\lim_{m\rightarrow\infty} \frac{1}{m}\log P(\|X\|^2 \leq m \alpha) = -I(\alpha),$$ where $I(\alpha)$ is the Legendre-Fenchel transform of the log-moment generating function of a $\chi^2$ random variable, computed here to be $$I(\alpha) = \frac{\alpha-1-\log(\alpha)}{2}.$$ (I believe $I(\alpha)$ is correct; consult Wikipedia for the moment generating function $m(t)$ and compute $\sup_{t > 0} \{\alpha t - m(t)\}$.) Then, for any $\alpha \in (0,1)$ and $\varepsilon > 0$, you have the following lower bound for sufficiently large $m$: $$P(\|X\| \geq \sqrt{m/\log m})\geq 1-P(\|X\|^2 \leq m\alpha)\geq 1-e^{-m (I(\alpha)-\varepsilon)}. $$

Answer 2

This is a non-asymptotic version of @snar's bound, obtainable from directly applying Chernoff. I hope I haven't overlooked anything in the computations...

---

By Cherchoff, we have non-asymptotic bound

$$ \frac{1}{m}\log P(\|X\|^2 \le m\alpha) \le -I^*(\alpha), $$

where $I^*(a) := \sup_{t \in \mathbb R} ta - I(t)$, and $I(t) := \log\mathbb E[e^{tX_1^2}]$, the log-MGF of $X_1^2$. One may compute $I^*(\alpha) = (\alpha-1-\log\alpha)/2$ for $\alpha \in (0, 1)$. Plugging $\alpha = 1/\log m$ with $m \ge 4$, we get

$$ \frac{1}{m} \log P(\|X\|^2 \le m/\log m) \le -I^*(1/\log m) = \frac{1/\log m - 1 + \log\log m}{2} \le \frac{\log\log m}{2}, $$

from where $P(\|X\|^2 \le m/\log m) \le e^{-(m\log\log m)/2} = \left(\frac{1}{\log m}\right)^{m/2}$. Putting things together, we have proved the following non-asymptotic bound

$$ P(\|X\|^2 \ge m/\log m) \ge 1 - \left(\frac{1}{\log m}\right)^{m/2} \ge 1 - e^{-Cm}, $$

where the last inequality is for anu fixed $C > 0$ and $m$ sufficiently large (but finite!).