# Lower bound on $P(X>\lambda)$ where $X$ is Gaussian.

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.

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

-
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$. – Dilip Sarwate Nov 25 '12 at 15:34
@DilipSarwate Isn't this exactly my point in the last paragraph? Or maybe I am confused... – Did Nov 25 '12 at 15:36
Yes, but I was wondering why you chose to find a limit first instead of just proving the bound directly. – Dilip Sarwate Nov 25 '12 at 15:38
I think our comments crossed in time. Yes, there is no limit in the last paragraph. – Dilip Sarwate Nov 25 '12 at 15:41
@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. – 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.

-
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. – Ivan Nov 25 '12 at 10:58
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. – Dilip Sarwate Nov 25 '12 at 12:58