Let $X$ and $Y$ be independent random variables, with $X\_1,X\_2$ being independent copies of $X$ and $Y\_1,Y\_2$ being independent copies of $Y$. Then (is it true that) 


$2\mathbb{E}|X-Y|\geq\mathbb{E}|X\_1-X\_2|+\mathbb{E}|Y\_1-Y\_2|$?


This is saying that the expected distance between two points drawn from different distributions is greater than the expected distance between points drawn from one or the other.


My attempts so far include:


* *Triangle inequality* gives $4\mathbb{E}|X-Y|\geq\mathbb{E}|X\_1-X\_2|+\mathbb{E}|Y\_1-Y\_2|$ when we write $|X\_1-X\_2|=|(X\_1-Y\_1)+(Y\_1-X\_2)|$;
* *Squared distances* work, i.e. $2\mathbb{E}(X-Y)^2\geq\mathbb{E}(X\_1-X\_2)^2+\mathbb{E}(Y\_1-Y\_2)^2$ holds immediately after expanding the squares;
* *Counterexamples?* I have tried generating $X$, $Y$ from different distributions, e.g. normal, exponential, simple Bernoulli, etc. and haven't found anything. However, the inequality very much doesn't hold for $X$ and $Y$ dependent - a trivial example is $Y=X$, when the LHS is 0 while the RHS can be positive.
* *Discrete case* doesn't seem to shed much more light on it. The inequality reduces to $\sum\_{i,j} (p\_i-q\_i)(p\_j-q\_j)|i-j|\leq 0$, where $p\_i=\mathbb{P}(X=i)$ and $q\_i=\mathbb{P}(Y=i)$.


I have also thought of Jensen for $|x|, \sqrt{x},x^2$, Holder ($||fg||\_1\leq ||f||\_p||g||\_q$ for $1/p+1/q=1$), and Minkowski ($||f+g||\_p\leq||f||\_p+||g||\_p$ for $p\geq 1$).


I would appreciate any ideas/counterexamples/references for this.


Thanks!



Expected distance between points drawn from different distributions
This is the result of me trying to prove the identity in Brendan McKay's answer. Consider, a bit more generally, any nonnegative independent r.v.'s $X$ and $Y$, still with $X\_1,X\_2$ being independent copies of $X$ and $Y\_1,Y\_2$ being independent copies of $Y$. Then $P(X\wedge Y>x)=F(x)G(x)$ for all real $x$, where $F(x):=P(X>x)$ and $G(x):=P(Y>x)$. So, 
\begin{equation}
 E(X\wedge Y)=\int\_0^\infty dx\,P(X\wedge Y>x)
 =\int\_0^\infty dx\,F(x)G(x). 
\end{equation}
Similarly, $E(X\_1\wedge X\_2)=\int\_0^\infty dx\,F(x)^2$ and $E(Y\_1\wedge Y\_2)=\int\_0^\infty dx\,G(x)^2$. 
Note also that $|x-y|=x+y-2(x\wedge y)$ for real $x,y$. 
It follows that 
\begin{equation}
 2E|X-Y|-(E|X\_1-X\_2|+E|Y\_1-Y\_2|)
\end{equation}
\begin{equation} 
=-2\int\_0^\infty dx\,[2F(x)G(x)-(F(x)^2+G(x)^2)]
\end{equation}
\begin{equation} 
 =2\int\_0^\infty dx\,[F(x)-G(x)]^2\ge0. 
\end{equation}


