# 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? Feb 18, 2017 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$$ Feb 18, 2017 at 5:58
• 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 Feb 18, 2017 at 13:29
• @JRichey No that's not correct. There are increasing functions where you don't get the function back when you integrate its derivative. For example, the Cantor function has zero derivative almost everywhere. If $F$ is an arbitrary increasing function, then you have to interpret dF/dx as a Borel measure. Nov 22, 2017 at 9:26
• By interpreting the integrals as Stieltjes integrals, this works for any distribution on the unit interval, or am I mistaken ? Aug 7, 2019 at 16:08

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