Let $f(x)$ be a continuous probability distribution in the plane. It is obvious that if $X$ and $X'$ are two independent random samples from $f$, then $\mathbf{E}(\|X - X'\|) \leq 2 \mathbf{E}(\|X\|)$ by the triangle inequality. Can this upper bound be made tighter if we assume that $f$ is rotationally symmetric about the origin., i.e. $f(x) = g(\|x\|)$ for some function $g$?


Using the pareto distribution $f(x) = \frac{\alpha}{x^{\alpha+1}}$ ($x > 1$) , the ratio $\frac{E(||X-X'||)}{E(||X||)}$ approaches a $2$ as $\alpha$ tends to 1.

To find such a distribution, consider that all else equal, you want to maximize the difference $||X||-||X'||$ since the angle between the two is independent. This means that you want a distribution that extends to infinity as flatly as possible.

  • $\begingroup$ Simpler than a Pareto distribution is a Bernoulli distribution with $p \to 0.$ $\endgroup$ – Douglas Zare Aug 31 '12 at 21:25
  • $\begingroup$ So you'd get a mixture between a circle of radius R and a Dirac at 0. $E(||X||)$ would be $(1-p)R$ and $E(||X−X′||)$ would be $p(1−p)R+(1−p)^2 R 4/\pi$ thus $E(||X−X′||)/E(||X||)=p+(1−p)4/\pi$... Am I missing something? $\endgroup$ – Arthur B Aug 31 '12 at 21:54
  • $\begingroup$ By convention, the parameter $p$ is the chance that the Bernoulli random variable is $1$, not $0.$ The expected magnitude of $X$ is $p$. $E\|X-X'\| = 2p(1-p) + p^2 \frac 4 \pi.$ The ratio goes to $2$ as $p \to 0.$ $\endgroup$ – Douglas Zare Sep 2 '12 at 8:11
  • $\begingroup$ Ahh, I forgot the factor of $2$ in $2p(1−p)$... yes, that is much simpler. My first idea was to go with Bernoulli,s but I made the same stupid mistake and thought it didn't work. $\endgroup$ – Arthur B Sep 4 '12 at 13:39

The conditional expectation $$\eqalign{E[ \|X - X'\| | \|X\| = r, \|X'\| = s] &= \frac{1}{2\pi} \int_0^{2\pi} \sqrt{r^2 + s^2 - 2 r s \cos \theta}\ d\theta \cr &= \frac{2(r+s)}{\pi} EllipticE(2 \sqrt{rs}/(r+s))\cr}$$ where EllipticE is Maple's version of the complete elliptic integral of the second kind. Note that $0 < 2 \sqrt{rs}/(r+s) \le 1$, with $1$ occurring for $r=s$. On the interval $[0,1]$, $1 \le EllipticE(x) \le \pi/2$. Thus $$ \frac{4}{\pi} E[\|X\|] = \frac{2}{\pi} E[\|X\|+\|X'\|] \le E[\|X - X'\|] \le E[\|X\|+\|X'\|] = 2 E[\|X\|] $$

  • 4
    $\begingroup$ These are sharp as constants. If $\|X\|$ is constant, then $E\|X-X'\| = \frac{4}{\pi}E\|X\|.$ If $P(\|X\|/\|X'\| \in (1/r,r)$ is close to $0$, which is achievable as Arthur B points out, then $E\|X-X'\|$ is close to $2 E\|X\|.$ $\endgroup$ – Douglas Zare Aug 29 '12 at 20:37
  • $\begingroup$ Thanks! It doesn't appear that I can accept both answers, but I would if I could =/ $\endgroup$ – Charlie Aug 29 '12 at 22:46

Under the assumption that $f$ is radial, the angle between $X$ and $X'$ is uniformly distributed in $[0,\pi]$ (since the signed angle that each of $X$ and $X'$ makes with the $x$-axis is uniformly distributed by rotational invariance, hence so is their difference). Thus the distribution of $\|X-X'\|$ is the same as the distribution of $\| (r,0)-s e^{i\alpha}\|$ where $\alpha$ is an angle chosen uniformly at random, and $r, s$ are two independent samples of the distribution $g$ (on $[0,\infty)$). Its expectation thus equals (after a little calculation) $$ \pi^{-1}\int_0^\pi \int \int \sqrt{r^2+s^2-2rs\cos(\alpha)} g(r) g(s) dr ds d\alpha, $$ or $$ \pi^{-1}\int_0^\pi \int \int \sqrt{(r+s)^2-2rs(1+\cos(\alpha))} g(r) g(s) dr ds d\alpha. $$ I suppose you could get some bound in terms of $\mathbb{E}(\|X\|)$ from here which is better than $2\mathbb{E}(\|X\|)$, but there is a much more pleasant expression for the expectation of $\mathbb{E}\|X-X'\|^2$: as before, this is $$ \pi^{-1}\int_0^\pi \int \int r^2+s^2-2rs\cos(\alpha) g(r) g(s) dr ds d\alpha, $$ which can be readily evaluated to $2\mathbb{E}(\|X\|^2)-4\mathbb{E}(\|X\|^2)/\pi$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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