jfp@emory.UUCP (09/14/83)
No answers yet to what I thought was a fairly interesting problem:
What is the probability that 3 points chosen at random on a circle
lie within a semicircle (i.e. all within 180 degrees)?
That's not so hard, so then answer the same question for n points.
If that's too easy, try it on the surface of an m-sphere. (I don't
know the answer for the m-sphere - if anyone can give me a reference
I'd be grateful (or a solution)).
-----------------------------------------------------------
John Pedersen {sb1,akgua}!emory!jfpprodeng@fluke.UUCP (Jim Hirning) (09/16/83)
No answers yet to what I thought was a fairly interesting problem:
What is the probability that 3 points chosen at random on a circle
lie within a semicircle (i.e. all within 180 degrees)?
That's not so hard, so then answer the same question for n points.
If that's too easy, try it on the surface of an m-sphere. (I don't
know the answer for the m-sphere - if anyone can give me a reference
I'd be grateful (or a solution)).
-----------------------------------------------------------
John Pedersen {sb1,akgua}!emory!jfp
I am really bothered by this problem. Correct me if I'm wrong, but I
had the impression that probability dealt with descrete objects, not
continuous ones. A circle is most definitely continuous.
Even more to the point, how can we construct ratios of (ways we can get
3 points to lie within a semicircle) to (ways we can pick 3 points at
random) when there are uncountably many ways to do both? (Remember
the points on a circle are uncountable.)
HOWEVER, ignoring both of these problems, it seems to me that this may
be the way John Pedersen looks at the problem:
If we choose 1 point at random, it certainly is in the same semicircle
with itself. (probability is 1)
If we choose 2 points at random, the smaller arc between them must be
<= a semicircle. So, again probability is 1.
Once 2 points have been chosen, the probability that a third point will
lie within a semicircle containing the other two points is 3/4.
Here is how I come up with the number 3/4:
Let A and B be the first two points. It is equally likely (?????)
that the arc between them will encompass any angle between 0 and
180 degrees. To find out what part of the circle would place a
third point within a semicircle containing A and B, consider
two semicircles containing A and B: one with endpoint A, the
other with endpoint B. If we take the union of these two semicircles,
we will encompass the largest portion of the circle in which the
third point may fall and still share a s.c. (semicircle) with A and B.
If you draw a diagram (my terminal isn't too hot at circles :-) )
you will see that the union of these two s.c.'s covers an arc of
angle 360 degrees - (size of small arc AB in degrees). Thus if A
and B are very close, the third point C may fall almost anywhere
in the circle. If arc AB is 180 degrees, this fails, but since
this is only one of an infinitely many (in fact uncountably many)
cases, it shouldn't amount to a hill of beans. (I hope!!!)
So, if we consider all AB arcs between 0 and 180 degrees equally
likely (a big IF), then allowable arcs for C between 360 and 180
are equally likely. So, we average (over an uncountable set!
I told you this problem REALLY bothers me) to get an available
arc for C of 270 degrees, or 3/4 of the circle. So, on random
choice of C, there is a 3/4 chance of it being in the same s.c.
with A and B.
WHEW!
When we consider more points than 3, I believe the same strategy applies,
but instead of considering the arc between A and B, consider the arc
encompassing all the points considered so far. Assume that all are
within one s.c., because if they weren't, no method of choosing a next
point will make them all in one s.c. Again, the probability at each
stage is 3/4. So, multiplying all the probabilities together, for n
points, we get ****(3/4)^(n-2)****. (3 points, (3/4)^(3-2)=(3/4)^1=3/4)
For n < 3 the probability is 1.
I won't be on the net at this address beyond September 23, so please
don't send me mail if you don't think it will get here before then.
Please do comment to the net, I'd appreciate anyone shedding some light
on this subject.
Thanks.
Debbie Smit
fluke!prodeng (until Sept 23)
jim@ism780.UUCP (Jim Balter) (09/16/83)
For each of the n points, imagine a chord extending clockwise from that point through the other n-1 points. Since the n different chords include all the ways that the points might be formed into a semicircle, and since no two of the chords can both fall within a semicircle (with the exception of singular cases), the odds that all the points fall within a semicircle is the sum of the odds that any of the chords falls within a semicircle; since the points are equivalent, p = n * p_one_chord. Since, in order for one of the chords to fall within a semicircle, all of the last n-1 points must be within 1/2 the circle from the first point, p_one_chord is clearly (1/2) ** (n-1). So, p = n/(2**(n-1)). I actually derived the result empirically (Monte Carlo), and then found an analytical explanation. Many mathematical results have been derived this way, despite the purely analytical form in which they are published. Thus, the methods of mathematics are sometimes not as far from the methods of science as is often believed. I have no idea how to extend the result to n points within half an m-sphere, or whether there are better and/or more formal proofs. Jim Balter (decvax!yale-co!ima!jim), Interactive Systems Corp --------
jim@ism780.UUCP (Jim Balter) (09/17/83)
I of course meant "arc" wherever I said "chord". Just a little bug in my thought-to-English translator. A friend mentioned a related problem he had seen, asking the odds that the three pieces formed from a stick broken randomly in two places would form a triangle. There was an interesting geometric proof in Mathematical Games a number of years ago. Jim Balter (decvax!yale-co!ima!jim), Interactive Systems Corp --------
levy@princeton.UUCP (09/18/83)
I consider Debbie Smit's response to the circle probability problem an excellent example of the usefulness and of the pitfalls of heuristic reasoning in mathematics. The impression I have is that although she does not believe in the existence of continuous distributions of probability, this does not prevent her from following a water-tight argument for the three-point problem. Here's what you do when your space of possible events is a subset of the reals (like [0, pi] in this case): instead of considering the probability of a *single* event (say angle between two points is x) you consider the probability of an *interval* of events (angle between two points is less than or equal to x). This gives you a function called the (cumulative) probability distribution; if this function is differentiable, its derivative is called the density distribution and intuitively gives the probability that the random variable takes the value "between x and x+dx". In other words, if the density is big the chance that the event will take place in that region is bigger. So Debbie essentially applied this reasoning (including one necessary integration) to get the correct answer 3/4. For more than three points however she oversimplified assuming the chance that points 1,2,3 are in the same semicircle is independent of the chance that points 1,2,4 are in the same semicircle. So the answer (3/4)^(n-2) is wrong. To find the answer for n=4, for example, I reason as follows: The distribution of probabilities for the length of the segment spanned by the first two points is uniform in the interval [0, pi]; let's call this length x. Then the cumulative distribution for the length y of the segment spanned by the first three points will depend on x in the following way: for y < x, it is constant and equal to 0; for x <= y <= pi it is affine linear, growing from x / 2pi to 1 - x / 2pi. (y > pi is irrelevant, since the three points already won't be in the same semicircle.) Now for a fixed y the probability of that value of y as a function of x starts at y / pi for x = 0, decreases linearly to y / 2pi for x = y, then stays equal to 0 for y < x < pi. Averaging out gives 3 y*y / 4pi for the cumulative probability distribution of y, so the density is 3y/2pi. Now for any value of y the probability that the four points will be in a semicircle is 1 - y/2pi; integrating this with the density above gives 3/4 - 1/4 = 1/2; this is the probability that the four points will be in a semicircle. I don't know the answer for arbitrary n, and suspect it must be obtainable by a simpler reasoning than the above. -- Silvio Levy (should be writing my thesis...)
levy@princeton.UUCP (09/18/83)
Jim Balter's solution to the circle problem is wrong. I have run the simulation and the result for n=4 agrees with my result, 1/2. Moreover I have an inductive proof that the probability for arbitrary n is equal to n/(2^(n-1)). The proof goes like this (very sketchily): The distribution of probabilities for n-1 points to be in a segment of length at most x is at worst a polynomial of degree n-2 in x; this is seen by induction since it is obtained by integration of the distr. of prob. for n-2 points. Now for x small we have (Probability of n points in a segment of length x) ~ coeff*x^(n-2); this means there is *only* one term in the polynomial, and that's the highest term. Now for y=1 the probability is P(n-1), so the coefficient of the monomial is P(n-2)/pi^(n-2), the probability distribution is P(n-2)* x^(n-2)/pi^(n-2), and the density function is (n-2)*P(n-1)*x^(n-3)/pi^(n-2). Adding the n-th point means integrating the function 1-(x/2pi) with the density above. Assuming that P(n-1) is given by the formula (n-1)/(2^(n-2)) (which is certainly true for n=2, so the induction is valid), we finally get, with a little bit of work, P(n)=n / 2^(n-1), proving the induction. Some values: P(3) = .75, P(4) = .5, P(5) = 5/16 = .3125, P(6) = 3/16 = .1875. -- Silvio Levy
jfp@emory.UUCP (09/21/83)
I meant Jim Balter, not Jim Bailey, in my previous article. Sorry. ---- John Pedersen.