## probability puzzles

hard | probability |

N points are chosen at random on the circumference of a circle. A convex $n$-gon (n sided polygon) is drawn by joining these n points. What is the probability that the center of circle lies inside the region of $n$-gon?

If the polygon contains the center, the longest distance between any two points on the circumference will be less than $\pi$.

$1- nP$ where $P = 1/{2^{n-1}}$

For a polygon inscribed in a circle to exclude the center of that circle, there must be a straight line that can be drawn through the center of the circle such that all vertices (points) of the polygon are on one side of that line. In terms of the circle, this line is a diameter, and all the points are within a semi-circle. Thus, the polygon excludes the center **if and only if** all points are within a semi-circle. This is easier to check.

Suppose we lock the first point (at random), imagine a semi-circular arc that starts from this point, in a clockwise direction around the circle. We want to know if the next $n-1$ points lie on this arc. Since the probability of each next point is uniformly random along the entire circumference, the probability is $1/2$ that each point lies within this imaginary semi-circle. Thus, the probability that all those $n-1$ points lie on this semi-circle is $P = \dfrac{1}{2} \cdot \dfrac{1}{2} \cdot ... \cdot \dfrac{1}{2} =\dfrac1{2^{n-1}}$.

Not all points may lie within the semi-circle starting from the first point. It is true that if the polygon excludes the center, then certainly all points are within some semi-circle, but which one? Let us define the semi-circle as an arc that starts from some point of the polygon in a clockwise direction. This definition ensures that only one such semi-circle can satisfy the desired constraints. Suppose $X_i = 1$ if the semi-circle starting from point $i$ contains all the other points, and $X_i = 0$ otherwise. Then, $P(X_1 = 1) = P$.

Note that the probability of this event is identical for each $i$ because when we observe the semi-circle starting from the $i$th point, all the other $n-1$ points are just random points on the circumference, hence $P(X_1 = 1) = P(X_i = 1) = P(X_n = 1) = P$.

We want to know the probability that any one of those start-points satisfies the condition, i.e. $P(X_1 = 1 \cup X_2 = 1 \cup ... \cup X_n = 1)$.

Note that if any $X_i$ is $1$, then all other $X_i$'s are $0$. This is because of the way we defined our semi-circle to start from one of the points. If we start the semi-circle for any other point $j \ne i$, then the $i^{th}$ point lies outside the semi-circle, i.e. $X_{i}=1 \implies X_{j} = 0, \forall j \ne i$. Hence, by definition, $(X_i = 1)$'s are disjoint events, and hence the probability of union is the sum of individual probabilities.

Thus, probability of center-exclusion = $P(X_1 = 1 \cup X_2 = 1 \cup ... \cup X_n = 1) = P(X_1 = 1) + ... + P(X_n = 1) = n * P$

Hence the probability that the polygon includes the center of the circle is $1 - nP$ where $P = \dfrac{1}{2^{n-1}}$

Final answer $1-\dfrac{n}{2^{n-1}}$