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