Author |
Topic: choosing points on a circle (Read 6956 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
choosing points on a circle
« on: Dec 26th, 2012, 7:18pm » |
 Quote  Modify
|
n points are chosen randomly on the circumference of a circle. What is the probability that all lie in the same semicircle ?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: choosing points on a circle
« Reply #1 on: Dec 27th, 2012, 12:57am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: choosing points on a circle
« Reply #2 on: Dec 27th, 2012, 1:36am » |
Quote Modify
|
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".)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: choosing points on a circle
« Reply #3 on: Dec 29th, 2012, 5:13pm » |
Quote Modify
|
Elegant!
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: choosing points on a circle
« Reply #4 on: Dec 30th, 2012, 3:38am » |
Quote Modify
|
Thanks.
(I guess you meant the second one, not the first  )
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: choosing points on a circle
« Reply #5 on: Dec 30th, 2012, 6:42am » |
Quote Modify
|
How about for the surface of a (hyper)sphere?
|
| « Last Edit: Dec 30th, 2012, 6:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: choosing points on a circle
« Reply #6 on: Dec 30th, 2012, 9:06am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: choosing points on a circle
« Reply #7 on: Dec 30th, 2012, 9:33am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: choosing points on a circle
« Reply #8 on: Dec 30th, 2012, 12:08pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: choosing points on a circle
« Reply #10 on: Dec 31st, 2012, 12:21am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print