I'm familiar with a "standard" bound on normal distribution in this form:
If $Z \sim \mathcal{N}(\mu, \sigma^2)$, then
$$
P(|Z – \mu| \geq t) \leq 2 \exp \left(\frac{-t^2}{2 \sigma^2} \right)
$$
though I don't recall seeing a proof of this (maybe someone knows?). But that's not the main problem.
In a larger proof I've encountered this:
We will use the tail bound
$$
P(Z \geq t) \leq \frac{\sigma}{\sqrt{2 \pi}} \exp \left(\frac{-t^2}{2 \sigma^2} \right)
$$
which I'm struggling to prove.
What I've tried:
If $X \sim \mathcal{N}(0, \sigma^2)$ then by definition of CDF:
$$
\Pr(X > t) = \int_{t}^{\infty} \frac{1}{\sigma^2 \sqrt{2 \pi}} \exp \left( \frac{-x^2}{2 \sigma^2} \right) \mathrm{d}x
$$
$$
= \frac{1}{\sigma^2 \sqrt{2 \pi}} \int_{t}^{\infty} \exp \left( \frac{-x^2}{2 \sigma^2} \right) \mathrm{d}x
$$
Now since $x \geq t$, we have $\frac{x}{t} \geq 1$ which we plug into the integral
$$
\leq \frac{1}{\sigma^2 \sqrt{2 \pi}} \int_{t}^{\infty} \frac{x}{t} \exp \left( \frac{-x^2}{2 \sigma^2} \right) \mathrm{d}x
$$
$$
= \frac{1}{\sigma^2 \sqrt{2 \pi}} \left( \frac{\sigma^2}{t} \exp \left( \frac{-t^2}{2 \sigma^2} \right) \right)
$$
which gives us this final bound
$$
\Pr(X > t) \leq \frac{1}{t \sqrt{2 \pi}} \exp \left( \frac{-t^2}{2 \sigma^2} \right)
$$
It looks close but it's not the same thing.
I've also tried Chernoff bounds but it got me nowhere near; just for the sake of curiosity (and sorry for using $t$ differently here)
Let $Z = (X − \mu)$, so $Z \sim \mathcal{N}(0, 1)$
$$
\Pr\left( Z \geq a \sigma \right) = \Pr(\exp(tZ) \geq \exp(t a \sigma))
$$
$$
\leq \frac{\mathbb{E}[ \exp(tZ)]}{\exp(t a \sigma)}
$$
now plug MGF
$$
= \frac{\exp \left( \frac{t^2 \sigma^2}{2} \right)}{\exp(t a \sigma)}
$$
$$
= \exp \left( \frac{t^2 \sigma^2}{2} – t a \sigma \right)
$$
$$
= \exp \left( \frac{t^2 \sigma^2 – 2t a \sigma}{2} \right)
$$
Since $t > 0$ can be arbitrary, we can do $t = a$ do get
$$
= \exp \left( \frac{a^2 \sigma^2- 2 a^2 \sigma}{2} \right)
$$
and here I gave up.
Any hints how the get the cited bound? Is it a "known" one?
Best Answer
The bound you cite is invalid as J.G. points out. But if $Z\sim N(0,\sigma^2),$ we have $$P(Z\geq t)\leq \frac{\sigma}{t\sqrt {2\pi}}\exp \left\{-\frac{t^2}{2\sigma^2}\right\},\quad\forall t>0.$$
Your proof using the integral would get you this inequality. You just had a small typo though (and should assume $t>0$):
$$\frac{1}{\sigma^2\sqrt{2\pi } }\exp \left\{-\frac{x^2}{2\sigma^2}\right\}$$ should be $$\frac{1}{\sigma\sqrt{2\pi } }\exp \left\{-\frac{x^2}{2\sigma^2}\right\}.$$