15 December 2011

Solution to distance between random points from a sphere

So I asked on Sunday the following question: pick two points on a unit sphere uniformly at random. What is the expected distance between them?

Without loss of generality we can fix one of the points to be (1, 0, 0). The other will be chosen uniformly at random and will be (X, Y, Z). The distance between the two points is therefore

√((1-X)2 + Y2 + Z2)

which does not look all that pleasant. But the point is on the sphere! So X2 + Y2 + Z2 = 1, and this can be rewritten as

√((1-X)2 + 1 - X2)

or after some simplification

√(2-2X).

But by a theorem of Archimedes (Wolfram Alpha calls it Archimedes' Hat-Box Theorem but I don't know if this name is standard), X is uniformly distributed on (-1, 1). Let U = 2-2X; U is uniformly distributed on (0, 4). The expectation of √(U) is therefore

04 (1/4) u1/2 du

and integrating gives 43/2/6 = 8/6 = 4/3.

(The commenter "inverno" got this.)

Of course it's not hard to simulate this in, say, R, if you know that the distribution of three independent standard normals is spherically symmetric, and so one way to simulate a random point on a sphere is to take a vector of three standard normals and normalize it to have unit length. This code does that:

xx1=rnorm(10^6,0,1); yy1=rnorm(10^6,0,1); zz1=rnorm(10^6,0,1)
d1=radic(xx1^2+yy1^2+zz1^2)
x1=xx1/d1;y1=yy1/d1;z1=zz1/d1;
xx2=rnorm(10^6,0,1); yy2=rnorm(10^6,0,1); zz2=rnorm(10^6,0,1)
d2=radic(xx2^2+yy2^2+zz2^2)
x2=xx2/d2;y2=yy2/d2;z2=zz2/d2;
d=radic((x1-x2)^2+(y1-y2)^2+(z1-z2)^2);

and then the output of mean(d), which contains the distances, is 1.333659; the histogram of the distances d is a right triangle. (The code doesn't make the assumption that one point is (1, 0, 0); that's a massive simplification if you want to do the problem analytically, but not nearly as important in simulation.)

7 comments:

Antoine said...

I'm confused. Say for simplicity that you're in 2D, on a circle. You say that X is uniformly distributed. Isn't the polar angle T uniformly distributed on [0,2pi]? Doesn't that mean that X = cos(T) is not uniformly distributed? Ie you have a higher probability to find X at poles.

Michael Lugo said...

The polar angle is not uniformly distributed. For example, look at a globe (not a map!); there is more area between 45 degrees north latitude and the equator than north of 45 degrees north. (The cosine of the polar angle is uniformly distributed -- Archimedes proved this, although it's not immediately obvious.)

Antoine said...

Ah, right, my bad. The situation is different in 2D and in 3D. So what about the average distance between two points on a n-sphere?

Michael Lugo said...

As n increases, points on the n-sphere get concentrated more and more around the equator. So the expected distance should approach the distance from the pole to any point on the equator, which is sqrt(2). But I don't know how quickly this limit is approached, or any other specific values.

FanfanTM said...

I believe the general answer for the n-sphere is
2^(n-1)/sqrt(pi)*gamma(n/2)^2/gamma(n-1/2)

FanfanTM said...

And this quantity tends to sqrt(2) approximately as sqrt(2)*(1-1/(8n))

Lava Kafle said...

wowowo god woow