Probability that n points on a circle are in one semicircle

Question

Choose n points randomly from a circle, how to calculate the probability that all the points are in one semicircle? Any hint is appreciated.

Answer 1

A variation on @joriki's answer (and edited with help from @joriki):

Suppose that point $i$ has angle $0$ (angle is arbitrary in this problem) -- essentially this is the event that point $i$ is the "first" or "leading" point in the semicircle. Then we want the event that all of the points are in the same semicircle -- i.e., that the remaining points end up all in the upper halfplane.

That's a coin-flip for each remaining point, so you end up with $1/2^{n-1}$. There's $n$ points, and the event that any point $i$ is the "leading" point is disjoint from the event that any other point $j$ is, so the final probability is $n/2^{n-1}$ (i.e. we can just add them up).

A sanity check for this answer is to notice that if you have either one or two points, then the probability must be 1, which is true in both cases.

Answer 2

Here's another way to do this:

Divide the circle into $2k$ equal sectors. There are $2k$ contiguous stretches of $k$ sectors each that form a semicircle, and $2k$ slightly shorter contiguous stretches of $k-1$ sectors that almost form a semicircle. The number of the semicircles containing all the points minus the number of slightly shorter stretches containing all the points is $1$ if the points are contained in at least one of the semicircles and $0$ otherwise; that is, it's the indicator variable for the points all being contained in at least one of the semicircles. The probability of an event is the expected value of its indicator variable, which in this case is

$$2k\left(\frac k{2k}\right)^n-2k\left(\frac{k-1}{2k}\right)^n=\frac k{2^{n-1}}\left(1-\left(1-\frac1k\right)^n\right)\;.$$

The limit $k\to\infty$ yields the desired probability:

$$ \lim_{k\to\infty}\frac k{2^{n-1}}\left(1-\left(1-\frac1k\right)^n\right)=\lim_{k\to\infty}\frac k{2^{n-1}}\cdot\frac nk=\frac n{2^{n-1}}\;. $$

Answer 3

See

https://mathoverflow.net/questions/33112/estimate-probability-0-is-in-the-convex-hull-of-n-random-points

for the general problem (when the points have any distribution that is invariant w.r.t. rotation about the origin) and

https://mathoverflow.net/questions/2014/if-you-break-a-stick-at-two-points-chosen-uniformly-the-probability-the-three-re/2016#2016

for a nice application.

As a curiosity, this answer can be expressed as a product of sines:

Prove that $\prod_{k=1}^{n-1}\sin\frac{k \pi}{n} = \frac{n}{2^{n-1}}$

Answer 4

Bull, 1948, Mathematical Gazette, Vol 32 No 299 (Dec), pp87-88 solves this problem in the context of the broken stick problem (he uses polytopes and relative volumes in his argument). Rushton, 1949, Mathematical Gazette, Vol 33 No 306 (May), pp286-288 points out that the problem can be re-stated in terms of placing points at random on the circumference of a circle. Ruston's answer is the clearest I have seen. Place $n$ points randomly on the circumference. Label them $X_1, X_2, ..., X_n$. Open up the circle at $X_n$ and produce a straight line. Label the line $OX_n$ (where $O$ is the part of the circle previously immediately adjacent to $X_n$). There are $n$ line segments: $OX_1, X_1X_2, ..., X_{n-1}X_n$. Each segment is equally likely to be longer than half the length of $OX_n$ (and thus correspond to greater than a semi-circle of the orginal circle). The probability that the first segment fulfils this condition is the probability that the remaining $n-1$ points lie upon the second half of the line $OX_n$. That is $(\frac{1}{2})^{(n-1)}$. The probability that there is one segment (note there can be at most one) greater than half the length of the circumference is the sum of the probabilities that each particular segment could be so (because these are mutually exclusive): $n(\frac{1}{2})^{(n-1)}$. So, the favorable probability is $1 -n(\frac{1}{2})^{(n-1)}$.

Answer 5

Another simpler approach,

1) Randomly pick $1$ out of $n$ points and call it $A$ : $\binom n1$ ways

2) Starting from $A$, mark another point $B$ on circumference, such that $length(AB) = \frac12(Cirumference)$ [so that $AB$ and $BA$ are two semi-circles]

3) Now out of remaining $(n-1)$ points, each point can lie on either $AB$ or $BA$ with probability $\frac12$

4) For ALL the remaining $(n-1)$ points to lie on EITHER $AB$ OR $BA$ (i.e., all $(n-1)$ lie on same semi-circle), the joint probability is $\frac12*\frac12 ...(n-1) times$ $=$ $(\frac12)^{(n-1)}$

Since #1 above (randomly picking $A$) is an independent event, $\therefore$ $(\frac12)^{(n-1)}$ (expression in #4) will add $\binom n1$ times

$\implies$ Required probability is $\binom n1(\frac12)^{(n-1)}$ $=$ $n(\frac12)^{(n-1)}$

Answer 6

Here is a brute force solution. We let $n > 2$. Let $X_1, \ldots, X_n$ be uniform random variables into the circle of circumference $1$, $S^1/2\pi$. We know that every configuration of $n$ points has two points on the outside. So now we calculate the probability $$ p_{i,j} = \mathbb{P}(\text{$X_1,\ldots,X_n$ lie in a semicircle} \wedge \text{$X_i,X_j$ are on the outside}) $$ where $\wedge$ means that the two events happen at the same time. Let us call the above event $E_{i,j}$. Let $\alpha(X_i,X_j)$ be the shorter distance of the two distances possible between $X_i$ and $X_j$. Now since the $X_i$ are independent, the variable $X_k$ is independent of $\alpha(X_i,X_j)$ for $k \neq i,j$. Thus we must have that $$ \mathbb{P}(E_{i,j}|\alpha(X_i,X_j) = \alpha_0) = \alpha_0^{n-2} $$ because the probability of $X_k$ landing in the shorter arc between $X_i$ and $X_j$ is just $\alpha(X_i,X_j)$. Note that $\alpha(X_i,X_j)$ is uniformly distributed on $[0,1/2]$. So we have that $$ \begin{aligned} p_{i,j} &= 2 \int_0^{1/2} \mathbb{P}(E_{i,j} | \alpha(X_i,X_j) = \lambda)d\lambda \\ &= 2\int_0^{1/2} \lambda^{n-2} d\lambda \\ &= \frac{2}{(n-1)2^{n-1}} \end{aligned} $$ Now we note that the probability these points lie in a semicircle is just $$ p = \sum_{\{i,j\} \subset \{1,\ldots,n\}} p_{i,j} = \frac{n(n-1)}{2}p_{1,2} $$ which gives us $$p = n/2^{n-1}$$