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

        riddles >> cs >> choosing points on a circle
        
(Message started by: birbal on Dec 26th, 2012, 7:18pm)
Title: choosing points on a circle
Post by birbal on Dec 26th, 2012, 7:18pm
n points are chosen randomly on the circumference of a circle. What is the probability that all lie in the same semicircle ?
Title: Re: choosing points on a circle
Post by jollytall on Dec 27th, 2012, 12:57am
Let the circumfence of the circle be 2 (to get rid of Pi).
I do not look at the options when two points are exactly opposite. It is not clear whether they are on the same semicircle or not, but the probability of this happeneing is anyway 0.

Let's place the points one by one. After n points there are two options. They are all on the same semicircle with Pn probability and 1-Pn probability that they are not. In the 1-Pn case game over, the (n+1)th point will not change it.
For the Pn part, let define a probability function Pn(x), where 0<x<1 and gives the probability of the two farest points being maximum x distance. We choose it that Pn(1) = Pn.
If we have Pn(x), then Pn+1(x) can be calculated:

Pn+1(x) = INT(z=0-x) dPn(z)/dz * (2x-z)/2 * dz = x*Pn(x) - 1/2* INT(z=0-x) dPn(z)/dz*z*dz
(INT(z=0-x) means integral according to z between 0 and x.)
The logic here, that if the two farest points are z apart, then we have a (2x-z)/2 probability that the next point will be still maximum x distance away from the farest.

P1(x) = 1
p2(x) = x-0=x
P3(x) = x2 - 1/2* INT(z=0-x) z * dz = x2 - 1/4x2 = 3/4 x2
etc.

for every n, there is an An to make Pn(x)=Anxn-1
A1=1
A2=1
A3=3/4
for larger n-s, An can be calculated from the above formula. An+1= An - 1/2*An*(n-1)/n = An*(n+1)/2n
A4=1/2
A5=1/2*5/8=5/16
A6=5/16*6/10=3/16
A7=3/16*7/12=7/64

It can be seen that
An=n/2n-1
with full induction, it can be proven for all n-s
An+1= n/2n-1*(n+1)/2n=(n+1)/2n+1

i.e. Pn(x)=n/2n-1 * xn-1
The probability of all the n points being on the same semicircle is Pn(1)=An=n/2n-1
Title: Re: choosing points on a circle
Post by jollytall on Dec 27th, 2012, 1:36am
Actually, the sub-forum misled me and I was looking for a relatively complicated solution. Now, having the result, there is a much easier solution too.
Having n points on the circle. Let choose one. What is the probability that all the n-1 are on the half circle right (clock-wise) from this point. It is obviously 1/2n-1.
We can choose all the n points as the "left most". So, the probabilities add up to n/2n-1.
(There is no overlap among the solutions, since no 2 points can be the "left most".)
Title: Re: choosing points on a circle
Post by Grimbal on Dec 29th, 2012, 5:13pm
Elegant!
Title: Re: choosing points on a circle
Post by jollytall on Dec 30th, 2012, 3:38am
Thanks.

(I guess you meant the second one, not the first :-) )
Title: Re: choosing points on a circle
Post by towr on Dec 30th, 2012, 6:42am
How about for the surface of a (hyper)sphere?
Title: Re: choosing points on a circle
Post by jollytall on Dec 30th, 2012, 9:06am
Can't it be done the same way? We assign two axises with a priority. If we have all the points on a semisphere we start turning the semishere around the first axis until any point would get out. If it does not happen after a full round, we can still use the second (right angle) axis. This way the semishere will get stuck at one point. We call this semishere belonging to this point (and only this point, except if it gets stuck on two points at the same time, what has a 0 probability). The probabiity that all other points are on this semiphere is 1/2n-1. We have n points. The turning of the semispere ensures that there is no overlap among the solutions.
So the result is the same?
Title: Re: choosing points on a circle
Post by towr on Dec 30th, 2012, 9:33am
That would suggest that for three points, there's only 50% probability they lie in the same hemisphere. But they lie on a circle, so they're in the same hemisphere.
Title: Re: choosing points on a circle
Post by jollytall on Dec 30th, 2012, 12:08pm
Yes, it was fishy to me too. It is not that easy.

My logic was wrong where tried to attach a semishere to one point. It is much more logic to attach it to two points.
The A and B points in this order point to ONE semishere only (the one on the right - let's say - from the A to B vector). The other semishere is B to A.
All points must be in the semishere, so it is a 1/2n-2 chance for a given AB point-pair.
I can choose 2 points (with an order) n*(n-1) ways.
Unfortunately, unlike the circle problem, they are not distinct solutions. It should be made distinct, but cannot figure out, how. If there are three points ABC, then AB, BC, CA can all be good, i.e. the result has to be divided by 3.
But if there are more than 3 points, then the multiple count is not a fixed number. Sometimes it is only three (the others are within the triangle), but can be up to n, if they form a relatively small convex poligon.
Title: Re: choosing points on a circle
Post by towr on Dec 30th, 2012, 1:10pm
The following page has a solution for the K-dimensional case: http://www.mathpages.com/home/kmath327/kmath327.htm (although I haven't read it through thoroughly yet)
Title: Re: choosing points on a circle
Post by jollytall on Dec 31st, 2012, 12:21am
Very nice find. It seems logic.

Back to the ball, I still try to find some "logic" explanation, now knowing the answer.

The answer in (n2-n+2)/2n.

That is the same as n/2n-1 + (n-1)*n-2)/2n. This is the circle solution (and my first guess) plus (n-1)*(n-2)/2n. There could be a logic explanation, what sounds like:
For every point from the n we can assign a hemishpere and the probability that all others are in that hemishere is 1/2n-1. The solutions must be exclusive, so the probabilities can add up. So far it is easy to implement. Lets choose a random point on the ball and call it the North Pole. Now every point of the n can be Greenwich and split the ball into a Western and Eastern hemishere. The probaility is just as said.
As towr, you pointed out this is obviously understating the probability, since it can happen that all points are on the Northern hemishere (or even a tilted one) scattered around. No Greenwich will work, but still they are on one semishpere. This adds additional probability, what based on the known answer is (n-1)(n-2)/2n. This second piece I cannot visualise. It would sound like, take a fixed point and from the remaining n-1 points select two (with or without direction...) and...
I think it is close, but cannot find.

Another way to look at the formula:
It is the same as 1/2n-2 * ( n*(n-1)/4 + 1/2).
It is very similar to my second approach. Choose two points with a direction. The probability that all the remaining n-2 are on the same semishere is 1/2n-2. But with the n*(n-1) we overcount the probability at least 3 times, but sometimes even more, so we have to divide it. I could not figure it out in my previous post, how. Now we know the solution: divide by 4 and also add a half. Why? I cannot visualise either.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board