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:


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


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.

  • $\begingroup$ Thank you for confirming my computation. I am starting to think this might be wrong. $\endgroup$ – Jia Zhao Dec 14 '14 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.