How likely are a bunch of random points on a circle to enclose the center?

September 9, 2017 @jamestanton asked on Twitter:

 

There are intelligent, even clever, ways to think about this problem.

However, in the spirit of Doron Zeilberger (who, by the way, IS very intelligent), I am just going to do a simulation of choosing 4 points on the circle, independently and uniformly randomly, many, many times, and check (= count) how often the center lies in the convex hull of those 4 points.

This, by the way, is very much in the spirit of Jim Tanton’s advice that if you don’t know what to do then just do something (and think about the result).

So … eassy-peasy, right?

But there’s a tiny issue: how do we choose a single point (let alone 4) uniformly randomly from a circle?

What does “uniform” mean in this setting?

Generally, “uniform” in this context is taken to mean that every line element, however small, on the circle gets it’s fair (= expected) share of points in many such choices of a point.

Let’s suppose, for the sake of being concrete and without really losing any generality, we take the circle to be the unit circle centered at the origin in the plane:

The points on the circle can be coordinatized as  where , so to uniformly randomly choose a point on the circle we uniformly randomly choose a number .

When we choose 4 points uniformly randomly on the unit circle we can get two geometric objects from these 4 points:

• a polygon, which depends on the order in which the points are chosen;
• the convex hull of the points, which does not depend on the order in which the points are chosen.

The difference is shown in the figures below:

 

Given 4 points, chosen uniformly and randomly in order, on the unit circle, Mathematica® has a neat way of finding the quadrilateral and the convex hull determined by these 4 points, and checking whether the circle center (0,0) lies in either region:

points = RandomPoint[Circle[], 4]
quad = Polygon[points];
convexhull = ConvexHullMesh[points];
Show[p2, p1, Graphics[quad]]
Show[p2, p1, convexhull]
RegionMember[quad, {0, 0}]
RegionMember[convexhull, {0, 0}]

We can simulate the choice of 4 uniformly random points on the circle a number of  times – say 100,000 – and check how often (0,0) lies in the quadrilateral and in the convex hull.

First we define the simulate function as follows:

simulate[n0_] :=
Module[{n = n0, points, quad, convexhull}, SeedRandom[n];
points = RandomPoint[Circle[], 4];
quad = Polygon[points];
convexhull = ConvexHullMesh[points];
{RegionMember[quad, {0, 0}], RegionMember[convexhull, {0, 0}]}]

It’s essential to put a re-seeding command inside the definition of the simulate function: without it the function will return the same result every time and will not be a (pseudo) random function.

The Mathematica® function Region Member checks whether a specified point lies in a given region.

Now we can simulate this 50,000 times, say, and calculate the relative frequency with which (0,0) lies in the quadrilateral and the convex hull:

upper = 50000;
simulations = Table[simulate[n], {n, 1, upper}];
N[Length[Cases[simulations, x_ /; x[[1]] == True]]/upper]
N[Length[Cases[simulations, x_ /; x[[2]] == True]]/upper]

with the result:

0.33586

0.50274

I should probably calculate a confidence interval for these estimates, but they are so tantalizingly close to 1/3 and 1/2 respectively, that perhaps it was wise to have thought a bit harder before calculating (sorry Doron!).

Anyway, having calculated we can now think about whether probabilities of 1/3 for the center of the circle being in the random quadrilateral, and 1/2 for being in the random convex hull, are correct and, if so, why.

---

When I first read Jim Tanton’s tweet I thought he meant in or on the circle : that would mean choosing 4 points uniformly randomly from a unit disk centered at (0,0).

The interpretation of uniformly random in this case is a little different: the basic idea is that each area element should receive its fair share of points.

Mathematica® does this automatically with RandomPoint[Disk[], 4], replacing RandomPoint[Circle[], 4] , so I can do the simulation over for the disk and when I do I get the same estimates for the probabilities.

Hmm!?? Should I?

What if I choose 5 points uniformly randomly instead of 4?

What if I choose n points? How does the probability of the polygon with these vertices (in order) containing the center of the circle vary with n? And what about the convex hull?

Surely if n is very large the convex hull is almost the unit disk so the probability of the center lying in the convex hull should get closer to 1 as n increases, shouldn’t it?

Here’s a plot of the approximate probability that the circle center will lie in the convex hull of n points chosen independently and uniformly randomly on the circle, versus n:

 

Mathematical food for thought.