= Solution
Apply <Markov's inequality> to the nonnegative <random variable> $e^{\lambda X}$, since $X>t$ implies $e^{\lambda X}>e^{\lambda t}$:
$$
\boxed{\mathbb P(X>t)\leq e^{-\lambda t}\mathbb E[e^{\lambda X}].}
$$
This <exponential Markov bound> remains true, though uninformative, when the <expected value> is infinite. For a <standard normal distribution>, completion of the square gives its <moment-generating function>
$$
\mathbb E[e^{\lambda X}]
=\frac1{\sqrt{2\pi}}\int_{\mathbb R}e^{\lambda x-x^2/2}\,dx
=e^{\lambda^2/2}.
$$
Minimize $\lambda^2/2-\lambda t$ over positive $\lambda$; the choice $\lambda=t$ gives the <Chernoff bound>
$$
\boxed{\mathbb P(X>t)\leq e^{-t^2/2}.}
$$
Back to article page
