Author |
Topic: random points on a sphere (Read 10012 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
random points on a sphere
« on: Aug 14th, 2004, 3:47pm » |
 Quote  Modify
|
What is the most likely distance between two randomly selected points on a sphere?
J CK
PS. With 'distance' I mean the 3D Euclidean distance (the distance along the straight line through the sphere). So the most likely distance aksed for is a non-negative real number not exceeding the diameter of the sphere.
PPS. a 'randomly selected point' should be interpreted such that equal surface areas on the sphere have the same chance of containing this randomly selected point.
|
|
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: random points on a sphere
« Reply #1 on: Aug 14th, 2004, 6:14pm » |
Quote Modify
|
I'm assuming you are not looking for the average distance.
::Calling the first point a 'pole' of the sphere, it seems logical to me that the second point would on average lie on the 'equator' of the sphere.
Then by Pythagoras, Distance = (r2+r2)1/2. ::
|
| « Last Edit: Aug 14th, 2004, 6:24pm by honkyboy » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: random points on a sphere
« Reply #2 on: Aug 15th, 2004, 12:37am » |
Quote Modify
|
Sorry, but not correct.... I'm indeed looking for the most likely distance, which need not be the expectation value for the distance.
JCK
|
| « Last Edit: Aug 15th, 2004, 12:39am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: random points on a sphere
« Reply #3 on: Aug 15th, 2004, 1:54am » |
Quote Modify
|
The solution:
::
If you consider the first point chosen as the north pole of the sphere, the the locii of points equidistant from it form the lines of latitude. The most likely latitude to find the second point at is the longest, namely the equator. So the answer is indeed 21/2r, though for a slightly different reason than honkyboy suggested
::
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: random points on a sphere
« Reply #4 on: Aug 15th, 2004, 5:39am » |
Quote Modify
|
That was my first thought as well. However, treating it a bit more carefully gives a surprising result:
Let [theta] be the angle between the two points:
The distribution function for [theta] is given by the (relative) area of the spherical cap:
1/4[pi]r2 [int]t=0[theta] [int]p=02[pi] r2sin t dp dt = (1 - cos[theta])/2.
The distance between two points an angle [theta] apart is d([theta]) = r[2(1-cos[theta])]1/2, or cos[theta] = 1-(d/r)2/2.
Since d is monotone, its distribution function is simply (1-cos[theta])/2 evaluated when d([theta]) = d, which gives (d/r)2/4. The density of d is the derivative of that, d/2r2, which is maximum at d=2r.
Another way to look at it:
Given the density function of [theta], we must divide by d'([theta]) = rsin[theta]/d to get the density of d, so the most likely value of d doesn't coincide with the most likely value of [theta].
|
| « Last Edit: Aug 16th, 2004, 12:48pm by Eigenray » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: random points on a sphere
« Reply #5 on: Aug 15th, 2004, 6:04am » |
Quote Modify
|
That is correct Eigenray! :: Indeed: the most likely distance between two randomly chosen points on a sphere is equal to the diameter of the sphere. ::
The same holds for a circle. For hyperspheres in higher dimensions, this breaks down, however. Anyone who would like to try the limit N [to] [infty] for the most likely distance between randomly chosen points on hyperspheres in N dimensions?
JCK
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: random points on a sphere
« Reply #6 on: Aug 15th, 2004, 10:37am » |
Quote Modify
|
JocK,
in your original post you have defined 'distance' and 'randomly selected point', but you have not defined 'most likely'.
As the 2d measure of a set of points yielding any particular distance is 0, all distances are equally likely.
As the 1d measure of a set of points yielding a particular distance reaches max at the equator, the answer is
r[sqrt]2.
How do you define the notion of maximum likelyhood in order to arrive at your intended answer?
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: random points on a sphere
« Reply #7 on: Aug 15th, 2004, 11:05am » |
Quote Modify
|
on Aug 15th, 2004, 10:37am, Leonid Broukhis wrote:| How do you define the notion of maximum likelyhood in order to arrive at your intended answer? |
|
Don't make things too complicated! 
'Most likely distance' should be interpreted in the common way: the distance d for which the probability distribution P(x) peaks at it's maximum value:
P(d) > P(x) for all x [ne] d that satisfy 0 [le] x [le] 2r.
No special measures! So P(x) dx simply is the probability to find distances d that satisfy x < d < x+dx.
JCK
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: random points on a sphere
« Reply #8 on: Aug 15th, 2004, 2:52pm » |
Quote Modify
|
 Help. With a given point on a sphere, there is only one specific point on the sphere that is a distance of 2r away from it. Is it not least likely that these points would be randomly chosen, with a probability infinitely close to zero.
With an infinite number of points on a sphere, isn't the probablility of any distance resulting infinitely close to zero. Some just infinitly closer that others.
What is wrong with my thinking? (sorry, my background in mathematics is relatively limited)
|
| « Last Edit: Aug 15th, 2004, 3:10pm by honkyboy » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: random points on a sphere
« Reply #9 on: Aug 16th, 2004, 8:48am » |
Quote Modify
|
on Aug 15th, 2004, 5:39am, Eigenray wrote:area of the spherical cap:
1/4[pi]r2 [int]t=0[theta] [int]p=02[pi] r2sin p dp dt |
|
I may be a little rusty on calculus (and I never liked it much) but doesn't that integral evaluate to 0?
Later in the working, allowing for the answer to the integral being correct, even if the integral wasn't, I get P(d)=d/2r2, which still doesn't alter the final conclusion.
I'm still not terribly happy with the answer - while I'm prepared to concede that the maths (once the errors are corrected) is impeccable, it is intuitively very dissatisfying.
As a final observation, if you take spherical distance (distance along the surface or the sphere) rather than spatial distance, you do get the points on the equator as lying at the most probable distance
|
| « Last Edit: Aug 16th, 2004, 8:51am by rmsgrey » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: random points on a sphere
« Reply #10 on: Aug 16th, 2004, 9:03am » |
Quote Modify
|
on Aug 15th, 2004, 2:52pm, honkyboy wrote: Help. With a given point on a sphere, there is only one specific point on the sphere that is a distance of 2r away from it. Is it not least likely that these points would be randomly chosen, with a probability infinitely close to zero.
With an infinite number of points on a sphere, isn't the probablility of any distance resulting infinitely close to zero. Some just infinitly closer that others.
What is wrong with my thinking? (sorry, my background in mathematics is relatively limited) |
|
Since the probability of choosing any given point, or even a point lying on any given line is 0, the probability of picking a given distance is calculated based on the area of the sphere where the points are within a certain fixed (arbitrarily small) error of the distance in question. The way to think about it is as a pair of concentric spheres or nearly the same radius, both centred at the north pole of the original sphere. The aim is to find the pair of spheres (with a given fixed difference between their radii) that have the largest strip of the original sphere trapped between them. It works out that that's always the pair where the largest has radius equal to the diameter of the original sphere - so just touches the south pole. As the gap between the two spheres shrinks, the average radius tends to 2r, so the limit is the distance 2r...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: random points on a sphere
« Reply #11 on: Aug 16th, 2004, 1:11pm » |
Quote Modify
|
on Aug 16th, 2004, 8:48am, rmsgrey wrote:
I may be a little rusty on calculus (and I never liked it much) but doesn't that integral evaluate to 0? |
|
That should have been a sin(t) in there; dA = r2sin t d[phi]dt (p=[phi] is the "longitude", t is the angle from the pole).
Quote:| Later in the working, allowing for the answer to the integral being correct, even if the integral wasn't, I get P(d)=d/2r2, which still doesn't alter the final conclusion. |
|
Right. I kind of threw the r term in at the last minute instead of taking it to be 1.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: random points on a sphere
« Reply #12 on: Aug 16th, 2004, 1:17pm » |
Quote Modify
|
on Aug 15th, 2004, 2:52pm, honkyboy wrote: Help. With a given point on a sphere, there is only one specific point on the sphere that is a distance of 2r away from it. Is it not least likely that these points would be randomly chosen, with a probability infinitely close to zero.
With an infinite number of points on a sphere, isn't the probablility of any distance resulting infinitely close to zero. Some just infinitly closer that others.
|
|
The probability of observing any particular distance is indeed zero. You fix one point on a sphere, let's say at the "north pole". Then you fix the distance between that first point and the second point. Then the second point can be any of a ring of points away from the pole. As that distance gets larger, the circumference of the ring increases. Then later, it decreases. But regardless, the probability of the second point lying in that ring, for any length ring, is still zero, since the dimensionality of the sample space (the sphere) is larger. So the problem as originally phrased is meaningless, I think.
Perhaps the right way to phrase it is, "What is the maximum likelihood estimate (MLE) of the distance between two randomly selected points on the sphere?" This says, find the distance for which the probability *density* function is maximized. Rather than thinking of a ring, we expand the ring by a small width dx and think of a ribbon, a strip of paper wrapped around the sphere with some thickness dx. Then we can derive a density function f(x) such that " f(x) * dx " is the probability of falling in that width-dx strip. Note that the density function is not necessarily bounded between 0 and 1 and thus for a particular x you are not getting a probability value. It is only after you multiply by the ribbon width that you get a probability.
I'm not 1337 enough to be unafraid of spherical coordinates. Instead, I first compute the cumulative disribution function
F(x) = Pr(X <= x)
which is simply the surface area of a spherical cap such that the length of the cord connecting the pole to the cap's rim is x. Then take the derivative of that with respect to x, and you get the density function:
f(x) dx = Pr(X = x) dx
I use the fact that the surface area of a cap is
2[pi]Rh = [pi](r12 + h2) = [pi]x2
Since the CDF should be normalized to range from 0 to 1, we have
F(x) = [pi]x2 / (4[pi]R2) = x2 / (4R2)
Then the density function f(x) is
f(x) = x/(2R2)
which is monotonically increasing in terms of x. Thus it is maximized when x is the most it can be, which is twice the radius:
MLE = argmax f(x) = 2R
This result feels counterintuitive due to the following thoughts: My immediate guess when seeing this problem was sqrt(2)*R, and the logic is this: if we just go back to thinking about the rings, then the length of a ring should be some indication of the probability density. And the length of the ring is maximized at the equator, where it is 2*pi*R. When x = 2r, the ring becomes a mere point.
Even when we think of ribbons instead of rings, it doens't make sense to me. The ribbon width dx should always be parallel to h, the variable which runs along the diameter connecting one pole to the other. (Do you believe this? Hmm.) So as we go further beyond the equator into the second hemisphere, the circumference of the ribbon gets smaller, but the thickness of the ribbon gets larger. So there is some tradeoff going on and perhaps the area could be maximized at the cap. But then there is a ribbon of equal area at the point we started from, in the first hemisphere! Then there should be two answers of equal density.
In fact, by symmetry alone, can't we argue that if the maximum likelihood estimate is not R[sqrt](2), then there must be two answers?
I'm still backtracking my work, praying for an error! 
Something else I was thinking about, just as an aside: Sometimes the most likely outcome never happens. For instance, consider flipping a coin n times, where the probability of heads is 0.9 and n is very very large. Then the most likely result is all heads, which occurs with probabilty (0.9)n. However, as n[to][infty], the probability of observing such a fantastic outcome of n consecutive heads is zero -- even though it is the most probable outcome.* However, this still doesn't explain why there is not a symmetric result in the first hemisphere; also there is no repeated drawing going here anyways.
Footnote: *What we can say though about likely long-term behavior is that as n[to][infty], 90% of the flips will be heads, and 10% of the flips will be tails. Thus coin sequences whose heads:tails ratios are [epsilon] away from this ratio fall into the [epsilon]-typical set of outcomes; by the law of large numbers, the probability of falling into this set approaches 1.
[edit] Corrected a normalization error in my CDF expression and resulting PDF expression; thanks Jock
|
| « Last Edit: Aug 16th, 2004, 2:17pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: random points on a sphere
« Reply #13 on: Aug 16th, 2004, 1:41pm » |
Quote Modify
|
Folks,
sorry if it is against your intuition, but as correctly stated by Eigenray: the probability density P(x) = x/(2r[sup2]). [As stated earlier in this thread, such a probability density should be interpreted as: the probability of finding two random points at a distance between x and x+dx is P(x) dx = x dx/(2r[sup2]).]
P(x) is a monotonically increasing function and therefore on the interval [0, 2r] reaches a maximum for x = 2r.
For those who still doubt: calculate the surface area of the spherical cap defined by all points at a distance x from the North pole with 1.98 r < x < 2 r, and compare this with the area of the sperical ring defined by all points at a distance x from the North pole with ([sqrt]2 - 0.01) r < x < ([sqrt]2 + 0.01) r. Which area is bigger?
JCK
|
| « Last Edit: Aug 16th, 2004, 1:59pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: random points on a sphere
« Reply #14 on: Aug 16th, 2004, 2:11pm » |
Quote Modify
|
on Aug 16th, 2004, 1:17pm, william wu wrote:
<..> the surface area of a cap is
2[pi]Rh = [pi](r12 + h2) = [pi]x2
Then the density function f(x) is
f(x) = 2[pi]x
<..>
Looks like my density doesn't match everyone else's; maybe I made an error. |
|
Yep, u forgot to divide by 4[pi]R2 when going from area to cumulative probability...
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: random points on a sphere
« Reply #15 on: Aug 16th, 2004, 2:14pm » |
Quote Modify
|
Ah right, CDF must be bounded between 0 and 1. Thanks that fixes it.
on Aug 16th, 2004, 1:41pm, JocK wrote:For those who still doubt: calculate the surface area of the spherical cap defined by all points at a distance x from the North pole with 1.98 r < x < 2 r, and compare this with the area of the sperical ring defined by all points at a distance x from the North pole with ([sqrt]2 - 0.01) r < x < ([sqrt]2 + 0.01) r. Which area is bigger?
JCK |
|
But how do you explain the fact that the surface area of the spherical cap defined by all points at a distance x from the North pole with 0 < x< 0.02r is identical, and yet x = 0 is not an equivalent MLE?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Fresno_Bob
Newbie
Gender:
Posts: 13
|
|
Re: random points on a sphere
« Reply #16 on: Aug 16th, 2004, 2:43pm » |
Quote Modify
|
The two caps 0 < x < 0.02r and 1.98r < x < 2r do not have the same area.
Consider walking 1 mile (north/south). Your distance from the North Pole would change by about 1 mile if you're at the North Pole, about 0.7 mile if you're at the equator, and about 0 if you're at the South Pole. It's a lot further from the South Pole to a point where x=1.98r than it is from the North Pole to a point where x=0.02r.
the ring arguments should tell you that the equator is the most likely angle, not the most likely distance.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: random points on a sphere
« Reply #17 on: Aug 16th, 2004, 2:59pm » |
Quote Modify
|
There is only one point that's 2r from a giving starting point, surely any other distance (except 0) should be more likely, as there are many more points in a circle..
Also, for a given angle the distance is uniquely determined, so the most likely angle goes together with the most likely distance, doesn't it?
|
| « Last Edit: Aug 16th, 2004, 3:01pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: random points on a sphere
« Reply #18 on: Aug 16th, 2004, 9:45pm » |
Quote Modify
|
Try thinking about it this way:
Let T be the angle between the two points, and D=D(T)=r sqrt(2(1-cosT)) be the (straight line) distance, with densities fT(t) and fD(d). Then
2[delta]fT(t) ~ Pr(|T-t| < [delta]) ~ Pr(|D-d| < [epsilon]) ~ 2[epsilon]fD(d),
when [epsilon]/[delta] ~ D'(t).
So fD(d) = fT(t)/D'(t), so there's no reason to expect both densities to be maximized at the same time.
In this case we have fD(d) = [sin(t)/2]/[r2sin(t)/d] = d/(2r2).
Consider, what is the "most likely" value of x2, when x is chosen uniformly from [0,1]?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: random points on a sphere
« Reply #19 on: Aug 17th, 2004, 6:47am » |
Quote Modify
|
For those still struggling with the concept of North and South poles not being equivalent, consider the locus at distance r from the North pole, which has latitude 30N. The area above that covers distances [0,r) while the remainder of the sphere covers distances (r,2r]. Equally, the equator is at distance 20.5 which is decidedly not the average of the two poles' distances.
As far as relative likelihood of angles and distances goes, distance varies non-linearly with angle, so while the probability of getting a given distance is the same as getting the equivalent angle, the probability of getting within epsilon>0 of a general distance is not the same as getting within delta of the corresponding angle regardless of choice of delta.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: random points on a sphere
« Reply #20 on: Aug 19th, 2004, 4:12am » |
Quote Modify
|
Yeah, it makes sense to me now. A tricky result! Thanks for the nice explanations guys. If anyone's still puzzled, here's another explanation -- which basically echoes what has already been said, but in my own words:
Let d denote the length of the chord connecting the north pole to the second point which is somewhere on the sphere's surface. Let [theta] be the angle between the chord and the diametric line connecting north and south poles. Now consider fixing some amount of change [smiley=bigtriangleup.gif]x in d.
Then when d is small (< R[sqrt]2), one doesn't have to vary [theta] much to change the chord length by [smiley=bigtriangleup.gif]x; consequently, the surface area of the zone swept by this chord movement is small. (A zone is a band on the sphere's surface, like a paper strip wrapped around a ball.)
However, when d is large and the second point is in the lower hemisphere, one must vary [theta] much more to change the chord length by the same amount [smiley=bigtriangleup.gif]x. This is because the curvature of the sphere in the lower hemisphere is getting flatter from the chord's perspective. Hence the zone swept by this chord movement has relatively large surface area.
|
| « Last Edit: Aug 19th, 2004, 6:26am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: random points on a sphere
« Reply #21 on: Aug 21st, 2004, 3:28pm » |
Quote Modify
|
So, if I look for a lost friend that could be anywhere on Earth, the distance to him is most likely to be one Earth diameter, so I should start to search in Australia? (I live in Switzerland).
 (enjoying the desperate looks)
|
| « Last Edit: Aug 23rd, 2004, 9:58am by Grimbal » |
IP Logged |
|
|
|
honkyboy
Junior Member
Gender:
Posts: 101
|
|
Re: random points on a sphere
« Reply #22 on: Aug 21st, 2004, 7:06pm » |
Quote Modify
|
Yep, I once had a girlfriend who moved to Austrailia. I figured that she was trying to get as far away from me as possible. I sure am relieved to know that's just the most likely place she'd move to.
P.S. Big thanks to all who helped out explaining this problem. Seems simple to me now. I never realized that without a stated way to interpret what a 'randomly selected point' is, the problem doesn't have a clear solution. Jock clearly stated how to interpret this in the problem statement. I ignored it.
Yep, I once had a girlfriend who told me that I jumped to conclusions and didn't listen . . .
|
|
IP Logged |
|
|
|
Rejeev
Newbie
Gender:
Posts: 31
|
|
Re: random points on a sphere
« Reply #23 on: Oct 8th, 2004, 2:16am » |
Quote Modify
|
relative to first point, probability for each distance depends on two things
1) Area of the ring at that distance ( propotional to the radius of the ring)
2) angle of the ring surface makes with line between ring and the first point (component of area perpenticular to the line from ring to first point)
Let A be the angle between the line from ring to centre of sphere and line from ring to first point.
Then radius (this area) propotional to sinA.
Vertical componet propotional to cosA
probability is maximum where sinAcosA is maximum
I am not sure if this solution is matching with Eigenray's solution.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: random points on a sphere
« Reply #24 on: Oct 8th, 2004, 2:47am » |
Quote Modify
|
I think you'll find that that's wrong. The angle A goes from a right angle at the north pole (the first point) to 0 at the south pole, meaning that, were sinA correct, the ring of largest radius would be the degenerate ring at the north pole rather than the equator. The correct value appears to be sin2A, giving correct ring sizes.
cosA is proportional to the euclidean distance from the north pole to the given ring, but what's wanted is the width of the strip that has euclidean distance close to that of the given ring, which is given by one over the rate of change of distance(I hope - I'm making an educated guess here) - in this case 1/sinA.
So the correct expression seems to be sin2A/sinA, which simplifies to cosA (ignoring the constant factor) whose maximum in the range 0[le]A[le][pi]/2 comes at A=0, in other words, the south pole
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print