7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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
  • 2
    $\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
  • 2
    $\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
  • 1
    $\begingroup$ @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. $\endgroup$ – shalop Nov 22 '17 at 9:26
  • 1
    $\begingroup$ By interpreting the integrals as Stieltjes integrals, this works for any distribution on the unit interval, or am I mistaken ? $\endgroup$ – Olivier Aug 7 '19 at 16:08

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.