11
$\begingroup$

What is the limit, as $n \to \infty$, of the expected distance between two points chosen uniformly at random within a unit edge-length hypercube in $\mathbb{R}^n$?

For $n=1$, the average distance is $\frac{1}{3}$. For $n=2$, it is approximately $0.52$. For $n=3$, approximately $0.66$ (Robbins' constant).

But I have not found an expression for arbitrary $n$...

$\endgroup$
2

2 Answers 2

9
$\begingroup$

The limit is $\infty$. See equation (2) of http://mathworld.wolfram.com/HypercubeLinePicking.html

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! This is somehow both obvious and counterintuitive. :-) $\endgroup$ Commented Apr 14, 2014 at 1:33
14
$\begingroup$

I think this easy probability argument, using the natural coupling, gives us the limit and the growth rate.

Let $\{U_i, V_i, i=1,2,\dots\}$ be iid uniform on $[0,1]$. Let $$D_n := \sqrt{(U_1 - V_1)^2 + \dots + (U_n - V_n)^2}$$ so that $E D_n$ is the expected distance between two independently and uniformly chosen points in $[0,1]^n$.

By the strong law of large numbers, $\frac{D_n^2}{n} \to E D_1^2 = \frac{1}{6}$ almost surely. Hence $\frac{D_n}{\sqrt{n}} \to \frac{1}{\sqrt{6}}$ almost surely. Moreover, since $E\frac{D_n^2}{n} = \frac{1}{6}$ for all $n$, $\frac{D_n}{\sqrt{n}}$ is bounded in $L^2$ and hence uniformly integrable. So we therefore have $$\frac{1}{\sqrt{n}} E D_n \to \frac{1}{\sqrt{6}}.$$ That is, $E D_n$ goes to infinity like $\sqrt{\frac{n}{6}}$.

$\endgroup$
4
  • $\begingroup$ Do you know the asymptotic variance of this distribution as $n \to \infty$? $\endgroup$
    – JeremyKun
    Commented Jan 26, 2016 at 1:36
  • $\begingroup$ The reason I ask is because when I run a simulation in 10,000 dimensions with 10,000 trials, the mean is very close to the correct mean (about 40.82), but the standard deviation is very close to 0.24. It is also almost exactly 0.24 when I run the same simulation for $n$ merely a thousand, or for $n$ a hundred thousand. It is surprising to me that the variance should be so close to 1/2 over many different orders of magnitude, but if I take your analysis at face value the variance should go to zero, no? $\endgroup$
    – JeremyKun
    Commented Jan 26, 2016 at 4:46
  • $\begingroup$ @JeremyKun: No, it doesn't have to go to zero. It depends on the lower order terms in $E D_n$. I don't know what those are. $\endgroup$ Commented Jan 26, 2016 at 5:10
  • $\begingroup$ @JeremyKun A bit late, but see math.stackexchange.com/questions/1976842/… and stats.stackexchange.com/questions/241504/… $\endgroup$ Commented Oct 27, 2016 at 22:09

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.