wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> random points on a sphere
        
(Message started by: JocK on Aug 14^th, 2004, 3:47pm)

Title: random points on a sphere
Post by JocK on Aug 14^th, 2004, 3:47pm

What is the most likely distance between two randomly selected points on a sphere?

J8)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.

Title: Re: random points on a sphere
Post by honkyboy on Aug 14^th, 2004, 6:14pm

I'm assuming you are not looking for the average distance.
::[hide]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 = (r²+r²)^1/2.[/hide] ::

Title: Re: random points on a sphere
Post by JocK on Aug 15^th, 2004, 12:37am

Sorry, but not correct.... I'm indeed looking for the most likely distance, which need not be the expectation value for the distance.

J8)CK

Title: Re: random points on a sphere
Post by rmsgrey on Aug 15^th, 2004, 1:54am

The solution:
::[hide]
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 2^1/2r, though for a slightly different reason than honkyboy suggested
[/hide]::

Title: Re: random points on a sphere
Post by Eigenray on Aug 15^th, 2004, 5:39am

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:[hide]
The distribution function for [theta] is given by the (relative) area of the spherical cap:
1/4[pi]r² [int]_t=0^[theta] [int]_p=0^2[pi] r²sin 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.
Since d is monotone, its distribution function is simply (1-cos[theta])/2 evaluated when d([theta]) = d, which gives (d/r)²/4. The density of d is the derivative of that, d/2r², which is maximum at d=2r[/hide].
Another way to look at it: [hide]
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][/hide].

Title: Re: random points on a sphere
Post by JocK on Aug 15^th, 2004, 6:04am

That is correct Eigenray! ::[hide] Indeed: the most likely distance between two randomly chosen points on a sphere is equal to the diameter of the sphere. [/hide]::
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?

J8)CK

Title: Re: random points on a sphere
Post by Leonid Broukhis on Aug 15^th, 2004, 10:37am

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?

Title: Re: random points on a sphere
Post by JocK on Aug 15^th, 2004, 11:05am

on 08/15/04 at 10:37:02, 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.

J8)CK

Title: Re: random points on a sphere
Post by honkyboy on Aug 15^th, 2004, 2:52pm

???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)

Title: Re: random points on a sphere
Post by rmsgrey on Aug 16^th, 2004, 8:48am

on 08/15/04 at 05:39:01, Eigenray wrote:

area of the spherical cap:
1/4[pi]r² [int]_t=0^[theta] [int]_p=0^2[pi] r²sin 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/2r², 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

Title: Re: random points on a sphere
Post by rmsgrey on Aug 16^th, 2004, 9:03am

on 08/15/04 at 14:52:51, honkyboy wrote:

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

Title: Re: random points on a sphere
Post by Eigenray on Aug 16^th, 2004, 1:11pm

on 08/16/04 at 08:48:38, 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 = r²sin 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/2r², 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.

Title: Re: random points on a sphere
Post by william wu on Aug 16^th, 2004, 1:17pm

on 08/15/04 at 14:52:51, honkyboy wrote:

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.

http://mathforum.org/dr.math/faq/formulas/images/spherecap.gif

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](r₁² + h²) = [pi]x²

Since the CDF should be normalized to range from 0 to 1, we have

F(x) = [pi]x² / (4[pi]R²) = x² / (4R²)

Then the density function f(x) is

f(x) = x/(2R²)

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! http://www.ocf.berkeley.edu/~wwu/YaBBImages/crazy.gif

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)ⁿ. 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

Title: Re: random points on a sphere
Post by JocK on Aug 16^th, 2004, 1:41pm

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?

J8)CK

Title: Re: random points on a sphere
Post by JocK on Aug 16^th, 2004, 2:11pm

on 08/16/04 at 13:17:17, william wu wrote:

<..> the surface area of a cap is

2[pi]Rh = [pi](r₁² + h²) = [pi]x²

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]R² when going from area to cumulative probability...

Title: Re: random points on a sphere
Post by william wu on Aug 16^th, 2004, 2:14pm

Ah right, CDF must be bounded between 0 and 1. Thanks that fixes it.

on 08/16/04 at 13:41:20, 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?

J8)CK

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?

Title: Re: random points on a sphere
Post by Fresno_Bob on Aug 16^th, 2004, 2:43pm

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.

Title: Re: random points on a sphere
Post by towr on Aug 16^th, 2004, 2:59pm

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?

Title: Re: random points on a sphere
Post by Eigenray on Aug 16^th, 2004, 9:45pm

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 f_T(t) and f_D(d). Then
2[delta]f_T(t) ~ Pr(|T-t| < [delta]) ~ Pr(|D-d| < [epsilon]) ~ 2[epsilon]f_D(d),
when [epsilon]/[delta] ~ D'(t).
So f_D(d) = f_T(t)/D'(t), so there's no reason to expect both densities to be maximized at the same time.
In this case we have f_D(d) = [sin(t)/2]/[r²sin(t)/d] = d/(2r²).

Consider, what is the "most likely" value of x², when x is chosen uniformly from [0,1]?

Title: Re: random points on a sphere
Post by rmsgrey on Aug 17^th, 2004, 6:47am

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 2^0.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.

Title: Re: random points on a sphere
Post by william wu on Aug 19^th, 2004, 4:12am

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.

Title: Re: random points on a sphere
Post by Grimbal on Aug 21^st, 2004, 3:28pm

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

;D (enjoying the desperate looks)

Title: Re: random points on a sphere
Post by honkyboy on Aug 21^st, 2004, 7:06pm

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. ;D

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

Title: Re: random points on a sphere
Post by Rejeev on Oct 8^th, 2004, 2:16am

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.

Title: Re: random points on a sphere
Post by rmsgrey on Oct 8^th, 2004, 2:47am

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

Title: Re: random points on a sphere
Post by Rejeev on Oct 8^th, 2004, 3:43am

see the attached diagram. A' and A are same.
cosA' is perpenticular component of area and
sin2A is radius [in my previous posting i was wrongly used sinA; in fact i was thinking for a while sin2A = 2 sinA :) ].
Hence probability for a purticular distance is maximun at: where cosAsin2A is maximum (not cosAsinA).
Is this matching with Eigemray's solution?
How to paste a image (jpg) in reply??? ( so i have attached it)

Title: Re: random points on a sphere
Post by ccornchip on Oct 6^th, 2011, 1:15pm

Ok, so this is an ancient thread: I send my standard bumping apologies.

The answer, 2R, bothers me. It goes all the way back to Leo Broukhis's question: "How do you define the notion of maximum likelyhood in order to arrive at your intended answer?" which was answered by "The distance d for which the probability distribution P(x) peaks at it's (sic) maximum value."
Meaning, "let f(x) be the probability density function (p.d.f.) of the Euclidean distance between two points on a sphere. Find the x that maximises f(x)." And the answer to that is indeed x=2R.

The reason this doesn't sit right with many people (myself included) is that the number is meaningless and does not relate to the "most likely distance."
As a physicist, I ask a similar question, "given that on average, there is one star every cubic megaparsec of space in the universe, what is the 'most likely distance' than one can travel before encountering a star"
... the proposed solution would give zero since the p.d.f. goes as exp(-x).

I interpret "most likely distance" as
"Given a ball with two dots placed at random on its surface, what is the (Euclidean) distance between the dots that you would place a bet on finding, given that the closest punter wins."
This becomes an expected value problem, which has an answer not yet mentioned on this thread at all.

It's not 2R, nor is it R*sqrt(2), it's:
[hideb]
4R/3.
Take the p.d.f. f(x) by william wu, multiply by x then integrate.
[/hideb]

Title: Re: random points on a sphere
Post by towr on Oct 6^th, 2011, 10:59pm

on 10/06/11 at 13:15:00, ccornchip wrote:

I interpret "most likely distance" as
"Given a ball with two dots placed at random on its surface, what is the (Euclidean) distance between the dots that you would place a bet on finding, given that the closest punter wins."

Running a quick simulation* supports that you'd be about twice as likely to win against 2R.
However if I picked ever so slightly higher than your [hide]4/3R[/hide], I seem to win more than 55% of the time. So it does not seem like an unambiguous best bet.
(Which come to think of it isn't surprising, because the expected value isn't necessarily the median, and in a one on one bet the median is the better bet if the closest one wins.)

* by picking random x,y,z in space, keeping ones that fall in a small range of distance from the center of the sphere, rather than exactly on a surface.

Title: Re: random points on a sphere
Post by TenaliRaman on Oct 13^th, 2011, 11:06pm

Choosing the random points on the unit sphere in the following way,
1] Choose x,y,z from a normal distribution
2] Normalize the vector using the norm

Now, computing distance between various points and computing the histogram, I get the largest bucket to be the range 1.9 - 2.0. This supports the original assertion of 2R.

-- AI

Title: Re: random points on a sphere
Post by Grimbal on Oct 25^th, 2011, 2:04am

I did a quick simulation with 1000 buckets and 1000000 samples. It shows that P(x) is proportional to x.

Method:

each sample:
draw x, y and z uniformly in [-1,1]
d = |(x,y,z)|
discard samples that don't have 0.1<d<1
divide (x,y,z) by d
compute d = distance between (x,y,z) and (0,0,-1)
increment bucket[d/2*1000]

at the end:
plot bucket[n] vs n

Graphically it shows a straight line starting at (0,0).

*
-*
--*
---*
----*
-----*
------*
-------*
--------*
---------*
----------*
-----------*
------------*
-------------*
--------------*
---------------*
----------------*
-----------------*
------------------*
--------------------*
--------------------*
----------------------*
----------------------*
-----------------------*
------------------------*
-------------------------*
--------------------------*
---------------------------*
---------------------------*
-----------------------------*
------------------------------*
-------------------------------*
--------------------------------*
---------------------------------*
----------------------------------*
-----------------------------------*
------------------------------------*
-------------------------------------*
--------------------------------------*
---------------------------------------*
----------------------------------------*
-----------------------------------------*
------------------------------------------*
-------------------------------------------*
--------------------------------------------*
---------------------------------------------*
---------------------------------------------*
-----------------------------------------------*
------------------------------------------------*
-------------------------------------------------*
--------------------------------------------------*
---------------------------------------------------*
----------------------------------------------------*
-----------------------------------------------------*
-----------------------------------------------------*
-------------------------------------------------------*
--------------------------------------------------------*
---------------------------------------------------------*
---------------------------------------------------------*
-----------------------------------------------------------*
-------------------------------------------------------------*
------------------------------------------------------------*
--------------------------------------------------------------*
--------------------------------------------------------------*
---------------------------------------------------------------*
-----------------------------------------------------------------*
------------------------------------------------------------------*
-------------------------------------------------------------------*
--------------------------------------------------------------------*
---------------------------------------------------------------------*
---------------------------------------------------------------------*
-----------------------------------------------------------------------*
------------------------------------------------------------------------*
-------------------------------------------------------------------------*
--------------------------------------------------------------------------*
---------------------------------------------------------------------------*
----------------------------------------------------------------------------*
-----------------------------------------------------------------------------*
-------------------------------------------------------------------------------*
-------------------------------------------------------------------------------*
---------------------------------------------------------------------------------*
--------------------------------------------------------------------------------*
----------------------------------------------------------------------------------*
----------------------------------------------------------------------------------*
------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------*
----------------------------------------------------------------------------------------*
----------------------------------------------------------------------------------------*
-----------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------------*
---------------------------------------------------------------------------------------------*
---------------------------------------------------------------------------------------------*
-----------------------------------------------------------------------------------------------*
------------------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------------------*
----------------------------------------------------------------------------------------------------*
-------------------------------------------------------------------------------------------------*