wu :: forums - Print Page


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

        riddles >> medium >> Points On a Semicircle
        
(Message started by: william wu on Aug 11^th, 2003, 2:11am)

Title: Points On a Semicircle
Post by william wu on Aug 11^th, 2003, 2:11am

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.

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 5:08am

on 08/11/03 at 02:11:37, 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.

Title: Re: Points On a Semicircle
Post by william wu on Aug 11^th, 2003, 5:54am

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

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 6:53am

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

Title: Re: Points On a Semicircle
Post by william wu on Aug 11^th, 2003, 8:15am

argh sorry, dammit :P yea i just realized it after eating breakfast. time to sleep now.

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 8:48am

on 08/11/03 at 06:53:51, 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 [hide]1 / 2^(n-2) (for n>1)[/hide].

Pity I didn't get to answer this one before lunch and thus before you, towr (again). ;)

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 9:34am

those two points might be in many halfcircles..
(all points might be in for instance a quarter circle)

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 9:48am

I don't get your point.

on 08/11/03 at 09:34:02, towr wrote:

(all points might be in for instance a quarter circle)

In this case they are also in a semicircle, right?

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 9:54am

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?

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 10:08am

on 08/11/03 at 09:48:10, 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.

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 10:11am

on 08/11/03 at 09:54:00, 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..

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 10:14am

on 08/11/03 at 10:11:44, 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.

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 10:23am

on 08/11/03 at 10:08:53, 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.

Title: Re: Points On a Semicircle
Post by James Fingas on Aug 11^th, 2003, 10:24am

To prove that the answer isn't 1/2^n-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).

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 10:43am

on 08/11/03 at 10:24:36, James Fingas wrote:

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

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 11:06am

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

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 11:51am

f(n) = n/2^(n-1) ?

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 11:55am

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.

Title: Re: Points On a Semicircle
Post by James Fingas on Aug 11^th, 2003, 11:58am

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:

[hide]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 n^th point, the first n-2 points are randomly distributed in n-2-space from zero to pi. If the n^th 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. [/hide]

Title: Re: Points On a Semicircle
Post by James Fingas on Aug 11^th, 2003, 12:02pm

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?

Title: Re: Points On a Semicircle
Post by Mike_V on Aug 11^th, 2003, 12:06pm

From towr's simulations, I conjectured that the formula would be [hide]n/2^(n-1)[/hide]. I then reasoned the following: [hide]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).[/hide]

***
Edit: Wow, I took too long writing. That, and I'm liking my explanation less the more I think about it.

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 11^th, 2003, 12:16pm

on 08/11/03 at 11:58:24, 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 n^th point, the first n-2 points are randomly distributed in n-2-space from zero to pi. If the n^th 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?

Title: Re: Points On a Semicircle
Post by towr on Aug 11^th, 2003, 12:45pm

with the answer in hand, google also gives an interesting result: http://www.mathpages.com/home/kmath327.htm

Title: Re: Points On a Semicircle
Post by James Fingas on Aug 11^th, 2003, 2:13pm

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.

Title: Re: Points On a Semicircle
Post by william wu on Aug 11^th, 2003, 3:36pm

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)

Title: Re: Points On a Semicircle
Post by william wu on Aug 11^th, 2003, 7:03pm

Found out what's wrong with my solution. P(C|E1) = 1, because if there exists a special point then C must be satisfied, by the definition of a special point. P(E1) = 1/2^n-1, because a point is special if all the other points fall in a CCW semicircle from it. Somehow I got tricked by some subtlety in the definitions, and the fact that P(E1) = 1/n seemed intuitively correct. Anyways, make these replacements and I also get n/2^n-1.

Note: Thanks to yosen for figuring out what happened.

Title: Re: Points On a Semicircle
Post by James Fingas on Aug 12^th, 2003, 9:22am

Let's solve the other problem in the link that towr posted: Given N points on a sphere, what is the probability that they all lie on some hemisphere?

Title: Re: Points On a Semicircle
Post by wowbagger on Aug 14^th, 2003, 5:57am

on 08/11/03 at 14:13:08, James Fingas wrote:

wowbagger,

Apologies--I wasn't very clear.

There's no need to apologise. The main reason I didn't get you at first was probably my inability to think rationally (caused by the heat, of course ;)).

Quote:

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.

Upon rethinking, I see your points and have to agree.

Title: Re: Points On a Semicircle
Post by william wu on Oct 5^th, 2003, 7:39pm

on 08/12/03 at 09:22:48, James Fingas wrote:

Let's solve the other problem in the link that towr posted: Given N points on a sphere, what is the probability that they all lie on some hemisphere?

Hmm. Well first how about n points placed according to a uniform distribution on the surface of a circle. What's the probability they all lie in one half of the circle?

Incidentally I believe this would correspond to the probability that a round table would topple over, even after n legs have been placed underneath it in uniformly random locations.

Title: Re: Points On a Semicircle
Post by James Fingas on Oct 6^th, 2003, 10:49am

on 10/05/03 at 19:39:21, william wu wrote:

This seems to be the same as the question already posed. We can consider each point to be place at a position on the circumference, and then moved randomly towards the center (with the appropriate distribution, of course). They will all be in one half of the circle iff they are all on one half of the circumference.

It does seem logical that this corresponds to a table falling over with random legs placed beneath it. Quite an amusing analogy, really!

Title: Re: Points On a Semicircle
Post by william wu on Oct 6^th, 2003, 12:38pm

on 10/06/03 at 10:49:28, James Fingas wrote:

Very cool! It seems right intuitively, from symmetry ... what a keen mind you have. So I guess we must argue that the probability of a point falling on a radial line in the disk area case is equivalent to the probability of a point falling onto a point in the circumference case. It's true that both events have measure zero. I'm cautious though about believing things like this that deal with the infinitesimal.

Title: Re: Points On a Semicircle
Post by James Fingas on Oct 7^th, 2003, 8:12am

on 10/06/03 at 12:38:00, william wu wrote:

I guess we must argue that the probability of a point falling on a radial line in the disk area case is equivalent to the probability of a point falling onto a point in the circumference case.

I really hope we don't need to argue that. What I'm saying is that we can place points uniformly on a circle by choosing a point uniformly on the circumference, and then selecting a radial distance in the appropriate manner (using the distribution p(x) = 2x/r).

As soon as we accept that this is a valid model for placing points uniformly on a circle, the answer drops out--we just ignore the radial locations and see that the conditions on the circumferential locations are the same in the two cases.