Points in a Semicircle


Points in a Semicircle, problem

Solution 1, Question 1

Associate with every point $X$ on a circle the semicircle arc $(X$ of which it is the midpoint. We claim that a set of points $\mathcal{X}$ on a circle lie in a semicircle only if the union of the associated semicircles does not completely cover the circle:

Let $(C)$ be the circumference of a circle (to avoid ambiguity); $\mathcal{X}=\{X_k:~X_k\in (C),~k=1,\ldots,n\},$ $n\gt 1$ an integer. Two statements below are equivalent

  1. There is point $P\in (C),$ such that $\mathcal{X}\subset (P.$
  2. $\displaystyle (C)\setminus\bigcup_{k=1}^n(X_k\ne\emptyset.$

Thus the original problem is equivalent to the one discussed earlier, where the probability was found to be $\displaystyle 1-2^{-n+1}n$ for the semicircles to cover $(C)$ completely, which implies that for a set $\mathcal{X}$ of $n$ random points on $(C)$ the probability of them all being covered by a semicircle is $\displaystyle \frac{n}{2^{n-1}}.$

Solution 2, Question 1

Case 1: $n$ is $1$ or $2.$

By inspection, the answer is $1.$

Case 2: $n \gt 2$

Let $P$ be any set of $n\gt 2$ points distributed uniformly at random on the circumference of a circle. With probability $1,$ the $n$ points are distinct. For any point $p\in P,$ let $S(p)$ be the semicircle starting at $p$ (inclusive) and continuing in the counterclockwise direction. If all $n$ points lie on the same semicircle, then there exists a point $p\in P$ such that $P \subseteq S(p).$

Choose a point $p \in P$ arbitrarily, and let $q$ be any one of the other $n-1$ points. The probability that $q \in S(p)$is $1/2.$ Therefore, the probability that $S(p)$contains all the other $n-1$ points is $(1/2)^{n-1}.$ Since, by definition, $S(p)$contains $p,$ the probability that $S(p)$ contains all $n$ points, that is, that $P \subseteq S(p),$ is also $(1/2)^{n-1}.$

When $n \gt 2,$ there is at most one point $p \in P$ such that $P \subseteq S(p).$ Therefore, we can sum the individual probabilities for each point $p \in P$ to obtain the probability that there exists any $p \in P$ such that $P \subseteq S(p).$ This sum is $n(1/2)^{n-1}.$ Therefore, the probability that all $n \gt 2$ points lie on the same semicircle is $n(1/2)^{n-1}.$

Combining cases

Note that $n(1/2)^{n-1} = 1$ when $n$ is either $1$ or $2.$ That is the same answer obtained in Case 1. Therefore, the expression from Case 2 gives the correct result for any positive integer $n,$ and the probability that all $n$ points lie on the same semicircle is $n(1/2)^{n-1}.$

Solution, Question 2

We make an assumption that $\phi\lt\pi.$

For a point $X\in(C),$ let $\Phi(X)$ be the arc subtending angle $\phi$ that extends counterclockwise from $X,$ inclusive of $X.$ The probability of a point uniformly distributed on $(C)$ to fall into $\Phi(X)$ equals $\displaystyle \frac{\phi}{2\pi}.$

Given $n\gt 2$ points $X_1,X_2,\ldots,X_n,$ the probability that $X_i\in\Phi(X_k),$ $i\ne k,$ is the same $\displaystyle \frac{\phi}{2\pi}$ and, for all $i\ne k,$ is $\displaystyle \left(\frac{\phi}{2\pi}\right)^{n-1}.$

For different $k,$ the events $E_k:~(\forall i\ne k) X_i\in\Phi(X_k)$ do not intersect, since $X_i\in\Phi(x_k)$ is incompatible with $X_k\in\Phi(X_i).$ It follows that the probability of the event $\displaystyle \sum_{k=1}^nE_k$ equals $\displaystyle n\left(\frac{\phi}{2\pi}\right)^{n-1}.$

Now, if for some point $Y,$ $(\forall i)X_i\in\Phi(Y),$ then, for $X_k$ nearest to $Y$ in the counterclockwise direction, $(\forall i\ne k)X_i\in\Phi(X_k).$ And, as we found, this event has the probability of $\displaystyle n\left(\frac{\phi}{2\pi}\right)^{n-1}.$


This is Problem 10 from an assignment for the MIT, 18.S34 (FALL 2007)

Solution 2 to Question 1 is by Joshua Jordan. Solution to Question 2 follows Josh's reasoning.


|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny