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

  • $\begingroup$ 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? $\endgroup$ – J Richey Feb 18 '17 at 5:54
  • $\begingroup$ @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 $$ $\endgroup$ – Graham Kemp Feb 18 '17 at 5:58
  • $\begingroup$ 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... $\endgroup$ – J Richey Feb 18 '17 at 5:59
  • $\begingroup$ The proof as it is works for continuous distributions (and for singular ones). For integrating by parts you can look at the Hewitt, Stromberg for the exact statement. $\endgroup$ – Sergei Golovan Feb 18 '17 at 6:10
  • $\begingroup$ 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 $\endgroup$ – Henry Feb 18 '17 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.