# Upper-bound on the sum of two dependent Gaussians.

Let $X$ and $Y$ be two dependent normally distributed continuous random variables (their marginals are $\mathcal{N}(0, 1)$). I would like to find an upper bound on the probability that one is greater than the other by a given threshold, i.e. find a $\theta$ such that $P(Y > X + \delta) < \theta$, $\delta, \theta \in \mathbb{R}$

If $X$ and $Y$ were independent it would be easy as I could directly compute their joint density, but in the case were they are allowed to be dependent all I could do is find a numerical solution by discretizing the joint density (which looked far from trivial).

-

If $X$ and $Y$ are jointly normal, $Y - X$ is normal with mean $0$ and variance $v = 2 - 2 \text{Cov}(X,Y)$, which can be anywhere from $0$ to $4$, and then $P(Y > X + \delta) = \Phi(-\delta/\sqrt{v})$, where $\Phi$ is the standard normal cdf.
If $X$ and $Y$ are not jointly normal, it's still true that $Y-X$ has mean $0$ and variance $v \in [0, 4]$. Now for any random variable $Z$ with mean $0$ and variance $v\le 4$, if $\delta > 0$ we have $$P(Z > \delta) \le \frac{v}{v + \delta^2} \le \frac{4}{4+\delta^2}$$
This comes from the fact that $$\frac{ (Z + v/\delta)^2}{(\delta + v/\delta)^2} \ge \cases{1 & if Z \ge \delta\cr 0 & otherwise\cr}$$ and $$E\left[\frac{(Z+v/\delta)^2}{(\delta+v/\delta)^2}\right] = \frac{ v + v^2/\delta^2}{(\delta+v/\delta)^2} = \frac{v}{v+\delta^2}$$
If $X$ and $Y$ are not jointly normal, I do not think it is true that $X - Y$ is jointly normal. For example, let $D$ be a -1,1 coinflip independent of $X$ and let $X$ be a standard normal random variable. Then $Z=XD$ is normally distributed, but $X - Z$ is not normally distributed (it takes on the value of zero with probability $\frac{1}{2}$). –  Chris Janjigian Mar 19 '12 at 0:43
I didn't mean to say $X-Y$ is normal. –  Robert Israel Mar 19 '12 at 1:01
Another bound: $$P(Y - X > \delta) \le P(Y > \delta/2) + P(X < -\delta/2) = 2 \Phi(-\delta/2)$$ This seems to be less than $4/(4+\delta^2)$ for all $\delta > 0$. –  Robert Israel Mar 19 '12 at 15:52