Limit of distance between two random points in a unit $n$-cube

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$...

• sciencedirect.com/science/article/pii/S0377042706004250 Apr 14 '14 at 0:59
• One way to see that the answer is $\infty$ is that with high probability, about $n/4$ of the coordinates will differ by at least $1/2$. Apr 14 '14 at 1:57

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

• Thanks! This is somehow both obvious and counterintuitive. :-) Apr 14 '14 at 1:33

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}}$.

• Do you know the asymptotic variance of this distribution as $n \to \infty$? Jan 26 '16 at 1:36
• 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? Jan 26 '16 at 4:46
• @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. Jan 26 '16 at 5:10
• @JeremyKun A bit late, but see math.stackexchange.com/questions/1976842/… and stats.stackexchange.com/questions/241504/… Oct 27 '16 at 22:09