27
$\begingroup$

Suppose $X$ and $Y$ are iid random variables taking values in $[0,1]$, and let $\alpha > 0$. What is the maximum possible value of $\mathbb{E}|X-Y|^\alpha$?

I have already asked this question for $\alpha = 1$ here: one can show that $\mathbb{E}|X-Y| \leq 1/2$ by integrating directly, and using some clever calculations. Basically, one has the useful identity $|X-Y| = \max{X,Y} - \min{X,Y}$, which allows a direct calculation. There is an easier argument to show $\mathbb{E}|X - Y|^2 \leq 1/2$. In both cases, the maximum is attained when the distribution is Bernoulli 1/2, i.e. $\mathbb{P}(X = 0) = \mathbb{P}(X = 1) = 1/2$. I suspect that this solution achieves the maximum for all $\alpha$ (it is always 1/2), but I have no ideas about how to try and prove this.

Edit 1: @Shalop points out an easy proof for $\alpha > 1$, using the case $\alpha = 1$. Since $|x-y|^\alpha \leq |x-y|$ when $\alpha > 1$ and $x,y \in [0,1]$,

$E|X-Y|^\alpha \leq E|X-Y| \leq 1/2$.

So it only remains to deal with the case when $\alpha \in (0,1)$.

$\endgroup$
  • $\begingroup$ Given two r.v.'s $X,Y$, we say that $X$ is greater than $Y$ in the convex order (denoted $X \succeq_c Y$) if $$Eg(x) \ge Eg(Y)$$ for all convex functions $g: \mathbf{R} \rightarrow \mathbf{R}$. The convex order is a partial order between r.v.s'. The convex order is closed under transformation by increasing convex functions: if $X \succeq_c Y$, then $g(X) \succeq_c g(Y)$ for any increasing convex function $g$. [...] $\endgroup$ – mlc Mar 30 '17 at 16:48
  • $\begingroup$ [...] Suppose you can prove that the r.v. $W=X-Y$ (when $X,Y$ are Bernoulli on $\{0,1\}$) is a maximal element in the convex partial order restricted to the class ${\cal S}$ of all r.v.'s generated by the difference of two i.i.d. r.v.'s. Then, by the closure property, $E|W|^a$ remains a maximal element in the class ${\cal S}$ for any increasing convex transformation. So $Eg(|X-Y|)$ is maximised in ${\cal S}$ for any increasing convex function $g(x)$, and in particular $g(x) = x^a$ for $a > 1$. $\endgroup$ – mlc Mar 30 '17 at 16:49
  • 2
    $\begingroup$ The fact that $X,Y \in [0,1]$ implies that $|X-Y|^p \leq |X-Y|$ for all $p \geq 1$. Hence $E[|X-Y|^p] \leq E[|X-Y|] \leq 1/2$ for all $p \geq 1$, so the maximizer is Bernoulli. If $p \in [0,1)$ it may be possible to find nontrivial maximizers. The best bound I can get via Jensen is: $E[|X-Y|^p] \leq E[|X-Y|]^p \leq 2^{-p}$. $\endgroup$ – Shalop Nov 22 '17 at 8:55
  • 2
    $\begingroup$ Actually, if the law of $X$ and $Y$ is atomless, then $|X-Y|^{\alpha} \to 1$ a.s. as $\alpha \to 0$. therefore by DCT $$\lim_{\alpha \to 0} E[|X-Y|^{\alpha}]=1$$which shows that the bound cannot be $1/2$ for very small $\alpha>0$. So, some nontrivial behavior is found in the regime of small $\alpha$. Maybe $2^{-\alpha}$ is optimal, as in the previous comment. $\endgroup$ – Shalop Nov 22 '17 at 10:06
  • 1
    $\begingroup$ @JRichey Yes, take $X,Y \sim U[0,1]$. You can do an easy integral to compute that $E[|X-Y|^{\alpha}] = \frac{2}{(\alpha+1)(\alpha+2)}$. So if you plug in $\alpha=\frac{1}{2}$, you get $E[|X-Y|^{1/2}]=\frac{8}{15}$. $\endgroup$ – Shalop Nov 28 '17 at 7:39
7
$\begingroup$

Throughout this answer, we will fix $\alpha \in (0, 1]$.

Let $\mathcal{M}$ denote the set of all finite signed Borel measures on $[0, 1]$ and $\mathcal{P} \subset \mathcal{M}$ denote the set of all Borel probability measure on $[0, 1]$. Also, define the pairing $\langle \cdot, \cdot \rangle$ on $\mathcal{M}$ by

$$ \forall \mu, \nu \in \mathcal{M}: \qquad \langle \mu, \nu\rangle = \int_{[0,1]^2} |x - y|^{\alpha} \, \mu(dx)\nu(dy). $$

We also write $I(\mu) = \langle \mu, \mu\rangle$. Then we prove the following claim.

Proposition. If $\mu \in \mathcal{P}$ satisfies $\langle \mu, \delta_{t} \rangle = \langle \mu, \delta_{s} \rangle$ for all $s, t \in [0, 1]$, then $$I(\mu) = \max\{ I(\nu) : \nu \in \mathcal{P}\}.$$

We defer the proof of the lemma to the end and first rejoice its consequence.

  • When $\alpha = 1$, it is easy to see that the choice $\mu_1 = \frac{1}{2}(\delta_0 + \delta_1)$ works.

  • When $\alpha \in (0, 1)$, we can focus on $\mu_{\alpha}(dx) = f_{\alpha}(x) \, dx$ where $f_{\alpha}$ is given by

$$ f_{\alpha}(x) = \frac{1}{\operatorname{B}(\frac{1-\alpha}{2},\frac{1-\alpha}{2})} \cdot \frac{1}{(x(1-x))^{\frac{1+\alpha}{2}}}, $$

Indeed, for $y \in [0, 1]$, apply the substitution $x = \cos^2(\theta/2)$ and $k = 2y-1$ to write

$$ \langle \mu_{\alpha}, \delta_y \rangle = \int_{0}^{1} |y - x|^{\alpha} f_{\alpha}(x) \, dx = \frac{1}{\operatorname{B}(\frac{1-\alpha}{2},\frac{1-\alpha}{2})}\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}} \left| \frac{\sin\theta - k}{\cos\theta} \right|^{\alpha} \, d\theta. $$

Then letting $\omega(t) = \operatorname{Leb}\left( \theta \in \left(-\frac{\pi}{2}, \frac{\pi}{2}\right) \ : \ \left| \frac{\sin\theta - k}{\cos\theta} \right| > t \right)$, we can check that this satisfies $\omega(t) = \pi - 2\arctan(t)$, which is independent of $k$ (and hence of $y$). Moreover,

$$ \langle \mu_{\alpha}, \delta_y \rangle = \frac{1}{\operatorname{B}(\frac{1-\alpha}{2},\frac{1-\alpha}{2})} \int_{0}^{\infty} \frac{2t^{\alpha}}{1+t^2} \, dt = \frac{\pi}{\operatorname{B}(\frac{1-\alpha}{2},\frac{1-\alpha}{2})\cos(\frac{\pi\alpha}{2})} $$

Integrating both sides over $\mu(dy)$, we know that this is also the value of $I(\mu_{\alpha})$.

So it follows that

\begin{align*} &\max \{ \mathbb{E} [ |X - Y|^{\alpha}] : X, Y \text{ i.i.d. and } \mathbb{P}(X \in [0, 1]) = 1 \} \\ &\hspace{1.5em} = \max_{\mu \in \mathcal{P}} I(\mu) = I(\mu_{\alpha}) = \frac{\pi}{\operatorname{B}(\frac{1-\alpha}{2},\frac{1-\alpha}{2})\cos(\frac{\pi\alpha}{2})}. \end{align*}

Notice that this also matches the numerical value of Kevin Costello as

$$ I(\mu_{1/2}) = \frac{\sqrt{2}\pi^{3/2}}{\Gamma\left(\frac{1}{4}\right)^2} \approx 0.59907011736779610372\cdots. $$

The following is the graph of $\alpha \mapsto I(\mu_{\alpha})$.

$\hspace{8em} $enter image description here


Proof of Proposition. We first prove the following lemma.

Lemma. If $\mu \in \mathcal{M}$ satisfies $\mu([0,1]) = 0$, then we have $I(\mu) \leq 0$.

Indeed, notice that there exists a constant $c > 0$ for which

$$ \forall x \in \mathbb{R}: \qquad |x|^{\alpha} = c\int_{0}^{\infty} \frac{1 - \cos (xt)}{t^{1+\alpha}} \, dt $$

holds. Indeed, this easily follows from the integrability of the integral and the substitution $|x|t \mapsto t$. So by the Tonelli's theorem, for any positive $\mu, \nu \in \mathcal{M}$,

\begin{align*} \langle \mu, \nu \rangle &= c\int_{0}^{\infty} \int_{[0,1]^2} \frac{1 - \cos ((x - y)t)}{t^{1+\alpha}} \, \mu(dx)\nu(dy)dt \\ &= c\int_{0}^{\infty} \frac{\hat{\mu}(0)\hat{\nu}(0) - \operatorname{Re}( \hat{\mu}(t)\overline{\hat{\nu}(t)} )}{t^{1+\alpha}} \, dt, \end{align*}

where $\hat{\mu}(t) = \int_{[0,1]} e^{itx} \, \mu(dx)$ is the Fourier transform of $\mu$. In particular, this shows that the right-hand side is integrable. So by linearity this relation extends to all pairs of $\mu, \nu$ in $\mathcal{M}$. So, if $\mu \in \mathcal{M}$ satisfies $\mu([0,1]) = 0$ then $\hat{\mu}(0) = 0$ and thus

$$ I(\mu) = -c\int_{0}^{\infty} \frac{|\hat{\mu}(t)|^2}{t^{1+\alpha}} \, dt \leq 0, $$

completing the proof of Lemma. ////

Let us return to the original proof. Let $m$ denote the common values of $\langle \mu, \delta_t\rangle$ for $t \in [0, 1]$. Then for any $\nu \in \mathcal{P}$

$$ \langle \mu, \nu \rangle = \int \left( \int_{[0,1]} |x - y|^{\alpha} \, \mu(dx) \right) \, \nu(dy) = \int \langle \mu, \delta_y \rangle \, \nu(dy) = m. $$

So it follows that

$$ \forall \nu \in \mathcal{P} : \qquad I(\nu) = I(\mu) + 2\underbrace{\langle \mu, \nu - \mu \rangle}_{=m-m = 0} + \underbrace{I(\nu - \mu)}_{\leq 0} \leq I(\mu) $$

as desired.

$\endgroup$
  • $\begingroup$ How do you know this is also the maximum over all distributions, not just distributions that have a density? And how did you get that solution? $\endgroup$ – J Richey Nov 29 '17 at 3:07
  • $\begingroup$ Right, I had guessed in one of the comments above that the correct answer should be Beta distributed, but I had no justification other than the idea that it should be symmetric about $1/2$, have smooth density, and converge weakly to Bernoulli(1/2) as $\alpha \to 1$. This seems like a good justification, even if it's still a bit informal. +1. $\endgroup$ – Shalop Nov 29 '17 at 3:31
  • $\begingroup$ Perhaps there are some information theory techniques that might apply here... $\endgroup$ – J Richey Nov 29 '17 at 3:46
  • 1
    $\begingroup$ I added the proof as promised. :) $\endgroup$ – Sangchul Lee Nov 29 '17 at 7:32
  • 1
    $\begingroup$ @JRichey, One idea is the variational method as in Kevin Costello's answer. This tells us that if $\mu$ is an 'interior maximum point', then it must satisfy $$\langle\mu,\delta_s\rangle=\text{constant}$$ as in Kevin Costello's answer. But instead of checking whether such interior maximum is possible, I took the logic backward by checking that this condition is enough to guarantee that $\mu$ is a maximum point. The other idea is the lemma, which I was motivated from my previous answer. $\endgroup$ – Sangchul Lee Dec 3 '17 at 14:12
3
+25
$\begingroup$

This isn't a full solution, but it's too long for a comment.

For fixed $0<\alpha<1$ we can get an approximate solution by considering the problem discretized to distributions that only take on values of the form $\frac{k}{n}$ for some reasonably large $n$. Then the problem becomes equivalent to $$\max_x x^T A x$$ where $A$ is the $(n+1) \times (n+1)$ matrix whose $(i,j)$ entry is $\left(\frac{|i-j|}{n}\right)^{\alpha}$, and the maximum is taken over all non-negative vectors summing to $1$.

If we further assume that there is a maximum where all entries of $x$ are non-zero, Lagrange multipliers implies that the optimal $x$ in this case is a solution to $$Ax=\lambda {\mathbb 1_{n+1}}$$ (where $1_{n+1}$ is the all ones vector), so we can just take $A^{-1} \mathbb{1_{n+1}}$ and rescale.

For $n=1000$ and $n=\frac{1}{2}$, this gives a maximum of approximately $0.5990$, with a vector whose first few entries are $(0.07382, 0.02756, 0.01603, 0.01143)$.


If the optimal $x$ has a density $f(x)$ that's positive everywhere, and we want to maximize $\int_0^1 \int_0^1 f(x) f(y) |x-y|^{\alpha}$ the density "should" (by analogue to the above, which can probably be made rigorous) satisfy $$\int_{0}^1 f(y) |x-y|^{\alpha} \, dy= \textrm{ constant independent of } x,$$ but I'm not familiar enough with integral transforms to know if there's a standard way of inverting this.

$\endgroup$
  • $\begingroup$ So, in the limit $n \to \infty$, supposedly one would obtain the true optimum. Is it possible to explicitly compute the limit of $A^{-1} 1$? $\endgroup$ – J Richey Nov 29 '17 at 1:47
  • $\begingroup$ Corrected. Thank you! $\endgroup$ – Kevin P. Costello Nov 29 '17 at 5:51
0
$\begingroup$

The following result has some bearing on the problem. It shows that the maximising distribution will be symmetrical and can be used to give an elementary proof in the case $\alpha=1$.

For any two real numbers $x$ and $y$ such that $0\leq y<x\leq\frac{1}{2}$ consider a random variable with distribution $$p(X=x)=p+a,p(X=y)=q+b,p(X=-x)=p-a,p(X=-y)=q-b,$$ for $p+q=\frac{1}{2}$.

Then $E[|X-Y|^{\alpha}]=(2x)^{\alpha}p^2+(2y)^{\alpha}q^2+((x+y)^{\alpha}+(x-y)^{\alpha})2pq-F(x,y)$ where $$F(x,y)=(2x)^{\alpha}a^2+((x+y)^{\alpha}-(x-y)^{\alpha})2ab+(2y)^{\alpha}b^2$$ For $\alpha\leq 1$, $(x+y)^{\alpha}-(x-y)^{\alpha}\leq2(xy)^{\frac{\alpha}{2}}$ and so the minimum value of $F(x,y)$ is $0$. This is attained when $a=b=0$ and then $$E[|X-Y|^{\alpha}]=(2x)^{\alpha}p^2+(2y)^{\alpha}q^2+((x+y)^{\alpha}+(x-y)^{\alpha})2pq.$$

The original distribution can, if necessary, be approximated as closely as one likes (in terms of the value of $E[|X-Y|^{\alpha}])$ by a discrete distribution and then one can look at the conditional value of the expectation when $X$ is restricted to pairs of values symmetrically placed about $x=\frac{1}{2}$.The above result can then be used to formally prove that the original distribution has to be symmetrical about $x=\frac{1}{2}$.

It is also straightforward to maximise $(2x)^{\alpha}p^2+(2y)^{\alpha}q^2+((x+y)^{\alpha}+(x-y)^{\alpha})2pq$ for $p+q=\frac{1}{2}$. When $\alpha=1$ this immediately gives $q=0$, giving another proof of the already known result in this case.

$\endgroup$
  • $\begingroup$ What are $a$ and $b$? Also, you should be clearer about shifting to $X \in [-1/2, 1/2]$, which is equivalent for $\alpha = 1$, but not for arbitrary $\alpha$! $\endgroup$ – J Richey Nov 28 '17 at 23:46
  • $\begingroup$ @JRichey It is equivalent for arbitrary $\alpha$ since $X-Y = (X-\frac{1}{2})-(Y-\frac{1}{2})$. $\endgroup$ – Shalop Nov 29 '17 at 1:59
  • $\begingroup$ @Shalop Does the absolute value mess that up? $\endgroup$ – J Richey Nov 29 '17 at 2:01
  • $\begingroup$ @JRichey No, of course not. Shifting never changes distances, even if distance is raised to $\alpha$ power. $\endgroup$ – Shalop Nov 29 '17 at 2:05
  • $\begingroup$ @Shalop Right, duh. I am on board. $\endgroup$ – J Richey Nov 29 '17 at 2:08
0
$\begingroup$

Experimentally, the distribution with pdf $12(x-\frac{1}{2})^2$ looks good for $\alpha=1/2$. This gives an expectation of $$\frac{18(\alpha^2+ \alpha+2)}{(\alpha+1)(\alpha+2)(\alpha+3)(\alpha+6)}.$$ For $\alpha$ close to 0 this is close to 1, and for $\alpha=1/2$, this is 264/455 or roughly 0.58.

Update: the pdf $$\left(\frac{1+\sqrt{2}}{4}\right) \left| \frac{1}{\sqrt{x}}- \frac{1}{\sqrt{1-x}} \right|$$ gives a better result for $\alpha=1/2$, namely 0.594. This suggests difficulties for numerical solutions, since the optimal distribution may have unbounded probabilities.

$\endgroup$
  • $\begingroup$ Probabilities are always bounded between $0$ and $1$, so I'm not sure what you mean. Simulations will certainly be difficult, since the optimization is over a function space, which is infinite dimensional! @KevinCostello gives a good idea about how to deal with this in his answer. $\endgroup$ – J Richey Nov 29 '17 at 0:26
  • $\begingroup$ Probabilities in the sense of the values of pdfs can be greater than 1. $\endgroup$ – Matt F. Nov 29 '17 at 0:51

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.