Given n points drawn randomly on the circumference of a circle, what is the probability they will all be within any common semicircle?

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