Q:

Let \(n\) be given, \(n \geq 4\), and suppose that \(P_1, P_2,...,P_n\) are \(n\) randomly, independently and uniformly, chosen points on a circle. Consider the convex \(n\)-gon whose vertices are the \(P_i\). What is the probability that at least one of the vertex angles of this polygon is acute?

A:

We will need to begin with a few lemmas which will help us simply the problem.

Lemma:

A point forms the vertex of an acute angle if and only if all the other points lie in an open semicircle (in considering probabilities, we can always consider the closed semicircle as well, as the problem of any point lying on a boundary is easily solved by noting that it lies on that boundary with probability zero).

Proof:

Trivial, just note that, to form an angle less than a right angle, the closest two points to our vertex V (the point immediately clockwise and immediately counterclockwise) have to lie just past a diameter of the circle, which means they are in the same semicircle. If the two closest points are in the same semicircle, then it must be that the rest are as well, otherwise they would be closer to the vertex.

Lemma:

There can be at most two acute angles.

Proof:

I mostly convinced myself by drawing and considering quadrilaterals and right angles, but of course we can prove it if we are still unconvinced. First, if we consider the sum of the angles of an \(n\)-gon (in degrees), \(180(n-2)\), we see that if we have two acute angles, then we leave the total sum of the rest of the angles to be greater than \(180(n-2) - 180 = 180(n-3)\), which we have to distribute over \(n-2\) remaining angles. This works out OK. However, if we have three acute angles, then we leave the total sum of the remaining \(n-3\) angles to be greater than \(180(n-2) - 270 = 180(n-3.5)\), which we see is impossible, as that means that at least one angle would have to be larger than 180 degrees, which means our polygon is not convex.

EDIT: The above is actually incorrect, as \(n = 4\) is the cutoff for what I described above; \(180(n-2) - 360 = 180(n-4)\) would be the total sum of non-acute angles, and that obviously cannot be satisfied by \(n-4\) points. This raises no issue for three points, however. We’ll have to try something else!

Consider two acute angle vertices; \(P_1\) and \(P_2\). From our first lemma, we know that there exist semicircles \(S_1\) and \(S_2\) where no other points lie. \(S_1\) and \(S_2\) subdivide the circle into four regions: a region where no points lie (\(S_1 \cap S_2\)), a region where only \(P_1\) lies (\(S_2 \setminus S_1\)), a region where only \(P_2\) lies (\(S_1 \setminus S_2\)), and finally a region where all the other points lie (call this “\(R\)”, for rest). Consider a point, \(P_3\), that is the third acute angle vertex, lying in region \(R\). we must find a diameter that divides \(P_3\) from the rest of \(R\), but we find that any such diameter separates the circle into semicircles with \(S_2 \setminus S_1\) on one side and \(S_1 \setminus S_2\) on the other (and therefore \(P_3\) has to be in the same semicircle as either \(P_1\) or \(P_2\)). Thus, \(P_3\) cannot be acute for arbitrary \(P_3\), which means a third acute angle may not exist.

Lemma:

Any two acute angles’ vertices must be consecutive points, if they exist.

Proof:

Again, drawing this out should suffice. But consider 4 points, labelled in order, clockwise, \(P_1\), \(P_2\), \(P_3\), and \(P_4\), where \(P_1\) and \(P_3\) are the vertices of acute angles, ensuring that our acute angle vertices are not consecutive. Based on our first lemma, that would mean that, because \(P_1\) is acute, all of \(P_2\), \(P_3\), and \(P_4\) lie in the same semicircle, in that order going clockwise, and because \(P_3\) is acute, all of \(P_4\), \(P_1\), and \(P_2\) lie in the same semicircle, in that order going clockwise. But, for \(P_2\) and \(P_4\) to be in the same semicircle but in different orders, it must mean that \(P_2\) and \(P_4\) lie on a diameter. In the case of \(n = 4\), it must be that \(P_1\) and \(P_3\) form right angles with \(P_2\) and \(P_3\), which means they are not acute. In the case of \(n>4\), consider another point \(P_5\). Because \(P_2\) and \(P_4\) were arbitrarily chosen, it must mean that any such point \(P_5\) can considered as the point between \(P_1\) and \(P_3\) instead of \(P_2\), or, if between \(P_3\) and \(P_1\), instead of \(P_4\). Then this point also lies on the diameter formed by \(P_2\) and \(P_4\), which means that any such point must lie on the diameter, which again means that we must not have had acute angles in the first place.

Now, to find the answer to the original problem:

We want to compute this probability, which we can rewrite (in terms of \(X_i\), which is when \(P_i\) forms the vertex of an acute angle:

\(\mathbb{P}(\)At Least One Acute\() = \sum_i \mathbb{P}(X_i) - \sum_{ij} \mathbb{P}(X_i \cap X_j) + \sum_{ijk} \mathbb{P}(X_i \cap X_j \cap X_k) - ...\)

Here, we use our lemma to realize that all of the higher order terms involving three or more acute angles at once disappear, and for all the terms involving two acute angles we only need to consider the probability that two consecutive angles are acute.

\(\mathbb{P}(\)At Least One Acute\() = \sum_i \mathbb{P}(X_i) - \sum_{i} \mathbb{P}(X_i \cap X_{i+1}) = n \mathbb{P}(X_1) - n \mathbb{P}(X_1 \cap X_{2})\)

Finally, we can rewrite in terms of conditional probability:

\[n \mathbb{P}(X_1) - n \mathbb{P}(X_1 \cap X_{2}) = n \mathbb{P}(X_1) - n \mathbb{P}(X_2 \vert X_{1})\mathbb{P}(X_1) = n \mathbb{P}(X_1) (1 - \mathbb{P}(X_2 \vert X_{1}))\]

First, we find \(\mathbb{P}(X_1)\). Instead of considering \(P_1\), the vertex of the acute angle, it turns out to be easier to consider the point right before the vertex (here, before will mean counterclockwise, and after will mean clockwise). Fix \(P_0\), and draw a diameter through it. Once \(P_0\) is fixed, we have \(n-1\) points to choose from, and we want to place exactly one point, call this \(P_1\), in the semicircle clockwise from \(P_0\), and then the rest on the opposite side. So we have \(n - 1\) ways to choose our single point, and we choose the correct side \(n-1\) times, or \((\frac{1}{2})^{n-1}\). Thus, we have \(\mathbb{P}(X_1) = (n-1)(\frac{1}{2})^{n-1}\).

Next to find \(\mathbb{P}(X_2 \vert X_1)\), consider the case where we already have an acute angle whose vertex is \(P_1\), with \(P_0\) as above. Now consider also \(P_2\) and \(P_3\), the two points after \(P_1\). Because \(P_1\) is acute, we know that \(P_2\) and \(P_3\) are in the other semicircle. However, what we want to know is, if we set \(P_1\) to be the new \(P_0\) by drawing the diameter through it, what are the chances that it now includes \(P_2\) and only \(P_2\) (that is, the diameter stops before it includes \(P_3\) but after \(P_2\))? This would make \(P_2\) an acute angle vertex. Let us consider the point \(P_{-1}\) which is the opposite end of a diameter drawn through \(P_1\). If \(P_{-1}\) lies between \(P_2\) and \(P_3\), then we have that the diameter through \(P_1\) and \(P_{-1}\) separates \(P_2\) from the rest of the points. So, we want the probability of \(P_{-1}\) being between \(P_2\) and \(P_3\). \(n-2\) points gives us \(n-1\) intervals, and the chance we place \(P_{-1}\) in the right one is \(\frac{1}{n-1}\).

Thus, we have: \(n \mathbb{P}(X_1) (1 - \mathbb{P}(X_2 \vert X_{1})) = n (n-1)(\frac{1}{2})^{n-1}(1 - \frac{1}{n-1}) = n(n-1)(\frac{1}{2})^{n-1}(\frac{n-2}{n-1}) = n(n-2)(\frac{1}{2})^{n-1}\)