If $X$ and $Y$ independent and identically distributed, then $E(|X-Y|)\leq E(|X+Y|)$. Are other proofs of this known?

Question

I know a proof of the theorem that if $X$ and $Y$ independent and identically distributed, then $E(|X-Y|)\leq E(|X+Y|)$. The proof uses an integral representation of the absolute value, $$\int_0^\infty u^{-2}[1-\cos(au)]\,\mathrm{d}u = \mathrm{constant}\cdot|a|$$ I'm trying to find other proofs. Does anyone know another one?

Answer 1

Shorn of probabilistic language, this inequality follows from the assertion that $|x+y|-|x-y|$ is a positive semi-definite kernel, and is therefore the sum (or integral) of squares. Your Fourier-analytic argument gives one such sum-of-squares representation; here is a physical space one.

First observe the identity $$ |X+Y| - |X-Y| = 2\min(|X|, |Y|) \mathrm{sgn}(X) \mathrm{sgn}(Y)$$ (for instance, one can first check the case $0 \leq Y \leq X$, then observe that the identity is preserved under permutations and sign changes of $X,Y$). Thus by Fubini's theorem \begin{align*} {\bf E} (|X+Y|-|X-Y|) &= 2{\bf E} \min(|X|, |Y|) \mathrm{sgn}(X) \mathrm{sgn}(Y) \\ &= 2\int_0^\infty {\bf E} 1_{|X| \geq t} 1_{|Y| \geq t} \mathrm{sgn}(X) \mathrm{sgn}(Y)\ dt \\ &= 2\int_0^\infty |{\bf E} 1_{|X| \geq t} \mathrm{sgn}(X)|^2\ dt \\ &\geq 0. \end{align*}

This is assuming that $X,Y$ are real-valued. I'm not sure what happens in the complex (or vector-valued) case.

UPDATE: In the paper of Buja et al. referenced in Iosif's answer there is a standard trick to get from the real scalar case to the (real or complex) vector-valued case, which is to note that for any vector $X$, the magnitude $\| X \|$ is proportional to ${\bf E} |\langle X, u \rangle|$ where $u$ is a random unit vector. For instance, if $z$ is a complex number, then $|z| = \frac{\pi}{2} \int_0^1 |\mathrm{Re} z e^{-2\pi i \theta}|\ d\theta$. One can now derive the vector-valued inequality ${\bf E} \|X-Y\| \leq {\bf E} \|X+Y\|$ by applying the scalar inequality to obtain ${\bf E} |\langle X-Y, u \rangle| \leq {\bf E} |\langle X+Y, u \rangle|$ for every unit vector $u$ and then averaging.

Answer 2

It suffices to prove that for arbitrary $X_1,\ldots,X_n$ we have $$\sum_{i, j} |X_i-X_j|\leqslant \sum_{i, j} |X_i+X_j|, \quad \quad \quad (\star)$$ then applying $(\star)$ for a random sample from your distribution and taking the expectation you get what you need with extra term which is $O(1/n)$, so in the limit exactly what you need.

Proving $(\star)$ may be done by many ways, for example by induction: the base cases $n=0,n=1$ are easy, for $n>1$ you may replace all $X_i$'s by $X_i+t$ and optimise by $t$. The left hand side is not changed, the right hand side is piecewise linear, thus the minimum is attained when one of terms is 0,that means $X_i=-X_j$ (possibly with $i=j$). Then you may safely remove these $X_i, X_j$, and both left and right hand side are changed by the same value. So you may proceed by induction.

For $\sqrt{|X-Y|}$ and $\sqrt{|X+Y|}$ the inequality like $(\star)$ was proposed at IMO 2021. Above is a modified the most standard solution of this problem.

Answer 3

$\newcommand\R{\mathbb R}$In Theorem 2.3 of Buja, Logan, Reeds, and Shepp, it was shown by a modification of a method of Lévy (Lemma 2.2 by Buja etal, with a proof like that in another answer) that the function $\R^n\times\R^n\ni(x,y)\mapsto\|x+y\|_q^p-\|x-y\|_q^p$ is positive definite if $q\in[1,2]$ and $p\in(0,q]$, where $\|\cdot\|_q$ is the $q$-norm on $\R^n$. It follows that $$E\|X-Y\|_q^p\le E\|X+Y\|_q^p, \tag{2}\label{2}$$ for such $p$ and $q$, where $X$ and $Y$ are independent identically distributed (iid) random vectors in $\R^n$.

---

A one-line proof, $$E|X+Y|-E|X-Y|=2\int_0^\infty[P(X>r)-P(X<-r)]^2\,dr,$$ of \eqref{2} for $n=p=q=1$ was given on p. 74 of the paper by Lifshits, Schilling, and Tyurin, who also gave various generalizations of \eqref{2}, including the following: $$E\psi(X-Y)\le E\psi(X+Y), \tag{3}\label{3}$$ where $\psi\colon\R^n\to\R$ is any continuous negative definite function and $X$ and $Y$ are iid random vectors in $\R^n$. They also showed a connection with bifractional Brownian motion.

---

Corollary 5 states the following: For any two-dimensional normed space $V$ and any iid random vectors $X$ and $Y$ in $V$ we have $$E\|X−Y\|≤E\|X+Y\|.$$ This inequality is based on (an explicit version of) the well-known result by Lindenstrauss that any two-dimensional normed space can be isometrically imbedded into $L^1(0,1)$.

---

The inequality in the title of your post also admits the following generalization: $$E\|X-Y\|^p\le E\|X+Y\|^p,$$ for any $p\in(0,2]$, where $X$ and $Y$ are iid random vectors in a separable Hilbert space with norm $\|\cdot\|$.

This follows immediately from Corollary 2.2, which is a certain generalization of the integral representation of the absolute value in your post, and Theorem 4.1 in the same paper.

Answer 4

$\newcommand\R{\mathbb R}$Pinelis mentions the result $$E[\psi(X-Y)] \le E[\psi(X+Y)], \tag{3'}\label{3'}$$ where $\psi\colon\R^n\to\R$ is any continuous negative definite function and $X$ and $Y$ are i.i.d. random vectors in $\R^n$. This is a special case of a more general result: Let $X, Y, X', Y'$ be independent with $(X, Y)$ and $(X', Y')$ having the same law. Then $$E[\psi(X - X')] + E[\psi(Y - Y')] \le 2 E[\psi(X - Y)];\tag{4}\label{4}$$ this is just the definition of negative definite when $(X, Y)$ takes only finitely many values, and the general case follows by approximation. Apply this to $Y$ having the law of $-X$ to get \eqref{3'}.

Thus, \eqref{4} implies \eqref{3'}. The converse is not quite true. Gao proves that if \eqref{3'} holds and $\psi$ is continuous and polynomially bounded, then $\psi$ is negative definite, whence \eqref{4} holds. [2] also gives a counterexample where \eqref{3'} holds but $\psi$ is not negative definite (so \eqref{4} fails), namely, $\psi(x) := e^{\|x\|}$.

More generally, if $X, X', Y, Y'$ above have values in a separable premetric space $(M, d)$, then $(M, d)$ is said to have negative type if $$E[d(X,X')] + E[d(Y,Y')] \le 2 E[d(X,Y)].\tag{5}\label{5}$$ For \eqref{4}, we can use the premetric on $\R^n$ to be $d(x, y) := \psi(x-y) - \psi(0)$. Suppose that \eqref{5} holds and $E[d(X, x_0) + d(Y, x_0)]< \infty$ for some $x_0 \in M$. If equality in \eqref{5} holds iff $X$ and $Y$ have the same law, then we say $(M, d)$ has strong negative type. For sketches of four proofs that $\R^n$ has negative type with its usual metric and one proof of the equality condition, see Distance covariance in metric spaces, where it is also proved that Hilbert space has strong negative type. The equality condition is crucial for applications in statistics. Negative type metric spaces have a beautiful theory and have important applications in computer science; sometimes the theory is used in the form of a kernel and a reproducing kernel Hilbert space.

To understand the genesis of some of these ideas, note that \eqref{4} with $\psi(x) = \|x\|$ becomes trivial if $\psi(x) = \|x\|^2$ were used instead, in which case the equality condition becomes that $E[X] = E[Y]$. Schoenberg proved that negative type for a separable premetric space $(M, d)$ is equivalent to the existence of an isometric embedding of $(M, \sqrt{d})$ into Hilbert space; [3] gives a sketch of the proof. Whenever a semimetric $d$ has negative type, then $d^\alpha$ has strong negative type for all $\alpha \in (0, 1)$; see [3, Remark 3.19]. In particular, equality holds in \eqref{3'} for $\psi(x) = \|x\|^p$ ($0 < p < 2$) iff the law of $X$ is symmetric by reflection in the origin.