Expected distance between points drawn from different distributions 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!
 A: Looking at the discrete nonnegative case, using your notation,
$$\sum_{i,j} (p_i-q_i)(p_j-q_j)|i-j| 
= -2 \sum_{i=0}^\infty \left( \sum_{j=0}^i p_j - \sum_{j=0}^i q_j\right)^2
\le 0,$$
where there are hopefully no convergence problems.
A: Take any real $p\ge0$. 
Assume that $E|X|^p+E|Y|^p<\infty$ and $0^0:=1$. For $p>2$, assume also that $EX=EY$. 
Let 
\begin{equation*}
 D_p:=2E|X-Y|^p-(E|X_1-X_2|^p+E|Y_1-Y_2|^p). 
\end{equation*}
The inequality in question can then be stated as $D_1\ge0$. 
Let us show, more generally, that 
\begin{equation}
 D_p\ge0\text{ for }p\in[0,2],\quad D_p\le0\text{ for }p\in[2,4]. \tag{1}
\end{equation}
By continuity, without loss of generality $p$ is not an integer. 
So, in the proof that follows let assume that $p\in(0,4)\setminus\{1,2,3\}$. 
Then, by formula (4) in [Positive-part moments via the Fourier-Laplace transform. J. Theoret. Probab. 24 (2011), no. 2, 409--421] or at \url{https://arxiv.org/abs/0902.4214}, 
\begin{equation*}
 E|Z|^p=EZ_+^p+E(-Z)_+^p
\end{equation*}
\begin{equation*} 
 =\frac{2\Gamma(p+1)}{\pi}\,\cos\frac{(p+1)\pi}2\,
 \int_0^\infty\frac{dt}{t^{p+1}}\Big(\Re h(t)
 -\sum_{j=0}^{\lfloor\ell/2\rfloor}\frac{(-1)^jt^{2j}}{(2j)!}\,EZ^{2j}\Big), 
\end{equation*}
where $Z$ is any random variable with $E|Z|^p<\infty$, $h$ is the characteristic function (c.f.) of $Z$, and $\ell:=\lceil p-1\rceil$. 
Since $p<4$, we have $\ell\le3$ and hence $\lfloor\ell/2\rfloor\le1$. 
Moreover, if $p<2$, then $\ell\le1$ and hence $\lfloor\ell/2\rfloor\le0$. 
Letting $f$ and $g$ denote the c.f.'s of $X$ and $Y$, respectively, we see that the c.f.'s of $X-Y, X_1-X_2,Y_1-Y_2$ are $f\bar g,|f|^2,|g|^2$, respectively. 
Note also that $D_0=0$. Also, $D_2=0$ in the case $p>2$, because in that case we assumed that $EX=EY$. It follows that 
\begin{equation*}
 D_p\overset{\text{sign}}=
 \cos\frac{(p+1)\pi}2\,
 \int_0^\infty\frac{\delta(t)dt}{t^{p+1}}
\end{equation*}
where $\overset{\text{sign}}=$ denotes the equality in sign and 
\begin{equation*}
\delta:= 2\Re(f\bar g)-|f|^2-|g|^2. 
\end{equation*}
Note that $\delta\le0$, since $2\Re(f\bar g)\le2|fg|\le|f|^2+|g|^2$. 
So, excluding the case when $D_p=0$, we conclude that 
\begin{equation*}
 D_p\overset{\text{sign}}=-\cos\frac{(p+1)\pi}2, 
\end{equation*}
which is the same as $(1)$. 
It also follows -- see e.g. The American Mathematical Monthly, Vol. 123, No. 5 (May 2016), pp. 491-496 or \url{https://arxiv.org/abs/1506.00537} --  that the inequality 
\begin{equation}
 2E\|X-Y\|\ge E\|X_1-X_2\|+E\|Y_1-Y_2\|
\end{equation}
holds, in particular, when $X$ and $Y$ are random vectors in a Euclidean space or in any two-dimensional normed space. 
A: 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}
