# can I get a bound on the probability of deviation, similar to Markov inequality?

I have two random variables $X$ and $Y$, both receiving values between 0 and 1.

I know that $E[X - Y] \ge 0$.

Can I get any inequality of the form:

$P(X - Y \ge \delta) \le F(\delta,X,Y)$

where $F(\delta,X,Y)$ is a (reasonable) function of $\delta$ and $E[X-Y]$?

Markov inequality would be good here, for example, by setting $F(\delta,X,Y) = E[X-Y]/\delta$. However, Markov inequality would require $X-Y \ge 0$, and I do not necessarily have that.

-

Since $0 \le X,Y \le 1$, you have $X-Y \ge -1$, so applying the Markov inequality to $X-Y+1$ gives $$P(X-Y \ge \delta) = P(X-Y+1 \ge \delta+1) \le (E[X-Y]+1)/(\delta+1)$$

Without any restrictions on the range of $X,Y$, no such bound is possible. For any numbers $\mu, \delta \in \mathbb{R}$, $p \in (0,1)$, there exists a random variable $Z$ (here $Z=X-Y$) with $P(Z \ge \delta) = p$ and $EZ = \mu$. Thus $p$ cannot be bounded by any function of $\mu$ and $\delta$.

For example, let $Z=a$ with probability $p$ and $Z=b$ with probability $1-p$. Then we have $\mu = EZ = pa + (1-p)b$, so $b = (\mu-pa)/(1-p)$. Since $b \to -\infty$ as $a \to \infty$, you can choose $a$ so large that $a > \delta$ and $b < \delta$, and then $P(Z \ge \delta) = p$.

-
I would like the bound to go to 0 as E[X-Y] goes to 0 as well, and it won't happen with this bound. I should have specified it explicitly when I wrote "reasonable", perhaps it was not clear. Any ideas about that? –  normvector Nov 20 '10 at 17:15
@piettre: as Yuval Filmus' example shows, this is impossible. –  Qiaochu Yuan Nov 20 '10 at 19:21

Nate's bound is optimal. Consider $X$ to be a fair coin toss and $Y = 1-X$. Then $EX=EY$ and $P(X-Y \geq 1) = 1/2$.

-

I would like the bound to go to 0 as E[X-Y] goes to 0 as well, and it won't happen with this bound. I should have specified it explicitly when I wrote "reasonable", perhaps it was not clear. Any ideas about that?

I don't think such a bound is possible. Consider $X,Y$ i.i.d uniform. $E[X-Y] = 0$ yet $P(X-Y \geq \delta) > 0$ for all $\delta < 1$.

-