Let $Z$ be a standard normal random variable, prove:
$P(Z > z) \leq \frac{e^{-\frac{z^2}{2}}}{2}$
How do I approach this question? Do I assume the moment generating function (in Chernoff Bounds) is $e^{-\frac{z^2}{2}}$? Does it even have anything to do with moment generating function or I can just simply use something like Markov's inequality or Chebyshev's inequality to solve this?
Use the Chernoff bound. Since the mgf of standard normal random variable is $e^{t^2/2}$, we have
$$\begin{split}P(Z>z)&\le \frac{\mathbb E(e^{tZ})}{e^{tz}},\forall t\ge0\\ &=\frac{e^{\frac 12 t^2}}{e^{tz}}\\ &=e^{\frac 12 t^2-tz}\\ &=e^{\frac 12 (t^2-2tz+z^2)-\frac 12 z^2}\\ &=e^{\frac 12(t-z)^2-\frac 12z^2}\end{split}$$
Letting $t=z$, we get the lower bound:
$$P(Z>z)\le e^{-\frac 12z^2}$$
This doesn't have the factor of $1/2$ though, so maybe you require a stronger type of bound.
Define $f(x) = 1 - \Phi(x) - e^{-x^2/2}/2$, where $\Phi(x)$ is the standard normal cdf. Then $$ f'(x) = e^{-x^2/2} \left(-\frac1{\sqrt{2\pi}} +\frac{x}2 \right), $$ so $f$ decreases for $x< \sqrt{2/\pi}$ and increases for $x>\sqrt{2/\pi}$. Since $f(0) = f(+\infty) = 0$, it follows that $f(x) <0$ for $x>0$.
For $x>\sqrt{2/\pi}$, one can also use the standard estimate $1-\Phi(x) < \phi(x)/x$, which is even better.
