Author |
Topic: Points On a Semicircle (Read 3186 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Points On a Semicircle
« on: Aug 11th, 2003, 2:11am » |
 Quote  Modify
|
N points are distributed randomly on the circumference of a circle according to a uniform distribution. What is the probability that all the points lie within a semicircle?
Edited 8:21 AM 8/11/2003 to remove a flawed and unnecessary third sentence. Thanks towr.
|
| « Last Edit: Aug 11th, 2003, 8:19am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Points On a Semicircle
« Reply #1 on: Aug 11th, 2003, 5:08am » |
Quote Modify
|
on Aug 11th, 2003, 2:11am, william wu wrote:
N points are distributed randomly on the circumference of a circle according to a uniform distribution. What is the probability that all the points lie within a semicircle?
|
|
dunno
Quote:| (In other words, what is the probability that the maximum distance along the circumference between any two points is pi*r, where r is the radius of the circle?) |
|
This is something else.. The distance along the circumference can never be greater than pi*r, since it is the furthest most point you can get from where you start, any 'further' and you get closer again.
|
| « Last Edit: Aug 11th, 2003, 5:09am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Points On a Semicircle
« Reply #2 on: Aug 11th, 2003, 5:54am » |
Quote Modify
|
sorry i meant to say less than or equal to pi*r
this problem is pretty tricky for me. i got 0 sleep today. actually i'm still stuck on it, my solution is very close to the right answer but it's slightly off and i can't figure why, grrr. i was going to put this problem in the hard section but i assume you guys are genius freaks 
|
| « Last Edit: Aug 11th, 2003, 8:17am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Points On a Semicircle
« Reply #3 on: Aug 11th, 2003, 6:53am » |
Quote Modify
|
Any two points on the circumference of a circle are never further than pi*r apart, since the circumference in total is 2*pi*r.. half of that is the furthest one point can be from another. (With more than zero sleep that should be clear  )
If you choose some halfcirlce, than the chance is 1 in 2^n that all points lie in that halfcircle's circumference.. But that's not the final answer, and perhaps not even helpfull in getting closer to it..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Points On a Semicircle
« Reply #4 on: Aug 11th, 2003, 8:15am » |
Quote Modify
|
argh sorry, dammit  yea i just realized it after eating breakfast. time to sleep now.
|
| « Last Edit: Aug 11th, 2003, 8:16am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #5 on: Aug 11th, 2003, 8:48am » |
Quote Modify
|
on Aug 11th, 2003, 6:53am, towr wrote:| If you choose some halfcirlce, than the chance is 1 in 2^n that all points lie in that halfcircle's circumference.. But that's not the final answer, and perhaps not even helpfull in getting closer to it.. |
|
I'd say it is helpful. You can choose your halfcircle using two of the n points. The firts defines your origin on the circle, the second defines the "right" side, where all other points should lie. So I think the answer should be 1 / 2^(n-2) (for n>1).
Pity I didn't get to answer this one before lunch and thus before you, towr (again).
|
| « Last Edit: Aug 11th, 2003, 8:50am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Points On a Semicircle
« Reply #6 on: Aug 11th, 2003, 9:34am » |
Quote Modify
|
those two points might be in many halfcircles..
(all points might be in for instance a quarter circle)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #7 on: Aug 11th, 2003, 9:48am » |
Quote Modify
|
I don't get your point.
on Aug 11th, 2003, 9:34am, towr wrote:| (all points might be in for instance a quarter circle) |
|
In this case they are also in a semicircle, right?
|
| « Last Edit: Aug 11th, 2003, 9:49am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #8 on: Aug 11th, 2003, 9:54am » |
Quote Modify
|
How about this (just to illustrate my thinking):
Map all points to an angle variable in the range [-pi..pi]. Our first point defines the angle 0. The second point can choose which side he likes more, he has either a positive angle or a negative one. After that, all n-2 other points have to have an angle whose sign agrees with the second point's.
Is this analogy flawed?
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Points On a Semicircle
« Reply #9 on: Aug 11th, 2003, 10:08am » |
Quote Modify
|
on Aug 11th, 2003, 9:48am, wowbagger wrote:I don't get your point.
In this case they are also in a semicircle, right? |
|
yes, but the chance of this happening is much smaller than it being more spread out over a semicircle.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Points On a Semicircle
« Reply #10 on: Aug 11th, 2003, 10:11am » |
Quote Modify
|
on Aug 11th, 2003, 9:54am, wowbagger wrote:Map all points to an angle variable in the range [-pi..pi]. Our first point defines the angle 0. The second point can choose which side he likes more, he has either a positive angle or a negative one. After that, all n-2 other points have to have an angle whose sign agrees with the second point's.
Is this analogy flawed? |
|
All points could be between -1/2 Pi and 1/2 Pi
Only if the first point is at an extreme of the semicircle this will work..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #11 on: Aug 11th, 2003, 10:14am » |
Quote Modify
|
on Aug 11th, 2003, 10:11am, towr wrote:| Only if the first point is at an extreme of the semicircle this will work.. |
|
Yes.
But we want the probability, right? We can choose a point at the extreme to be point number one.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #12 on: Aug 11th, 2003, 10:23am » |
Quote Modify
|
on Aug 11th, 2003, 10:08am, towr wrote:
yes, but the chance of this happening is much smaller than it being more spread out over a semicircle.
|
|
They are within a semicircle, my logic works for them... what's wrong?
Now, seriously: what probability do you want to calculate?
P(a) = "prob. that all n points are within an angle of a"? That's a more or less interesting generalization, but we should find an agreed-upon solution to the semicircle case first.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Points On a Semicircle
« Reply #13 on: Aug 11th, 2003, 10:24am » |
Quote Modify
|
To prove that the answer isn't 1/2n-2, consider what happens for n=3.
Place one point, WLOG, at zero degrees.
Place another point at the angle theta to the first (WLOG, theta is between zero and pi inclusive)
Place a third point at an angle alpha.
The three are all within one semi-circle if pi <= alpha <= theta-pi, so the probability is larger than 1/2. In fact, for three points, the probability is exactly 3/4 (seen by taking theta at its average value of pi/2--I know this is a bad statistical habit, but it works in this case).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #14 on: Aug 11th, 2003, 10:43am » |
Quote Modify
|
on Aug 11th, 2003, 10:24am, James Fingas wrote:To prove that the answer isn't 1/2n-2, consider what happens for n=3.
Place one point, WLOG, at zero degrees.
Place another point at the angle theta to the first (WLOG, theta is between zero and pi inclusive)
Place a third point at an angle alpha.
The three are all within one semi-circle if pi <= alpha <= theta-pi, so the probability is larger than 1/2. In fact, for three points, the probability is exactly 3/4 (seen by taking theta at its average value of pi/2--I know this is a bad statistical habit, but it works in this case). |
|
I don't think I can accept that as it is. You place some (random) point at zero degrees, while I don't. Maybe I wasn't clear enough on this, but my point number one, which defines zero degrees, is by definition an extreme point. That is, it is at the end of the semicircle. In the your scenario it is possible that your third point is my first.
Maybe a simulation would help, but I'm not sure I can come up with a reliable one right now. Besides, I'd have to devise an algorithm that actually does all the work.
|
| « Last Edit: Aug 11th, 2003, 10:45am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Points On a Semicircle
« Reply #15 on: Aug 11th, 2003, 11:06am » |
Quote Modify
|
I allready began a simulation..
here's the results for 10000 time, on a circle divided into 1024 discrete sections (which is why the N=2 case isn't 10000)
2 9992
3 7540
4 5042
5 3145
6 1868
7 1101
8 648
9 324
10 181
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #17 on: Aug 11th, 2003, 11:55am » |
Quote Modify
|
After my first simulation I thought it'd get even more interesting, but that was due to an error in my semicircle-detection. 
Now my simulation yields (100000 instances each, continuous angles):
n P(semicircle)
2 1.0
3 0.75015
4 0.49934
5 0.31332
6 0.18762
7 0.10964
8 0.06232
9 0.03498
10 0.01983
I tend to believe in my (and towr's) simulation results. Now, where is the error in my logic?
There seems to be a reasonable agreement with the formula you proposed, towr.
|
| « Last Edit: Aug 11th, 2003, 11:58am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Points On a Semicircle
« Reply #18 on: Aug 11th, 2003, 11:58am » |
Quote Modify
|
wowbagger,
It should be clear that my calculations are quite straight-forward, and are true representations of the averages. The problem with your approach is that choosing the extremal point to be at zero changes the probabilities for where the other points can be located.
Consider the general case, where we define n points such that the largest gap is from zero to some negative angle. By definition, you have changed the distribution of points around the circle, so they are less likely to be located at small negative angles.
My approach is a little simpler: after adding each point, rotate the resulting figure so that the largest gap is from zero to some negative angle. I'm sure the math is harder than we should by trying for, but it works for three points.
Here's my wild stab at a formula, but my explanation is currently a little weak:
p(1)=1
p(n+1) = p(n)*(1+1/(n-1))/2
giving predictions (out of 10000) of:
1: 10000
2: 10000
3: 7500
4: 5000
5: 3125
6: 1875
7: 1094
8: 625
9: 352
10: 195
11: 107
12: 59
13: 32
14: 17
I guess I'm saying that when you add the nth point, the first n-2 points are randomly distributed in n-2-space from zero to pi. If the nth point is from zero to pi, then you're good (hence the constant term of 1), or if you are larger than the maximum of all the previous values minus pi, you are okay. The expectation of the maximum of n values is (1-1/(n+1)), explaining the other term.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Points On a Semicircle
« Reply #19 on: Aug 11th, 2003, 12:02pm » |
Quote Modify
|
Okay,
So you beat me to the formula! And also to the explicit formula. Well, I'll be back...
How about this explanation (made to order to match the formula!)
We are calculating the probability that, taking any one of the n points to lie at zero degrees, all the other n-1 points lie within the first pi degrees. Note that doesn't seem logical at first, because the probabilities wouldn't really be independent ... or would they?
|
| « Last Edit: Aug 11th, 2003, 12:06pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Points On a Semicircle
« Reply #20 on: Aug 11th, 2003, 12:06pm » |
Quote Modify
|
From towr's simulations, I conjectured that the formula would be n/2^(n-1). I then reasoned the following: To make the problem easier, say we have n-1 points and we prechoose the specified semicircle. It's then clear that the probability that those n-1 points will lie in THAT semicircle is 1/2^(n-1). But this easier problem is the same situation as having n points and letting the first point define the semicircle (not as one end of it (there would be two possible ones), but as the middle). So for any preselected point, the probability that the other n-1 points lie in the semicircle defined by that point is 1/2^(n-1). Applying this possibility to all points: we multiply by n. Thus the probability is n/2^(n-1).
***
Edit: Wow, I took too long writing. That, and I'm liking my explanation less the more I think about it.
|
| « Last Edit: Aug 11th, 2003, 12:14pm by Mike_V » |
IP Logged |
Don't specify the unspecified.
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Points On a Semicircle
« Reply #21 on: Aug 11th, 2003, 12:16pm » |
Quote Modify
|
on Aug 11th, 2003, 11:58am, James Fingas wrote:| The problem with your approach is that choosing the extremal point to be at zero changes the probabilities for where the other points can be located |
|
There is rotational symmetry in this problem, no? So why am I not allowed to choose my zero the way I did?
Quote:Consider the general case, where we define n points such that the largest gap is from zero to some negative angle. By definition, you have changed the distribution of points around the circle, so they are less likely to be located at small negative angles.
My approach is a little simpler: after adding each point, rotate the resulting figure so that the largest gap is from zero to some negative angle. I'm sure the math is harder than we should by trying for, but it works for three points. |
|
As you may already have guessed, I don't see the difference. You end up with the same zero as me, right?
Have I really changed the distribution of points? (rhetorical question)
Quote:| I guess I'm saying that when you add the nth point, the first n-2 points are randomly distributed in n-2-space from zero to pi. If the nth point is from zero to pi, then you're good (hence the constant term of 1), or if you are larger than the maximum of all the previous values minus pi, you are okay. The expectation of the maximum of n values is (1-1/(n+1)), explaining the other term. |
|
I think I get that part, which is good enough for a start. But what's that n-2-space doing there?
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Points On a Semicircle
« Reply #23 on: Aug 11th, 2003, 2:13pm » |
Quote Modify
|
wowbagger,
Apologies--I wasn't very clear.
What I mean to say is that the location of the other points are not independent of the location of the endpoint you choose to stick at zero. For instance, with n=2, the second point cannot be in the lower half-plane. So now your math breaks down when you multiply the probabilities, because in doing so, you are assuming they are independent.
The difference I am trying to highlight in the second quote is that it's okay to rotate the end point to zero after you add a point, but it is not okay to do so before you add a point, because that rules out some locations for the new point, making its pdf no longer evenly distributed.
Sorry for the "n-2 space" remark. It was a side effect of trying to visualize how you would compute the expectation for the maximum of n-2 uniform random variables. The visualization didn't work ... I had to simulate to be sure I was using the right formula.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Points On a Semicircle
« Reply #24 on: Aug 11th, 2003, 3:36pm » |
Quote Modify
|
Alright guys, where did I go wrong here:
consider a random scattering of N points on the circumference of a circle. if all points are within a semicircle, then there exists a "special" point from which we can sweep our finger clockwise along the circumference and hit all the other N-1 points. given a special point, it is clear that (1/2)^(n-1) is the probability all other points lie within a clockwise sweep of length pi*r from the special point. so we invoke the total probability theorem: 1) for each point, compute the probability of success if that was the special point, 2) respectively multiply each of these conditional probabilities by the probability that that point was the special point, and 3) sum up all the products found in step 2).
N = total number of points
C = successful event that all points lie in semicircle
E1 = event that point 1 is the special point
EX = there is no special point
n = intersection operator
u = union operator
// Note that E1, E2, ... EN, EX form a partition.
Pr(C)
= Pr(C n E1) u Pr(C n E2) u ... u Pr(C n EN) u Pr(C n EX)
= Pr(C n E1) u Pr(C n E2) u ... u Pr(C n EN)
= Pr(E1)Pr(C|E1) + Pr(E2)Pr(C|E2) + ... + Pr(C n EN)
= (1/n)(2(-n+1)) + (1/n)(2(-n+1)) + ...
= n*(1/n)(2(-n+1))
= 2(-n+1)
(so i manage to cancel out the n in the numerator due to the (1/n) factor which comes from considering the probability that a certain point is the special point)
|
| « Last Edit: Aug 11th, 2003, 3:37pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print