Probability that polygon formed by n points on a circle contain the center of the circle?

Question

I have seen similar questions being asked on this forum, but couldn't find this exact problem.

So there are n points selected uniformly randomly on a circle. What is the probability that the polygon of these n points contains the center of the circle?

Now, taking cue from a similar question of probability that all these n points lie within a semicircle,

Suppose we mark the bottom most point of the circle as zero. From there on, we move to the right and find the first point, lets say point i, at a distance x along the circumference.

Now, the probability that the next n-1 points lie within the arc length $(x, x+\frac12)$ is $P = { (\frac { 1 }{ 2 } ) }^{ n-1 }$, which is the probability that these n points lie within a semicircle. The probability that they don't lie in the same semicircle then becomes $1-P.$

Clearly, if these n points lie within a semicircle, their polygon doesn't contain the center of the circle.

Next, the point i could be any of those n points. So we need to account for all the n possibilities being the first point. But, should the final probability be $1-nP$, or $n(1-P)$?

Answer 1

The answer is $1-nP = 1-\frac{n}{2^{n-1}}$. You can see this as follows:

Select and fix a direction around the circle (clockwise or counterclockwise). For the $i$-th point $X_i$ selected, what is the probablity that all the other points are not inside the semi-circle started by $X_i$ and in the selected direction? The answer is $P=\frac1{2^{n-1}}$. If that is the case, then the center of the circle does not lie inside the polygon.

Conversely, if the center of the circle does not lie inside the polygon, there must be a pair of 'consecutive' (in the chosen direction around the circle) points who are more than a semi-circle away (in that direction). The first one of the them fills the role of the point $X_i$ above.

To sum up, the center of the circle does not lie inside the polygon iff there exists a point $X_i$ such that all the other points are not inside the semi-circle started by $X_i$ and going in the chosen direction.

We also known the probability for that event, if we chose the index $i$ beforehand: $P=\frac1{2^{n-1}}$

To get the probability that this happens for any $i$, we apply the principle of inclusion and exclusion.

The good thing is the formulas get really easy, because the probability that the event happens for more than one index is zero! That would imply two different non-overlapping (at most touching at the end) segments without any chosen points inside, that are both longer than a semi-circle. That can't happen, of course.

That means the probability that for any index $i$ the point $X_i$ starts an 'empty' semi-circle is just the sum of all the single probabilities, namely $\frac{n}{2^{n-1}}$.

Since you are looking for the opposite event, the probability you seek is $1-\frac{n}{2^{n-1}}$

Answer 2

Assume the radius of the circle is one. $A=P(\text{convexchull of n points does not contain the center})=P(\text{all points lie in an arc of length less than $\pi$})$. Suppose we have $n$ points now. We first order them clockwisely and Let the points be $P_1,P_2,...,P_n$. Then $\{\text{all points lie in an arc of length less than $\pi$}\}=\cup_{i=1}^{n} A_i$ where $A_i=\{\text{the angle between $P_j$ and $P_i$ is lesser or equal to $\pi$ clockwisely for all $j$}\}$. And $P(A_i)=\frac{1}{2^{n-1}}$. And $A_1,A_2,...,A_n$ are pairwisely disjoint so $P(A)=\sum_{i=1}^{n}P(A_i)=\frac{n}{2^{n-1}}$. So the answer is $1-P(A)=1-\frac{n}{2^{n-1}}$.