Suppose X is a 0 mean Gaussian random variable with variance 1. I'm trying to find a lower bound on $P(X>\lambda)$. Specifically I'd like to derive a lower bound of the form $c e^{-C\lambda^2}$ for positive constants $c,C$. I know there exists several upper bounds of this form. But I am looking for a lower bound.

  • 1
    $\begingroup$ See this answer for a method of developing both upper and lower bounds, though, unfortunately, they are not of the form $ce^{-C\lambda^2}$ but of the form $g(\lambda)e^{-\lambda^2/2}$ where $g(\cdot)$ is a rational function. $\endgroup$ – Dilip Sarwate Nov 13 '12 at 21:19

Using the change of variable $x=\lambda+t/\lambda$, one gets, for every positive $\lambda$, $$ \mathbb P(X\gt\lambda)=\frac1{\sqrt{2\pi}}\int_\lambda^{+\infty}\mathrm e^{-x^2/2}\mathrm dx=\frac1{\lambda\sqrt{2\pi}}\mathrm e^{-\lambda^2/2}\int_0^{+\infty}\mathrm e^{-t}\mathrm e^{-t^2/(2\lambda^2)}\mathrm dt. $$ When $\lambda\to\infty$, the very last exponential goes to $1$ hence the last integral converges to $1$ and $$ \lim_{\lambda\to+\infty}\sqrt{2\pi}\lambda\mathrm e^{\lambda^2/2} \mathbb P(X\gt\lambda)=1. $$ To get nonasymptotic bounds, one can use the fact that $\mathrm e^{-t^2/(2\lambda^2)}\geqslant\mathrm e^{-1/2}$ for every $t\leqslant\lambda$ and $\mathrm e^{-t^2/(2\lambda^2)}\leqslant1$ everywhere. This yields, for every positive $\lambda$, $$ \mathrm e^{-1/2}(1-\mathrm e^{-\lambda})\leqslant\sqrt{2\pi}\lambda\mathrm e^{\lambda^2/2} \mathbb P(X\gt\lambda)\leqslant1. $$

  • $\begingroup$ Perhaps you could point out that $e^{-t^2/2\lambda^2} < 1$ and so the last integral has value less than $1$ for every positive $\lambda$. So the limiting value $1$ is approached from below and we have the nonasymptotic bound $$\sqrt{2\pi}\lambda e^{\lambda^2/2}P(X>\lambda) < 1 ~~\text{for all}~\lambda > 0$$ instead of the limit value being $1$. $\endgroup$ – Dilip Sarwate Nov 25 '12 at 15:34
  • $\begingroup$ @DilipSarwate Isn't this exactly my point in the last paragraph? Or maybe I am confused... $\endgroup$ – Did Nov 25 '12 at 15:36
  • $\begingroup$ Yes, but I was wondering why you chose to find a limit first instead of just proving the bound directly. $\endgroup$ – Dilip Sarwate Nov 25 '12 at 15:38
  • $\begingroup$ I think our comments crossed in time. Yes, there is no limit in the last paragraph. $\endgroup$ – Dilip Sarwate Nov 25 '12 at 15:41
  • $\begingroup$ @Dilip Because these bounds alone do not imply the exact equivalent (since the prefactor $e^{-1/2}$ is (somewhat convenient but) off). Others do (for example, using the cut-off $t=\sqrt{\lambda}$ instead of $t=\lambda$) but not these ones. $\endgroup$ – Did Nov 25 '12 at 15:45

Let $Q(\alpha)$ denote $P\{X > \alpha\}$, the probability that a standard normal random variable exceeds $\alpha$. As shown in this answer, for $\alpha > 0$, $$ \frac{\exp(-\alpha^2/2)}{\sqrt{2\pi}} \left (\frac{1}{\alpha} - \frac{1}{\alpha^3}\right ) < Q(\alpha) < \frac{\exp(-\alpha^2/2)}{\alpha\sqrt{2\pi}} $$ which is not quite a bound of the desired form $c\exp(-C\alpha^2)$ where $c$ and $C$ are constants. But the result does indicate that no lower bound on $Q(\alpha)$ can have both $c$ a constant and $C = \frac{1}{2}$; $C$ must be larger than $\frac{1}{2}$. (Note that the answers provided by @did do have $C = \frac{1}{2}$ but are of the form $g(\alpha)\exp(-\alpha^2/2)$ where the $g(\alpha)$ are decreasing functions of $\alpha$.)

A weak bound of the desired form, with $c$ and $C$ both constants (but unfortunately with $C = 1$) can be obtained as follows.

Suppose that $X$ and $Y$ are independent standard normal random variables. Then, for $\alpha \geq 0$, $P\{|X| \leq \alpha,|Y| \leq \alpha\} = [1-2Q(\alpha)]^2$ where $Q(\alpha)$ is the complementary cumulative probability distribution function of the standard normal random variable. But this probability is the integral of the joint density of $X$ and $Y$ over the square region of side $2\alpha$ centered at the origin, and is bounded above by the integral over the circumscribed circle of radius $\sqrt{2}\alpha$. Thus, we have $$\begin{align*} P\{|X| \leq \alpha, |Y| \leq \alpha\} &= \int_{-\alpha}^{\alpha}\int_{-\alpha}^{\alpha} \frac{1}{2\pi}\exp[(-x^2-y^2)/2]\,\mathrm dx\,\mathrm dy\\ &\leq \int_{0}^{\sqrt{2}\alpha} \int_{0}^{2\pi}\frac{1}{2\pi}\exp(-r^2/2) \,r\mathrm d\theta \,\mathrm dr\\ &= 1 - \exp(-\alpha^2) ~~ \text{for} ~\alpha \geq 0. \end{align*}$$ giving $[1-2Q(\alpha)]^2 \leq 1 - \exp(-\alpha^2)$ for $\alpha \geq 0$, or, equivalently, $\exp(-\alpha^2) \leq 4Q(\alpha) - 4Q^2(\alpha)$. But, since $4Q^2(\alpha) > 0$ for all $\alpha$, we get that $$Q(\alpha) > \frac{1}{4}\exp(-\alpha^2) ~ \text{for}~ \alpha \geq 0$$ which is a lower bound of the form desired. But, as mentioned earlier, this is a very loose bound.

  • $\begingroup$ Dilip, may I please ask you to comment on this bound $1 - \Phi(t) \leq \frac{1}{2} \exp(-t^2/2)$, $t > 0$, which can be found in "Probability in Banach Spaces: Isoperimetry and Processes" by Ledoux and Talagrand; the authors refer to it as "the classical estimate". I was trying to prove/to find a proof but have not succeeded so far. Thank you. $\endgroup$ – Ivan Nov 25 '12 at 10:58
  • 1
    $\begingroup$ For $t>x>0$, $t+x>t-x>0$ and so $(t+x)(t-x)=t^2-x^2>(t-x)^2$. It follows that $\exp(-(t^2-x^2))<\exp(-(t-x)^2)$ and so $$\begin{align*}\exp(x^2/2)Q(x)&=\exp(x^2/2)\int_x^\infty(2\pi)^{-1/2}\exp(-t^2/2)\,dt\\&=\int_x^\infty(2\pi)^{-1/2}\exp(-(t^2-x^2)/2)\,dt\\&<\int_x^\infty(2\pi)^{-1/2}\exp(-(t-x)^2/2)\,dt\\&=\frac{1}{2}\end{align*}$$ and so $$Q(x)<\frac{1}{2}\exp(-x^2/2) ~~\text{for}~ x>0.$$ Since $Q(0)=\frac{1}{2}$, we have $$Q(x)\leq\frac{1}{2}\exp(-x^2/2)~~\text{for}~ x\geq 0$$ where equality holds at $x=0$. For small $x$, this is a better bound than the first one in my answer above. $\endgroup$ – Dilip Sarwate Nov 25 '12 at 12:58

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.