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.
Lower bound on P(X>\lambda) where $X$ is Gaussian.
-
1See [this answer](http://math.stackexchange.com/a/69417/15941) 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. – 2012-11-13
2 Answers
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. $
-
0@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. – 2012-11-25
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.
-
1For 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. – 2012-11-25