5
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ Assuming the circle has perimeter $1$ and fixing one point, then selecting the other $n-1$ points is the same as selecting $x_n \in (0,1)$. You then want $x_1=0$ and $x_2 + \cdots+ x_n \ge 1/2$. $\endgroup$ – lhf May 18 '18 at 14:28
  • $\begingroup$ Is it as simple as $P = (1/2)^{n-1}$? I'm looking at it as randomly placing points on the circumference one after the other. The 1st and 2nd point can go anywhere except for being diametrically opposite (assuming a side cannot go through the center). The next point can go anywhere along an arc which extends from the 1st point to the 2nd point and on to a semi-circle length, and from the 2nd point to the 1st point and on to another semi-circle length in that direction. Being longer than a semi-circle it would be higher than p = 1/2 for the placement of the next point and so forth. $\endgroup$ – Phil H May 18 '18 at 14:50
7
$\begingroup$

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}}$

$\endgroup$
  • $\begingroup$ Good answer, that addresses the issue of the probability being higher if it's any semi-circle rather than a specific one. $\endgroup$ – Phil H May 18 '18 at 15:22
0
$\begingroup$

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}}$.

$\endgroup$
  • $\begingroup$ I think you've calculated the opposite of what's asked in the question $\endgroup$ – qwerty_uiop May 18 '18 at 14:54
  • $\begingroup$ oh right. Thank you. I have edited. $\endgroup$ – Ben May 18 '18 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.