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

In a simulation of 1,000,000 trials, adding 11 points at random, one at a time, and noting at each number of points from 3 to 11 the span taken up, the following numbers appear:
  3 187486 561980 749466 250534 0 1000000
  4 62659 437033 499692 500308 0 1000000
  5 19439 292777 312216 683941 3843 1000000
  6 5880 181339 187219 787418 25363 1000000
  7 1662 107769 109431 816731 73838 1000000
  8 492 62104 62596 790008 147396 1000000
  9 153 35259 35412 726006 238582 1000000
 10  34 19706 19740 643549 336711 1000000
 11  7 10834 10841 554994 434165 1000000

The middle column is the number, for the given number of points plotted so far, that are within 180 degrees. The two numbers before this are for the first and second quadrants (fitting within 90 degrees, fitting more than 90 less than 180). After the 180 figure come the 3rd and 4th quadrants and the final column has the total of 1,000,000 for a check.

The program simulating the random placement placed the first point always at 0 and everything else is relative to that:

DIM span(11, 360)
DIM pt(11)
PRINT : PRINT : PRINT
RANDOMIZE TIMER
FOR trial = 1 TO 1000000
  ERASE pt
  pt(1) = 0
  pt(2) = RND(1) * 360
  FOR ptNo = 3 TO 11
    cPosn = RND(1) * 360
    ins = 0
    FOR i = 2 TO ptNo - 1
      IF pt(i) > cPosn THEN
        FOR j = i TO ptNo
          SWAP pt(j), cPosn
        NEXT
        ins = 1
        EXIT FOR
      END IF
    NEXT
    IF ins = 0 THEN pt(ptNo) = cPosn
    lgGap = 0
    FOR i = 2 TO ptNo
      IF pt(i) - pt(i - 1) > lgGap THEN lgGap = pt(i) - pt(i - 1)
    NEXT
    IF 360 - pt(ptNo) > lgGap THEN lgGap = 360 - pt(ptNo)
    lgSpan = 360 - lgGap
    span(ptNo, INT(lgSpan)) = span(ptNo, INT(lgSpan)) + 1
  NEXT
NEXT trial

FOR i = 3 TO 11
  tot = 0: subtot = 0: st2 = 0
  PRINT USING "### "; i;
  FOR j = 1 TO 360
    subtot = subtot + span(i, j - 1)
      ' j - 1 because of original truncation
    st2 = st2 + span(i, j - 1)
    tot = tot + span(i, j - 1)
    IF j / 90 = INT(j / 90) THEN
      PRINT USING "#######"; subtot;
      subtot = 0
    END IF
    IF j = 180 THEN
      PRINT USING " ######## "; st2;
      st2 = 0
    END IF
  NEXT
  PRINT USING "##########"; tot;
  tot = 0
  PRINT
NEXT

Posted by Charlie on 2003-05-20 10:03:08