Points on a circle

[bonanova]

What is the probability that n points placed at random on the circumference of a circle all lie on a semicircular arc?

That is, for at least one of the points, all the others lie [0, pi] radians from it.

[bubbled]

You can use logic to find that n=2 is 1, n=3 is 3/4 and n=4 is 1/2. It gets harder to use logic after that. This problem begs for a simulation to get an idea of a simple formula.

Use the real interval [0,1] and choose p_1 to be .5 and then you can simply collect your random points in a list and see whether max.list - min.list is less than .5.

Here is the result of the simulation:

n = 3 Probability = 0.749789
n = 4 Probability = 0.499941
n = 5 Probability = 0.312493
n = 6 Probability = 0.187558
n = 7 Probability = 0.109467
n = 8 Probability = 0.062752
n = 9 Probability = 0.034904
n = 10 Probability = 0.019425
n = 11 Probability = 0.010682
n = 12 Probability = 0.005788
n = 13 Probability = 0.003232
n = 14 Probability = 0.001665
n = 15 Probability = 0.000889
n = 16 Probability = 0.000488
n = 17 Probability = 0.000283
n = 18 Probability = 0.00014
n = 19 Probability = 7.2e-05

An interesting pattern emerges. The probability for n=2 is 2/2, for n=3 is 2/2*3/4, for n=4 is 2/2*3/4*4/6, for n=5 is 2/2*3/4*4/6*5/8. This can be simplified to:

n/(2^(n-1))

Edited May 6, 2014 by bubbled

[DeGe]

The first three points are always within a semi-circular arc.

From 4th point onwards, the probability of lying within a semi-circular arc is 1/2. For 4th the probability is 1/2. For 5th, it will be 4th lies within the arc and the 5th also; so 1/4... and so on

The overall probability is then 1/2^(n-3) for n>3. For n<3 it is 1.

[Rob_G]

The first three points are always within a semi-circular arc.

From 4th point onwards, the probability of lying within a semi-circular arc is 1/2. For 4th the probability is 1/2. For 5th, it will be 4th lies within the arc and the 5th also; so 1/4... and so on

The overall probability is then 1/2^(n-3) for n>3. For n<3 it is 1.

with your first statement. A counter-example would be if the three points formed an inscribed equilateral triangle.

[Rob_G]

(1-Pi/360)^n-2

I'm not certain my math is correct though.

[m00li]

Assume we have placed two points on the circle. the first at 0 radian and the second somewhere between x and x+dx radians. (the probability of doing this is dx/2pi). Here we are assuming a circle from -pi to pi, so that 0 is at the mid point of the interval (-pi,pi)

When x is in the interval (0,pi),

for any point to lie in the same semi circle as these two points, it can lie anywhere in the interval (x-pi, pi) with prob. (2pi-x)/2pi = 1-x/2pi

So, for n-2 points, prob. is (1-x/2pi)^(n-2)

Similarly, when x is in the interval (-pi,0),

prob. for n-2 points is (1-|x|/2pi)^(n-2)

Hence total probability is Int_(-pi,pi)(1-|x|/2pi)^n-2dx/2pi = (1/2pi)Int_(-pi,pi)(1-|x|/2pi)^n-2dx .... where Int(a,b) is definite integral from a to b

=2*(1-2^1-n)/(n-1) for n>2

The 'aha' solution you are looking for might not be applicable for a sphere. am i right?

[plasmid]

m00li: if you start with points 0 and x and then add a third point y that is within a semicircle containing 0 and x but y is not between 0 and x, then the probability of another point being in a semicircle with all three of those is no longer 1-x/2pi but is 1-(longest distance between any of 0 x and y)/2pi

[m00li]

Yes, the solution is absolutely incorrect

[DeGe]

Considering the point raised by Rob, the answer stands corrected as 1/2

^(n-2)

[bonanova]

Considering the point raised by Rob, the answer stands corrected as 1/2

^(n-2)

What if you picked a different starting point?

[bonanova]

You can use logic to find that n=2 is 1, n=3 is 3/4 and n=4 is 1/2. It gets harder to use logic after that. This problem begs for a simulation to get an idea of a simple formula.

Use the real interval [0,1] and choose p_1 to be .5 and then you can simply collect your random points in a list and see whether max.list - min.list is less than .5.

Here is the result of the simulation:

n = 3 Probability = 0.749789

n = 4 Probability = 0.499941

n = 5 Probability = 0.312493

n = 6 Probability = 0.187558

n = 7 Probability = 0.109467

n = 8 Probability = 0.062752

n = 9 Probability = 0.034904

n = 10 Probability = 0.019425

n = 11 Probability = 0.010682

n = 12 Probability = 0.005788

n = 13 Probability = 0.003232

n = 14 Probability = 0.001665

n = 15 Probability = 0.000889

n = 16 Probability = 0.000488

n = 17 Probability = 0.000283

n = 18 Probability = 0.00014

n = 19 Probability = 7.2e-05

An interesting pattern emerges. The probability for n=2 is 2/2, for n=3 is 2/2*3/4, for n=4 is 2/2*3/4*4/6, for n=5 is 2/2*3/4*4/6*5/8. This can be simplified to:

n/(2^(n-1))

Right answer, marked solved.

It's similar to DeGe's result, which is the probability that a particular point is a terminus of the arc.

A very simple words-only description also gives the result.

In this case it shoul explain why simulating a line segment works also when the ends are joined (circle.)

[bubbled]

You can use logic to find that n=2 is 1, n=3 is 3/4 and n=4 is 1/2. It gets harder to use logic after that. This problem begs for a simulation to get an idea of a simple formula.

Use the real interval [0,1] and choose p_1 to be .5 and then you can simply collect your random points in a list and see whether max.list - min.list is less than .5.

Here is the result of the simulation:

n = 3 Probability = 0.749789

n = 4 Probability = 0.499941

n = 5 Probability = 0.312493

n = 6 Probability = 0.187558

n = 7 Probability = 0.109467

n = 8 Probability = 0.062752

n = 9 Probability = 0.034904

n = 10 Probability = 0.019425

n = 11 Probability = 0.010682

n = 12 Probability = 0.005788

n = 13 Probability = 0.003232

n = 14 Probability = 0.001665

n = 15 Probability = 0.000889

n = 16 Probability = 0.000488

n = 17 Probability = 0.000283

n = 18 Probability = 0.00014

n = 19 Probability = 7.2e-05

An interesting pattern emerges. The probability for n=2 is 2/2, for n=3 is 2/2*3/4, for n=4 is 2/2*3/4*4/6, for n=5 is 2/2*3/4*4/6*5/8. This can be simplified to:

n/(2^(n-1))

Right answer, marked solved.

It's similar to DeGe's result, which is the probability that a particular point is a terminus of the arc.

A very simple words-only description also gives the result.

In this case it shoul explain why simulating a line segment works also when the ends are joined (circle.)

I thought long and hard about a words/logic only answer. So I'd love to see one. I'd find it much more interesting than my prosaic approach.

[bonanova]

Two points are on a semicircular arc, even if they are opposite ends of a diameter. For larger n, the remaining n-2 points simply have to lie on the same side of the diameter, with equal probability. That gets us a (1/2)^n-2 term, where DeGe stopped. We finally say that the argument applies to all of the n points. Thus p = n/2^n-2.

I see now you had n-1, but I think you meant n-2.

[m00li]

Two points are on a semicircular arc, even if they are opposite ends of a diameter. For larger n, the remaining n-2 points simply have to lie on the same side of the diameter, with equal probability. That gets us a (1/2)^n-2 term, where DeGe stopped. We finally say that the argument applies to all of the n points. Thus p = n/2^n-2.

I see now you had n-1, but I think you meant n-2.

This logic doesnt seem convincing. Suppose we have only three points to consider. Two issues:

1) "n-2 points simply have to lie on the same side of the diameter". Which diameter are we considering here? If we have fixed two points, and fixed 'the' diameter, the third can STILL lie on the other side of the diameter but be in the same semi circle. So the probability will not be 1/2 but more or less depending on the configuration of the first two points.

2) "We finally say that the argument applies to all of the n points". Since we did not chose 'the' two out of three points to begin with, this clause seems to 're-count' already counted cases. This clause seems to suggest that the ordering of selection is important.

[bubbled]

Two points are on a semicircular arc, even if they are opposite ends of a diameter. For larger n, the remaining n-2 points simply have to lie on the same side of the diameter, with equal probability. That gets us a (1/2)^n-2 term, where DeGe stopped. We finally say that the argument applies to all of the n points. Thus p = n/2^n-2.

I see now you had n-1, but I think you meant n-2.

The formula that fits the data is definitely n/(2^(n-1)). If you have 2^(n-2) in the denominator, you get p > 1 for n = 2 or n = 3 and p = 1 for n = 4.

My initial approach was to look at the average "spread" of the points after n points are chosen assuming they all fell in a semi-circular arc. I'm going to run a simulation of that and see if there's a pattern.

For example, if 2 points have been chosen, the average spread is 90 degrees. So the third point will satisfy the constraint if it falls 90 degrees to the left or right or falls in-between. Therefore, the third point has a 75% chance of "winning."

After 3 points, I believe the average spread would be 120 degrees, and after 4 points, it would be 125 degrees. As the spread gets bigger, the chances that the next point "wins' goes down.

As n gets large, the spread would converge on 180 degrees. This is why having n in the numerator and 2^(n-1) in the denominator makes sense.

I still feel like there's a simple logical "wordy" explanation. I just haven't had an "aha" yet.

Edited May 7, 2014 by bubbled

[plasmid]

I agree with m00li's skepticism of the answer in words as it's phrased, but the formula's results agreed with my simulation. It looks like I used essentially the same approach as bubbled, but having two different programs reach the same conclusion makes it unlikely that it's from a bug.

For 3 points, simulated  probability was 0.75365
For 3 points, calculated probability was 0.75

For 4 points, simulated  probability was 0.50114
For 4 points, calculated probability was 0.5

For 5 points, simulated  probability was 0.31222
For 5 points, calculated probability was 0.3125

For 6 points, simulated  probability was 0.18659
For 6 points, calculated probability was 0.1875

For 7 points, simulated  probability was 0.10713
For 7 points, calculated probability was 0.109375

For 8 points, simulated  probability was 0.06267
For 8 points, calculated probability was 0.0625

For 9 points, simulated  probability was 0.0344
For 9 points, calculated probability was 0.03515625

For 10 points, simulated  probability was 0.01999
For 10 points, calculated probability was 0.01953125

For 11 points, simulated  probability was 0.01029
For 11 points, calculated probability was 0.0107421875

For 12 points, simulated  probability was 0.00567
For 12 points, calculated probability was 0.005859375

For 13 points, simulated  probability was 0.00323
For 13 points, calculated probability was 0.003173828125

For 14 points, simulated  probability was 0.00173
For 14 points, calculated probability was 0.001708984375

For 15 points, simulated  probability was 0.00091
For 15 points, calculated probability was 0.00091552734375

For 16 points, simulated  probability was 0.00058
For 16 points, calculated probability was 0.00048828125

For 17 points, simulated  probability was 0.00026
For 17 points, calculated probability was 0.0002593994140625

For 18 points, simulated  probability was 0.00012
For 18 points, calculated probability was 0.0001373291015625

For 19 points, simulated  probability was 7e-005
For 19 points, calculated probability was 7.2479248046875e-005

#!/usr/bin/perl
use strict;
use warnings;

my $iterations = 100000;
my $maxpoints = 20;

for(my $points=3; $points<$maxpoints; $points++) {
  my $hits = 0;
  for(my $iteration=0; $iteration<$iterations; $iteration++) {
    # This will generate points on the circle with values from
    # zero to one. Think of it as units of 2pi radians.
    #
    # Without loss of generality, place the first point at 0.5
    # since that will make calculations easier.
    #
    # It means that if difference between the largest and smallest
    # point is greater than 0.5, then you can't fit them all in a
    # semicircle... If their difference is greater than 0.5 in
    # terms of simply subtracting one numeric value from another
    # (like points 0.8 and 0.1) then any arc of length 0.5 that
    # contains both of them must pass through the point 0, and
    # therefore could not also include the point 0.5.
    #
    # On the other hand, if the difference is less than 0.5, then
    # you can make an arc of length 0.5 containing all points.
    #
    # Rather than keeping track of every random point that gets
    # generated, this algorithm will just keep track of the
    # largest and smallest point coordinates. Remember that I
    # am placing the first point at 0.5.
    my $minpoint = 0.5;
    my $maxpoint = 0.5;
    for(my $point=1; $point<$points; $point++) {
      my $newpoint = rand;
      if($newpoint < $minpoint) {
        $minpoint = $newpoint;
      }
      if($newpoint > $maxpoint) {
        $maxpoint = $newpoint;
      }
    }
    
    $hits += ($maxpoint - $minpoint < 0.5);
  }
  print "For $points points, simulated  probability was " . ($hits/$iterations) . "\n";
  print "For $points points, calculated probability was " . ($points / (2**($points-1))) . "\n\n";
}

Addressing m00li's point about not having a pre-specified, fixed, diameter: this code essentially does allow the diameter that defines the semicircle to move over the course of adding points. For example, if both points 0.8 and 0.1 were included with point 0.5, then this would not count as a hit where you can draw a semicircle containing all points. But if either 0.8 alone or 0.1 alone appeared with point 0.5, then it would still count as a hit. No point is excluded as a possibility unless the other points that are already included force it to be impossible.

[bonanova]

Apologies to you both. I tried to think late last night, and from memory. The better (euphemism for accurate) thought solution follows:

Place a set of n points p_i on a circle.

The basic event of the puzzle is E_i = the event that a (edit: clockwise) semicircular arc beginning at p_i contains no p_j where i <> j.

The events for each point are disjoint, they all have obvious probabilities of (1/2)^n-1 and they may be summed.to obtain p = n/2^n-1.