https://growingswe.com/blog/points-on-ring Back Points on a ring Thinking about my undergrad days studying math, I wish more problems were visualized like this Points on a ring N=4 N=5 N=3 N=6 N=4 N=5 Here's a problem that shows up in math competitions and quant interviews: Drop 4 points randomly on a circle. What are the chances they all land in the same half? Drop 4 points click drop to place points Drop 4 points Try it a few times. Sometimes all four cluster into one semicircle, sometimes they spread out. What probability would you guess? The obvious (wrong) answer The circle is symmetric, so place one point anywhere and ask whether the other three land in the same semicircle. Each of those 3 points independently has a 1/21/21/2 chance of landing in that half, so the probability should be (1/2)3=1/8=12.5%(1/2)^3 = 1/8 = 12.5\%(1/2)3=1/ 8=12.5%. Test that reasoning here. Click on the circle to fix your point, then drop 3 more and see whether they land in your semicircle. Repeat it many times and watch the rate: Fixed semicircle click on the circle to fix your point The rate hovers around 12.5%. The reasoning checks out for a fixed semicircle. But go back to the first demo and drop 4 points a bunch of times. The rate there is closer to 50%, not 12.5%. Something is off. The semicircle is not fixed We are not asking "do the points fit in this particular semicircle?" We are asking "do the points fit in any semicircle?" The semicircle gets to move. It can be anchored at whichever point makes it work. Drop 4 points below and click each one to try anchoring a semicircle there. Notice that at most one anchor ever works: Pick an anchor drop 4 points first Drop 4 points Fixing the semicircle in advance ignores configurations where the points do cluster together, just not around the chosen anchor. The real question is whether some point is a valid anchor. That is a much more generous condition. Anchoring at each point Label the 4 points 1,2,3,41, 2, 3, 41,2,3,4 in clockwise order around the circle. For each point iii, define the event: Ei= "all other points lie in the clockwise semicircle starting at point i"E_i = \text{"all other points lie in the clockwise semicircle starting at point } i\text{"}Ei = "all other points lie in the clockwise semicircle starting at point i " We already know the probability of each individual event. Once point iii is the anchor, each of the other N-1N - 1N-1 points independently has a 1/21/21/2 chance of landing in that semicircle: P(Ei)=(12)N-1P(E_i) = \left(\frac{1}{2}\right)^{N-1}P(Ei )=(21 )N-1 For 4 points, that is (1/2)3=1/8(1/2)^3 = 1/8(1/2)3=1/8, the same 12.5% we measured earlier. There is one such event for each of the NN N points, so we have NNN events each with probability 1/2N-11/2^{N-1} 1/2N-1. The points all fit in some semicircle exactly when at least one of these events occurs. We want the probability of the union E1[?]E2[?][?][?]ENE_1 \cup E_2 \cup \cdots \cup E_NE1 [?]E2 [?][?][?]EN . If we could just add them, we would get: Nx12N-1N \times \frac{1}{2^{N-1}}Nx2N-11 For N=4N = 4N=4: 4x1/8=1/24 \times 1/8 = 1/24x1/8=1/2. That matches our simulation. But we can only add probabilities when the events are mutually exclusive (no two can happen at the same time). Can two of these events overlap? Only one anchor ever works Go back to the anchor picker and try clicking different points. Whichever anchor's semicircle contains all the others, click the remaining points. Their semicircles always miss somebody. Place points below and click one to see its semicircle. Watch the gap (the empty arc going counterclockwise from the farthest point back to the anchor): Event E_i visualizer place 4 points first Place 4 points When EiE_iEi occurs, all the points are packed into a 180deg arc starting at point iii. The remaining arc (the gap going counterclockwise back to iii) is at least 180deg. Now suppose some other point jjj also tried to be an anchor. Point jjj's clockwise semicircle is exactly 180deg. But to contain all the points, it would need to bridge that gap of 180deg or more while simultaneously containing point iii on the other side. A 180deg arc cannot straddle a 180deg gap. So EjE_jEj cannot hold. Step through this argument on concrete points: Mutual exclusivity 1P12P23P34P4 4 points on a circle E1: point 1's semicircle covers all The gap is >= 180deg Try E2: misses point(s) Try E3: misses point(s) Try E4: misses point(s) Only E1 works 1 / 7 At most one EiE_iEi can occur at a time. The events are mutually exclusive, so we can add: P(all in some semicircle)=[?]i=1NP(Ei)=N[?]12N-1=N2N-1P(\text{all in some semicircle}) = \sum_{i=1}^{N} P(E_i) = N \cdot \frac{1}{2^{N-1}} = \ frac{N}{2^{N-1}}P(all in some semicircle)=[?]i=1N P(Ei )=N[?]2N-11 =2N-1N For 4 points: 4/8=1/24/8 = 1/24/8=1/2. Exactly 50%. Checking the formula The formula predicts that any two points always fit in a semicircle ( N=2N = 2N=2: 2/2=100%2/2 = 100\%2/2=100%), three points fit 75% of the time, and the probability drops sharply as NNN grows: NNN P(all in semicircle)P(\text{all in semicircle})P( Decimal all in semicircle) 2 2/2=12/2 = 12/2=1 100% 3 3/43/43/4 75% 4 4/8=1/24/8 = 1/24/8=1/2 50% 5 5/165/165/16 31.25% 6 6/32=3/166/32 = 3/166/32=3/16 18.75% 10 10/51210/51210/512 1.95% Adjust NNN and run batches. The simulated rate converges to the prediction: Semicircle simulator N = 4[4 ]4 click to simulate Place 4x100x1000 Smaller arcs Nothing in the argument required the arc to be a semicircle. If the arc has length xxx times the circumference (where x<=1/2x \leq 1/2x<=1/ 2), each anchor's event has probability xN-1x^{N-1}xN-1 instead of (1 /2)N-1(1/2)^{N-1}(1/2)N-1. Mutual exclusivity still holds because the gap is at least 1-x>=1/21 - x \geq 1/21-x>=1/2 of the circumference, too large for any other anchor's arc to bridge: P(all N points in some arc of length x)=N[?]xN-1P(\text{all } N \text{ points in some arc of length } x) = N \cdot x^{N-1}P(all N points in some arc of length x)=N[?]xN-1 Adjust the arc size and number of points: Arc size explorer N = 4[4 ]4 arc = 50% (180deg)[50 ]50 180deg arc Drop 4x100x1000 For example, 5 points all fitting in an arc covering 1/31/31/3 of the circumference: 5x(1/3)4=5/81[?]6.2%5 \times (1/3)^4 = 5/81 \approx 6.2\ %5x(1/3)4=5/81[?]6.2%. Beyond the circle The same decomposition works in higher dimensions. For NNN random points on a sphere, the probability they all lie in a hemisphere is also N/2N-1N / 2^{N-1}N/2N-1. The argument is identical: anchor a hemisphere at each point, observe that each event has probability 1/ 2N-11/2^{N-1}1/2N-1, and verify that at most one anchor can work (the complementary cap is at least a full hemisphere, so no other anchor's hemisphere can straddle it). TODO: If I figure out how to add 3d visualizations to this website, I'll cover the 3D case Thanks for reading! Wanna work with me? I'm open to software engineering and technical writing projects: growingswe at proton dot me growing