Maximum mean absolute difference of two iid random variables

Question

Suppose $X$ is any random variable taking values in $[0,1]$, and let $Y$ be an iid copy of $X$. What is the maximum possible value of $\mathbb{E}|X-Y|$, over all possible $X$'s?

I suspect that $\mathbb{E}|X-Y| \leq 1/2$ for any $X$, but I don't see an easy proof of this. The value $1/2$ is attained if $X$ has distribution Bernoulli(1/2), i.e. $\mathbb{P}(X = 0) = \mathbb{P}(X = 1) = 1/2$.

I can prove that $E|X-Y|^2 \leq 1/2$ for any iid variables $X$ and $Y$, as follows: just write

$\mathbb{E}|X-Y|^2 = EX^2 + EY^2 - 2E(XY) = 2(EX^2 - (EX)^2) \leq 2(EX - (EX)^2) \leq 1/2$,

since the quadratic $s(1-s)$ has maximum value $1/2$. (Here I used the fact that $X$ takes values in $[0,1]$ to bound $EX^2 \leq EX$.)

The bound on $\mathbb{E}|X-Y|^2$ is tight, again with $X$ having the Bernoulli(1/2) distribution.

(Edit 1) There is an easy way to get a bound of $\frac{1}{\sqrt{2}}$, using Jensen:

$\mathbb{E}|X-Y| \leq \sqrt{\mathbb{E}|X-Y|^2} \leq \frac{1}{\sqrt{2}}$,

since we showed above that $\mathbb{E}|X-Y|^2 \leq \frac{1}{2}$ always.

Edit: Thanks to @Sergei Golovan for a nice solution. I am now wondering if this can be generalized to other moments. Is it true that

$\mathbb{E}|X-Y|^\alpha \leq 1/2$ for all $\alpha > 0$?

As before, since a Bernoulli variable is 0-1 valued, it achieves the value 1/2. I don't think the given solution for $\alpha = 1$ will generalize. I wonder if there is a way to think about this using characteristic functions / moment generating functions of $|X-Y|$.

Answer 1

For a continuous distribution. Denote $F(x)$ the CFD of $X$ or $Y$. Then the expectation $$ \begin{aligned} \mathop{\mathbb E}|X-Y|&=\mathop{\mathbb E}(\max\{X,Y\}-\min\{X,Y\})\\ &=\int_0^1xdF^2(x)-\int_0^1xd(1-(1-F(x))^2)\\ &=2\int_0^1xF(x)dF(x)-2\int_0^1x(1-F(x))dF(x)\\ &=2\int_0^1x(2F(x)-1)dF(x)=\int_0^1xG(x)dG(x), \end{aligned} $$ where $G(x)=2F(x)-1$. Integrating by parts, we get $$ \begin{aligned} \int_0^1xG(x)dG(x)&=xG^2(x)\bigg|_0^1-\int_0^1G(x)d(xG(x))\\ &=1-\int_0^1xG(x)dG(x)-\int_0^1G^2(x)dx. \end{aligned} $$ Hence, $$ \mathop{\mathbb E}|X-Y|=\frac12-\frac12\int_0^1G^2(x)dx\le\frac12. $$

Answer 2

This proof applies in general to all random variables supported in $[0,1]$ . From the identity $|a-b|=a+b-2\min(a,b)$ we obtain that $$ \mathbb E|X-Y|=2\bigl(\mathbb EX-\mathbb E\min(X,Y)\bigr). $$ Thus by this formula and using $\mathbb P(\min(X,Y)>t)=\mathbb P(X>t)^2$ we have $$ \frac{\mathbb E|X-Y|}{2}= \int_0^1\mathbb P(X>t)-P(X>t)^2\ dt=\int_0^1\mathbb P(X>t)\cdot \mathbb P(X\leq t)\ dt\leq \frac{1}{4}, $$ since by AM-GM we have $$\mathbb P(X>t)\cdot \mathbb P(X\leq t)\leq \Bigl(\frac{\mathbb P(X>t)+ \mathbb P(X\leq t)}{2}\Bigr)^2=\frac 14.$$

---

A slight variant of the proof, might be considered more appealing depending on taste.

From the identity $$ |X-Y|=\int_0^1 1[X>t\geq Y]+1[Y>t\geq X]\ dt,\quad a.s. $$ it follows directly by Tonelli's Theorem that $$ \frac{\mathbb E|X-Y|}{2}=\int_0^1 \mathbb P(X>t)\cdot \mathbb P(X\leq t)\ dt\leq \frac{1}{4}. $$