17
$\begingroup$

If $f$ is a probability distribution on the unit disk in $\mathbb{R}^2$, and $X_1$ and $X_2$ are two independent samples from $f$, then what is the distribution $f^*$ that maximizes the average distance between these two samples, $E\|X_1-X_2\|$? Should all of the probability mass be distributed along the perimeter?

$\endgroup$
1
  • $\begingroup$ It would be interesting to consider this question with the disk replaced by other sets. $\endgroup$ Apr 14, 2014 at 16:32

2 Answers 2

19
$\begingroup$

The uniform distribution on the circle is optimal.

Every probability measure on the disc can be approximated by the sum of atomic measures with equal wieghts, that is, by measures of the form $\frac1n\sum_{i=1}^n \delta_{p_i}$ where $p_1,\dots,p_n$ are points in the disc. For such a measure, the average distance equals $\frac1{n^2}\sum_{i,j} |p_i-p_j|$. It suffices to show that for every $n$ and every collection of points $p_i$, this quantity is no greater than the average distance w.r.t. the uniform distribution on the circle.

Let us show that, for every fixed $n$, the maximum of the sum of pairwise distances $\sum_{i,j} |p_i-p_j|$ is attained when $p_i$'s are vertices of a regular $n$-gon insribed in the boundary circle. This implies the desired inequality.

First of all, the maximum exists by compactness. Then, since the distance is a convex function, the maximum is attained when all points are on the boundary. Now re-enumerate the points according to the cyclic order on the circle and split the sum into $\sum_i |p_i-p_{i+1}|$ (the sides), $\sum_i |p_i-p_{i+2}|$, etc.

For each fixed $k$, the sum $\sum_i |p_i-p_{i+k}|$ is maximized by a regular $n$-gon. Indeed, we have $p_i-p_{i+k}=2\sin(\alpha_i/2)$ where $\alpha_i$ is the angular measure of the arc between $p_i$ and $p_{i+k}$. So our sum equals $2\sum_i\sin(\alpha_i/2)$ where $0\le\alpha_i\le 2\pi$ and $\sum_i\alpha_i=2\pi k$. Since the function $t\mapsto\sin(t/2)$ is concave on $[0,2\pi]$, by Jensen's inequality the maximum is attained when all $\alpha_i$'s are equal, q.e.d.

$\endgroup$
2
$\begingroup$

the uniform distribution along the perimeter gives average distance $4/\pi$; a small perturbation of this distribution reduces the average distance, so this is at least a local optimum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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