Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

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

September 9, 2017 By Gary Ernest Davis

September 9, 2017 @jamestanton asked on Twitter:

 

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

Doron Zeilberger

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 (\cos (\theta), \sin (\theta))  where 0\leq \theta \leq 2\pi , so to uniformly randomly choose a point on the circle we uniformly randomly choose a number 0\leq \theta \leq 2\pi .

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.

 

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

 

 

 

 

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in