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?

  • 1
    $\begingroup$ What is $t$ in your inequality? Does it hold for all $t$? $\endgroup$ – gunes Apr 11 '19 at 11:26
  • $\begingroup$ For all t. I have edited the question. $\endgroup$ – Harry Apr 11 '19 at 11:37
  • $\begingroup$ did you understand my answer? $\endgroup$ – gunes Apr 11 '19 at 19:37
  • $\begingroup$ 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). $\endgroup$ – 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<t<h$$

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<t<h \\&=e^{ct}P(X\ge c) \end{align}

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$.


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.