# Maximum mean absolute difference of two iid random variables

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

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.$$
• Thanks for your answer. I'm a bit confused though: actually, I've always been confused about this notation. What exactly does $\int x dF^2(x)$ mean? (Or the integral of something "d (some function)"?) I thought $\int d h(x) = \int h(x) dx.$ Could you explain the rules for computing with that notation? – J Richey Feb 18 '17 at 5:54
• @JRichey It is just $\int x\mathrm d u$ where $u=F^2(x)$. $$\int x \mathrm d(F^2(x)) = \int x\cdot \frac{\mathrm d F^2(x)}{\mathrm d x}\mathrm dx = \int x\cdot 2 F(x) \frac{\mathrm d F(x)}{\mathrm d x}~\mathrm d x$$ – Graham Kemp Feb 18 '17 at 5:58
• But if the measure corresponding to F is not absolutely continuous with respect to Lebesgue, then the Radon-Nikodym derivative $dF/dx$ doesn't make sense. Am I missing something? I also don't see how integration by parts makes sense in this context... – J Richey Feb 18 '17 at 5:59
• Any discrete distribution can be approximated arbitrarily closely by a continuous distribution so $\le \frac12$ is also true for discrete distributions, and in fact is strictly $\lt \frac12$ for continuous distributions – Henry Feb 18 '17 at 13:29