I find this easier to visualize with an equivalent way to pick points: drop four (n) lines through the center of the circle. For each line, randomly pick one of the two points that intersect the circle.
Independent of the lines dropped, there are eight (2n) ways to pick adjacent points and sixteen (n^2) different combinations of points.
There are four (n) adjacent points iif the points lie on the same half of the circle (proof by interactive visualization).
Probably best to avoid the word ring in a mathematics discussion unless you're talking about the algebraic structure. It's very much a mathematical `keyword`.
This can be the case if the other point is exactly 180 degrees from the anchor point that works though? But I think this case occurs with probability 0 ("almost never") so can basically be ignored.
Also the "obvious (wrong) answer" that reasons "by symmetry" is interesting since the n=3 case _can_ actually be solved in this manner. It's well known that probability the center of the circle is contained in the triangle of 3 randomly chosen points can be computed is 1/4. (This can be found by placing 1 point arbitrarily then computing an integral that ranges over the arc length to the second point). For the n=4 case this can be done via a double integral considering two arcs but it's slightly more annoying.
I think there was a 3b1b problem about this that presents the more elegant approach the other commenter mentions.
You still have to unroll the circle from the anchor point, so once you have the circle to start with, you may as well finish there. A half-circle is more visually intuitive than a half-interval
> The same decomposition works in higher dimensions.
I don't think the same argument works in higher dimensions. On a circle, we can canonically pick a semicircle corresponding to each point (we have two choices, let's say we pick the clockwise one).
In higher dimensions there's no canonical choice of half-sphere. In odd dimensions one could pick a canonical half-sphere per point but it might turn out that some other non-chosen half-sphere for that point contains all the other points. In even dimensions there isn't even a way to canonically pick a half-sphere for each point (this is a consequence of the Hairy Ball Theorem).
(For all I know the actual numbers might turn out to be the same, I don't know. I'm just saying that the argument doesn't work.)
Well, it's easy to pick a half-n-sphere corresponding to a point on the surface. You just take the half-sphere centered at that point. For our two-dimensional circle, it would be the arc defined by the diameter that is perpendicular to the radius running between "the point" and the center of the circle.
At that point you've lost the ability to say that only one such half-sphere defined by a dropped point can be a valid solution, and you've also lost the ability to say that if a valid solution exists then there must be a valid solution defined by one of the points you want to include in the half-sphere, but you can define a canonical half-sphere for any point.
I was uncomfortable with the idea of picking "random points on a circle" to begin with, because of https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) , but the article doesn't even address whether the concept is well-defined. We can always choose a point on the perimeter deterministically from any chord (...that isn't a diameter), so the ill-definedness of the problem of choosing a random chord seems like it would infect the problem of choosing a random point on the perimeter.
Right, I was taking it as given that the problem of choosing a hemisphere canonically for a point meant "such that the argument works in the same way as for the circle".
Bertrand paradox just doesn't apply here, there's a natural measure on the circle and all higher dimensional spheres. I wouldn't expect an article on this subject to need to make that clarification unless it's dealing with chords or some other situation without a natural measure.
If I choose my four points as the endpoints of two chords chosen by the "random radial point" method described on the wikipedia page, is it still true that the odds of all four being covered by a semicircle are 50%?
I have no idea, but I wouldn't expect so unless it was by coincidence? Not sure what chords have to do with any of this. There's a canonical way to choose 4 points uniformly and independently at random on the circle, and it's got nothing to do with chords.
Seems unlikely, because the density of chords is much higher near the center of the circle than the rim. (The density of chords is infinite at exactly the center). This combines with the fact the points are farther apart when their bisector is closer to the center, making it harder for all 4 of them to be on a half-circumference.
I think about this by unwrapping the circle to form a straight line. Then you draw an imaginary point in the middle of the line.
Then what are the chances they will all fall on one side of the line or the other? 1/2 because it's divided into two equal lengths.
1. Your answer can be "no" when the true answer is "yes". Consider this process with a circle of perimeter "21":
--------------------- (unwrap the circle)
----------+---------- (bisect the line)
-**-------+--------** (drop four points)
The four points don't fall into either of the two semicircles that you stupidly predefined, but they do fall into a different semicircle.
2. Your answer of "1/2, because it's divided into two equal lengths" is completely wrong for the scenario that you specify.
Consider the case where we drop a single point. We can do the same procedure:
A. Unwrap the circle;
B. Bisect the line;
C. Drop one point.
But even though the line is still divided into two equal lengths, our one point has a 100% chance of falling either on one side of the bisection point, or on the other side.
For the case where we drop four points, the article already gives the correct answer for your method, which is 1/2^3 (because there are 3+1 points).
This approach implies the probability doesn’t depend on N. It only happens to be 1/2 for N=4 (the article goes into this). The trick is that you don’t know beforehand which semicircle all the points can land in, but your unwrapping step assumes you do.
I find this easier to visualize with an equivalent way to pick points: drop four (n) lines through the center of the circle. For each line, randomly pick one of the two points that intersect the circle.
Independent of the lines dropped, there are eight (2n) ways to pick adjacent points and sixteen (n^2) different combinations of points.
There are four (n) adjacent points iif the points lie on the same half of the circle (proof by interactive visualization).
So the answer is eight sixteenths (2n/2^n).
I think you typo'd, "sixteen (n^2) different combinations of points" should be 2^n instead.
Great argument. I found this generalization to higher dimension: https://www.mathpages.com/home/kmath327/kmath327.htm
Probably best to avoid the word ring in a mathematics discussion unless you're talking about the algebraic structure. It's very much a mathematical `keyword`.
>A 180° arc cannot straddle a 180° gap
This can be the case if the other point is exactly 180 degrees from the anchor point that works though? But I think this case occurs with probability 0 ("almost never") so can basically be ignored.
Also the "obvious (wrong) answer" that reasons "by symmetry" is interesting since the n=3 case _can_ actually be solved in this manner. It's well known that probability the center of the circle is contained in the triangle of 3 randomly chosen points can be computed is 1/4. (This can be found by placing 1 point arbitrarily then computing an integral that ranges over the arc length to the second point). For the n=4 case this can be done via a double integral considering two arcs but it's slightly more annoying.
I think there was a 3b1b problem about this that presents the more elegant approach the other commenter mentions.
I actually had to do this exact thing with my game recently in order to create interesting AI patterns during combat.
Wouldn't this be much cleaner to explain using polar coordinates and turning the circle into a line segment?
You still have to unroll the circle from the anchor point, so once you have the circle to start with, you may as well finish there. A half-circle is more visually intuitive than a half-interval
> The same decomposition works in higher dimensions.
I don't think the same argument works in higher dimensions. On a circle, we can canonically pick a semicircle corresponding to each point (we have two choices, let's say we pick the clockwise one).
In higher dimensions there's no canonical choice of half-sphere. In odd dimensions one could pick a canonical half-sphere per point but it might turn out that some other non-chosen half-sphere for that point contains all the other points. In even dimensions there isn't even a way to canonically pick a half-sphere for each point (this is a consequence of the Hairy Ball Theorem).
(For all I know the actual numbers might turn out to be the same, I don't know. I'm just saying that the argument doesn't work.)
Well, it's easy to pick a half-n-sphere corresponding to a point on the surface. You just take the half-sphere centered at that point. For our two-dimensional circle, it would be the arc defined by the diameter that is perpendicular to the radius running between "the point" and the center of the circle.
At that point you've lost the ability to say that only one such half-sphere defined by a dropped point can be a valid solution, and you've also lost the ability to say that if a valid solution exists then there must be a valid solution defined by one of the points you want to include in the half-sphere, but you can define a canonical half-sphere for any point.
I was uncomfortable with the idea of picking "random points on a circle" to begin with, because of https://en.wikipedia.org/wiki/Bertrand_paradox_(probability) , but the article doesn't even address whether the concept is well-defined. We can always choose a point on the perimeter deterministically from any chord (...that isn't a diameter), so the ill-definedness of the problem of choosing a random chord seems like it would infect the problem of choosing a random point on the perimeter.
Right, I was taking it as given that the problem of choosing a hemisphere canonically for a point meant "such that the argument works in the same way as for the circle".
Bertrand paradox just doesn't apply here, there's a natural measure on the circle and all higher dimensional spheres. I wouldn't expect an article on this subject to need to make that clarification unless it's dealing with chords or some other situation without a natural measure.
If I choose my four points as the endpoints of two chords chosen by the "random radial point" method described on the wikipedia page, is it still true that the odds of all four being covered by a semicircle are 50%?
I have no idea, but I wouldn't expect so unless it was by coincidence? Not sure what chords have to do with any of this. There's a canonical way to choose 4 points uniformly and independently at random on the circle, and it's got nothing to do with chords.
Seems unlikely, because the density of chords is much higher near the center of the circle than the rim. (The density of chords is infinite at exactly the center). This combines with the fact the points are farther apart when their bisector is closer to the center, making it harder for all 4 of them to be on a half-circumference.
I think about this by unwrapping the circle to form a straight line. Then you draw an imaginary point in the middle of the line. Then what are the chances they will all fall on one side of the line or the other? 1/2 because it's divided into two equal lengths.
There are two major problems with your idea:
1. Your answer can be "no" when the true answer is "yes". Consider this process with a circle of perimeter "21":
The four points don't fall into either of the two semicircles that you stupidly predefined, but they do fall into a different semicircle.2. Your answer of "1/2, because it's divided into two equal lengths" is completely wrong for the scenario that you specify.
Consider the case where we drop a single point. We can do the same procedure:
A. Unwrap the circle;
B. Bisect the line;
C. Drop one point.
But even though the line is still divided into two equal lengths, our one point has a 100% chance of falling either on one side of the bisection point, or on the other side.
For the case where we drop four points, the article already gives the correct answer for your method, which is 1/2^3 (because there are 3+1 points).
This approach implies the probability doesn’t depend on N. It only happens to be 1/2 for N=4 (the article goes into this). The trick is that you don’t know beforehand which semicircle all the points can land in, but your unwrapping step assumes you do.
This is exactly what the OP does, but without the mistakes you made.
Interesting and fun