2
$\begingroup$

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?

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.