All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Don't Be a Square (Posted on 2003-05-19)
Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

 See The Solution Submitted by DJ Rating: 4.4667 (15 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Numerical Answers | Comment 1 of 21
The problem involves finding a probability distribution for the expanse taken up by a set of n random points on the circle. Each such probability distribution depends on a certain integration of the distribution on the preceding value, n-1.

Daunted by the possibility of integrating this, I chose to integrate numerically. For a reasonable run time, 1/64 of a degree works as the interval for the numeric integration.

With n = 2, every separation from zero to 180 degrees is equally likely. From then on we need find the entire distribution from zero to 360 and see what fraction is below 180. Actually we could just integrate to 180, but finding the full distribution to 360 allows us to check our correctness to make sure our total probabilities add up to 1, or close enough to 1, based on the accuracy of our numerical integration.

The probability that n points will span the nominal value of the particular interval (of size 1/64 degree in the implementation) is equal to the probability of that span in the distribution for n-1 points multiplied by the probability that the next point would fall between the existing end points and so not increase the span, plus the total of the probabilities of any smaller span on the n-1 distribution multiplied by the probability that it would expand exactly (that is within 1/64 degree) to that span.

For a particular span, the probability that it would not change is span/360. The probability that a given smaller span would expand to a particular larger span, based on the interval of integration of 1/64 degree, is 2/64 for every new, larger span that lies between oldspan+1/64 and 180+oldspan/2 (the largest case, in which the new point is 180 degrees away from the midpoint of the old arc). (It's 2/64 rather than 1/64 as it could be on either side of the original span.) When trying to find the smallest previous span that could lead to the new span being calculated, the latter limit translates to lowest oldspan = 2 * newspan - 360. Of course the largest span that could expand to the new span would be just the new span minus the increment of 1/64.

The program to evaluate this is

incr = 1 / 64
DIM pr(360 / incr + 1)
multr = 2 * incr / 360
n = 2
FOR i = 0 TO 180 STEP incr
ss = i / incr
pr(ss) = 1 / (180 / incr)
NEXT
PRINT : PRINT n;
tot = 0
FOR i = 0 TO 360 STEP incr
ss = i / incr
tot = tot + pr(ss)
IF i < 180 THEN tot2 = tot2 + pr(ss)
NEXT
PRINT tot, tot2 / tot
DO
n = n + 1
FOR i = 360 TO 0 STEP -incr
ss = i / incr
pr(ss) = pr(ss) * i / 360
lowv = 2 * i - 360: IF lowv < 0 THEN lowv = 0
FOR j = lowv TO i - incr STEP incr
ss2 = j / incr
pr(ss) = pr(ss) + pr(ss2) * multr
NEXT
NEXT
PRINT n;
tot = 0: tot2 = 0
FOR i = 0 TO 360 STEP incr
ss = i / incr
tot = tot + pr(ss)
IF i < 180 THEN tot2 = tot2 + pr(ss)
NEXT
PRINT USING \"#.##### #.#####\"; tot; tot2 / tot
' DO: LOOP UNTIL INKEY\$ > ""
LOOP

The results from this program are
2 .9999816 .9999132 1
3 1.00013 0.74990 3/4
4 1.00010 0.49988 1/2
5 1.00008 0.31240 5/16
6 1.00006 0.18742 3/16
7 1.00004 0.10932 7/64
8 1.00001 0.06246 1/16
9 1.00000 0.03513 1/32 ?
10 0.99997 0.01951 ?

The total probability from zero to 360 is included as a check, and all are indeed close to 1. After the computed decimal fraction that are below 180 degrees, the rational approximations above were my estimates, rather than output. The numbers all looked like fractions with powers of 2 in the denominator. The question mark after 1/32 reflects the fact that, while in all the rest the numerical decimal fraction is slightly below what presumably is the rational fraction, .03513 is slightly above 1/32. I don't venture to guess about .01951.

 Posted by Charlie on 2003-05-19 09:40:39

 Search: Search body:
Forums (0)