10
$\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$
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks! This is somehow both obvious and counterintuitive. :-) $\endgroup$ – Joseph O'Rourke Apr 14 '14 at 1:33
13
$\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$
  • $\begingroup$ Do you know the asymptotic variance of this distribution as $n \to \infty$? $\endgroup$ – JeremyKun Jan 26 '16 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 Jan 26 '16 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$ – Nate Eldredge Jan 26 '16 at 5:10
  • $\begingroup$ @JeremyKun A bit late, but see math.stackexchange.com/questions/1976842/… and stats.stackexchange.com/questions/241504/… $\endgroup$ – S. Catterall Oct 27 '16 at 22:09

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.