inequality for real-valued Gaussian sums

Question

I saw the following Lemma in an article:

Let $\mathbf{b}\in \mathbb{R}^N$ be fixed, and let $\mathbf{\epsilon}\in \mathbb{R}^N$ be a random vector whose N entries are i.i.d. random variables drawn from a Gaussian distribution with $\mathcal{N}(0,\sigma^2)$. Then for any $u>0$,

$\mathbf{P} \left\{ | \sum_{i=1}^{N} \epsilon_ib_i | \ge u \right\} \le e^{- \frac{u^2}{2\sigma^2 ||\mathbf{b}||_2^2}} $

I have tried to prove this using Gaussian tail bound but ended up with something different. Here is what I have so far:

Proof:

Let random variable $Z=\sum_{i=1}^N b_i\epsilon_i$, then $\mathrm{E}[Z]=0, \mathrm{Var}[Z]=\sigma^2||\mathbf{b}||^2_2$. Since $Z$ is a linear combination of real Gaussian random variables, $Z$ is also Gaussian with $Z \sim \mathcal{N}(0,\sigma^2||\mathbf{b}||^2_2)$. Apply the Gaussian tail bound:

$\mathbf{P} \left\{ Z \ge u \right\} = \int_u^\infty \frac{1}{\sqrt{2\pi}\sigma||\mathbf{b}||_2} e^{-\frac{z^2}{2\sigma^2||\mathbf{b}||_2^2}}dz \le \frac{1}{\sqrt{2\pi}\sigma||\mathbf{b}||_2} \int_u^\infty \frac{z}{u} e^{-\frac{z^2}{2\sigma^2||\mathbf{b}||_2^2}}dz = \frac{\sigma||\mathbf{b}||_2}{\sqrt{2\pi}u} e^{-\frac{u^2}{2\sigma^2||\mathbf{b}||_2^2}}$

Due to symmetry of distribution, we have

$\mathbf{P} \left\{ |Z| \ge u \right\} \le \frac{2\sigma||\mathbf{b}||_2}{\sqrt{2\pi}u} e^{-\frac{u^2}{2\sigma^2||\mathbf{b}||_2^2}}$,

which is off by a factor of $\frac{2\sigma||\mathbf{b}||_2}{\sqrt{2\pi}u}$ compared to the original statement.

I feel like I must have missed something important, can anyone help me ? Thanks

Answer 1

Your computation is correct. I can only speculate that this may have been in a context where the $2 \sigma \|b\|_2/(\sqrt{2\pi}u)$ didn't make a difference --- or else it was just a mistake.

Answer 2

The bound $P(Z>u)\le \exp(- \frac{u^2}{2\sigma^2\|b\|^2})$ is also correct. To prove it, apply Markov's inequality after applying $t\mapsto\exp(\lambda t)$: $$ P(e^{\lambda Z} > e^{u\lambda}) \le e^{-u\lambda}E[e^{\lambda Z}] = e^{-u\lambda} \exp(\lambda^2 \sigma^2 \|b\|^2/2), $$ and choose $\lambda$ so that the right hand side is minimzed and equal to $\exp(- \frac{u^2}{2\sigma^2\|b\|^2})$. This is known sometimes as a "Chernoff bound".

So both the lemma from the article and your conclusions are correct. One of them is sharper than the other, depending whether $\sigma\|b\|/\sqrt{2\pi u}$ is greater than 1.