Upper bound of normal cdf

Random variable $$X\sim N(0,1)$$. Show that, $$P(X\geq c) \leq e^{-ct+ \frac{t^{2}}{2}}$$ for $$c>0$$ and for all $$t$$ in $$R$$.

I found that $$P(X\geq c) = \Phi(-c)$$ where $$\Phi(x)=\int_{-\infty}^{x}\phi(u)du$$ is the cdf of a standard normal variable.

I understand that the upper bound is in the form of mgf of normal distribution. How do I arrive at the above relation?

• What is $t$ in your inequality? Does it hold for all $t$? – gunes Apr 11 '19 at 11:26
• For all t. I have edited the question. – Harry Apr 11 '19 at 11:37
• did you understand my answer? – gunes Apr 11 '19 at 19:37
• Title should be "upper bound on gaussian complimentary CDF (aka survival function)". Your question is about concentration (i.e upper-bounding the survival function), not anti-concentration (i.e upper-bounding the CDF). – dohmatob Jan 27 '20 at 12:14

For any random variable $$X$$ with moment generating function $$M(t)$$ existing in an open interval enclosing $$t$$, say $$t\in(-h,h)$$, it is true that $$P(X\ge c)\le e^{-ct}M(t)\quad,\,\text{ if }0

This is because

\begin{align} M(t)=\int_{\mathbb R} e^{tx}\,dF(x)&\ge \int_c^\infty e^{tx}\,dF(x) \\&\ge e^{ct}\int_c^\infty \, dF(x)&,\text{ for }0

I am not sure if this holds for any $$t\in\mathbb R$$ in case $$X$$ is normal.

Interesting question. If it is for all $$t$$, then it must satisfy the worst case, i.e. $$t=c$$ which minimizes the exponent. Then the upper bound to prove becomes the following: $$P(X\geq c)\leq e^{-c^2/2}$$

From this post, we have the following inequality: $$P(X\geq c)\leq \frac{e^{-c^2/2}}{\sqrt{2\pi}c}$$ When $$c\geq \frac{1}{\sqrt{2\pi}}$$, the denominator will be larger than $$1$$, and RHS will be automatically smaller than $$e^{-c^2/2}$$.

When $$c\in [0,1/\sqrt{2\pi}]$$, $$e^{-c^2/2}\in [e^{-1/\pi},1]\approx[0.727,1]$$. And, trivially, we know that $$P(X\geq c)$$ cannot be larger than $$0.5$$.