Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
1  
@piettre: as Yuval Filmus' example shows, this is impossible. –  Qiaochu Yuan Nov 20 '10 at 19:21
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.