bonanova 77 Report post Posted May 2, 2014 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. Share this post Link to post Share on other sites

0 bubbled 3 Report post Posted May 6, 2014 (edited) 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 Share this post Link to post Share on other sites

0 DeGe 9 Report post Posted May 2, 2014 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. Share this post Link to post Share on other sites

0 Rob_G 1 Report post Posted May 2, 2014 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. Share this post Link to post Share on other sites

0 Rob_G 1 Report post Posted May 2, 2014 (1-Pi/360)^{n-2 } I'm not certain my math is correct though. Share this post Link to post Share on other sites

0 m00li 1 Report post Posted May 3, 2014 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-2}dx/2pi = (1/2pi)Int_{(-pi,pi)}(1-|x|/2pi)^{n-2}dx .... 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? Share this post Link to post Share on other sites

0 plasmid 39 Report post Posted May 3, 2014 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 Share this post Link to post Share on other sites

0 m00li 1 Report post Posted May 4, 2014 Yes, the solution is absolutely incorrect Share this post Link to post Share on other sites

0 DeGe 9 Report post Posted May 4, 2014 Considering the point raised by Rob, the answer stands corrected as 1/2^{(n-2)} Share this post Link to post Share on other sites

0 bonanova 77 Report post Posted May 4, 2014 Considering the point raised by Rob, the answer stands corrected as 1/2^{(n-2)} What if you picked a different starting point? Share this post Link to post Share on other sites

0 bonanova 77 Report post Posted May 6, 2014 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.) Share this post Link to post Share on other sites

0 bubbled 3 Report post Posted May 6, 2014 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. Share this post Link to post Share on other sites

0 bonanova 77 Report post Posted May 6, 2014 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. Share this post Link to post Share on other sites

0 m00li 1 Report post Posted May 6, 2014 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. Share this post Link to post Share on other sites

0 bubbled 3 Report post Posted May 7, 2014 (edited) 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 Share this post Link to post Share on other sites

0 plasmid 39 Report post Posted May 7, 2014 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. Share this post Link to post Share on other sites

0 bonanova 77 Report post Posted May 7, 2014 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}. Share this post Link to post Share on other sites

What is the probability that

points placed at random on the circumference of a circle all lie on a semicircular arc?nThat is, for at least one of the points, all the others lie [0, pi] radians from it.

## Share this post

## Link to post

## Share on other sites