The probability that n random points inside a circle all lie within a sector of central angle θ

圆内随机n点在同一个圆心角为θ的扇形的概率 苏剑林 · 2022-10-25 · Mathematics probability competition random

A "four ducks share a semicircle" problem went viral online recently:

Four ducks share a semicircle problem

Quite a few readers probably tried it after seeing it, and even Teacher Li Yongle devoted an entire lecture to this problem (see "Four ducks in a circular pond all end up in the same semicircle — what's the probability?"]). As far as the problem itself goes, the answer isn't too hard, and there are many ways to work it out. What's slightly harder is its generalized version — which is what the title of this post describes — generalizing the number of ducks to $n$ and the semicircle to a sector with central angle $\theta$. Even more interestingly, when $\theta \leq \pi$ there's still a fairly elementary solution, but once $\theta > \pi$, the complexity "explodes"...more

Reformulating the problem

First, let's clarify that here we treat the ducks as points drawn uniformly at random inside a circle; we won't be considering generalizations such as "the footprint area of a duck." As for "four ducks share a semicircle," it's easy to generalize it, for instance by extending it to higher-dimensional space:

Given $n$ points drawn uniformly at random inside a $d$-dimensional hypersphere, what is the probability that they all lie within the same $d$-dimensional hyper-hemisphere?

This particular generalization was actually already answered in a 1962 paper, "A Problem in Geometric Probability"]. Another generalization is the one in the title of this post:

Given $n$ points drawn uniformly at random inside a circle, what is the probability that they all lie within a sector of central angle $\theta$?

This post is mainly about discussing this problem. It can also be equivalently transformed into (I leave it to the reader to figure out how):

Given $n$ points chosen uniformly at random on a circle, dividing the circle into $n$ arcs, what is the probability that the central angle subtended by the longest arc exceeds $2\pi - \theta$?

Further still, this can be equivalently transformed into:

Given $n-1$ points chosen uniformly at random on a unit-length segment, dividing the segment into $n$ pieces, what is the probability that the length of the longest piece exceeds $1 - \frac{\theta}{2\pi}$?

Solving the distribution

As it happens, the distribution involved in this last equivalent formulation has already been discussed quite thoroughly — for instance, in the Zhihu post "If n points are chosen uniformly at random in (0, 1), dividing the interval into n segments, what is the expected length of the longest segment?"]. To make things easier to follow, I'll reorganize the presentation and go through it step by step here. The whole process is a bit long, but it's necessary if we want a general solution (one that works for $\theta > \pi$).

As an aside, the maximum (or minimum) of multiple random variables falls under the category of "order statistics]," which also shows up quite often in machine learning — e.g., the nearest-neighbor estimator of entropy discussed in "EAE: Autoencoder + BN + Maximum Entropy = Generative Model"], and the general construction of discrete distributions discussed in "Constructing Discrete Probability Distributions from the Reparameterization Perspective"] — both can be reduced to this kind of problem.

Joint distribution

Starting from the last equivalent formulation, suppose a unit-length segment is divided by $n-1$ random points into $n$ pieces, with lengths $x_1,x_2,\cdots,x_n$ from left to right (note: this only fixes a direction, they are not sorted by size). Let the joint probability density function of these variables be $p_n(x_1,x_2,\cdots,x_n)$. The answer in the Zhihu link solves the problem directly based on the fact that "$p_n(x_1,x_2,\cdots,x_n)$ is uniformly distributed," but — whether I've missed some detail or failed to see through some subtlety — it seems to me that "$p_n(x_1,x_2,\cdots,x_n)$ is uniformly distributed" is not an obviously true statement, so let's derive it here from scratch.

First, note two facts:

1. $x_1,x_2,\cdots,x_n$ is subject to the constraint $x_1 + x_2 + \cdots + x_n = 1$, so it only has $n-1$ degrees of freedom; we take the first $n-1$ variables as the free variables;
2. $p_n(x_1,x_2,\cdots,x_n)$ is a probability density, not a probability — $p_n(x_1,x_2,\cdots,x_n)dx_1 dx_2 \cdots dx_{n-1}$ is the probability.

To understand why "$p_n(x_1,x_2,\cdots,x_n)$ is uniformly distributed," let's start from $n=2$. In this case we are simply choosing a single point uniformly at random on $(0, 1)$ that divides the segment into two parts. Since the point is drawn uniformly (density equal to 1), and the point is in one-to-one correspondence with $(x_1, x_2)$, we also have $p_2(x_1, x_2)=1$.

Next consider $n=3$, whose corresponding probability is $p_3(x_1, x_2, x_3)dx_1 dx_2$. There are two possible ways to arrive at this:

1. First sample a point that splits the segment into two pieces $(x_1, x_2 + x_3)$, with probability (density) $p_2(x_1, x_2 + x_3) dx_1$; then sample another point that splits the $x_2 + x_3$ piece into two pieces $(x_2, x_3)$, with probability (density) $dx_2$. Multiplying these gives $p_2(x_1, x_2 + x_3) dx_1 dx_2$;
2. First sample a point that splits the segment into two pieces $(x_1 + x_2, x_3)$, with probability (density) $p_2(x_1 + x_2, x_3) dx_2$; then sample another point that splits the $x_1 + x_2$ piece into two pieces $(x_1, x_2)$, with probability (density) $dx_1$. Multiplying these gives $p_2(x_1 + x_2, x_3) dx_1 dx_2$;

Adding the two together gives

\begin{equation}p_3(x_1, x_2, x_3)dx_1 dx_2 = p_2(x_1, x_2 + x_3) dx_1 dx_2 + p_2(x_1 + x_2, x_3) dx_1 dx_2 = 2dx_1 dx_2\end{equation}

which shows that $p_3(x_1, x_2, x_3)=2$ is also uniformly distributed. Proceeding by a similar recursion, we obtain

\begin{equation}p_n(x_1,x_2,\cdots,x_n) = (n - 1) p_{n-1}(x_1,x_2,\cdots,x_{n-1}) = \cdots = (n - 1)!\end{equation}

Marginal distribution

Now that we have the joint distribution, we can compute the marginal distribution of any chosen subset of $k$ variables — this is preparation for applying the "inclusion-exclusion principle" in the next section. Since the joint distribution is itself uniform, all the variables are fully symmetric, so without loss of generality we only need to compute the marginal distribution of the first $k$ variables.

By definition,

\begin{equation}p_n(x_1,x_2,\cdots,x_k) = \int \cdots \int p_n(x_1,x_2,\cdots,x_n) dx_{k+1}\cdots dx_{n-1}\end{equation}

Note the limits of integration: the lower limit is naturally $0$, but because of the constraint $x_1 + x_2 + \cdots + x_n = 1$, the upper limit differs for each variable — given $x_1,x_2,\cdots,x_i$, the value of $x_{i+1}$ can only range up to $0\sim 1 - (x_1 + x_2 + \cdots + x_i)$. So the precise form is

\begin{equation}\int_0^{1 - (x_1 + x_2 + \cdots + x_k)} \cdots \left[\int_0^{1 - (x_1 + x_2 + \cdots + x_{n-2})} p_n(x_1,x_2,\cdots,x_n) dx_{n-1}\right] \cdots dx_{k+1}\end{equation}

Since $p_n(x_1,x_2,\cdots,x_n)=(n-1)!$ is just a constant, the above can be integrated out term by term, giving the final result

\begin{equation}p_n(x_1,x_2,\cdots,x_k) = \frac{(n-1)!}{(n - k - 1)!}[1 - (x_1 + x_2 + \cdots + x_k)]^{n-k-1}\end{equation}

At this point we can compute the probability that $x_1,x_2,\cdots,x_k$ are simultaneously greater than a given threshold $c_1, c_2, \cdots, c_k$ (assuming $c_1 + c_2 + \cdots + c_k \leq 1$ holds):

\begin{equation}\begin{aligned} &\, \qquad P_n(x_1 > c_1,x_2 > c_2,\cdots,x_k > c_k) = \int_{c_1}^{1 - (c_2 + c_2 + \cdots + c_k)} \cdots \\ &\, \left[\int_{c_{k-1}}^{1 - (x_1 + x_2 + \cdots + x_{k-2} + c_k)}\left[\int_{c_k}^{1 - (x_1 + x_2 + \cdots + x_{k-1})} p_n(x_1,x_2,\cdots,x_k) dx_k\right]dx_{k-1}\right] \cdots dx_1 \end{aligned}\end{equation}

The upper limits of integration are derived in a manner similar to before, under the constraint $x_1 + x_2 + \cdots + x_n = 1$. Just as with $p_n(x_1,x_2,\cdots,x_n)$, this can also be integrated out term by term, and the final result turns out to be remarkably simple:

\begin{equation}P_n(x_1 > c_1,x_2 > c_2,\cdots,x_k > c_k) = [1 - (c_1 + c_2 + \cdots + c_k)]^{n-1}\end{equation}

Inclusion-exclusion principle

With everything now in place, it's time for the "inclusion-exclusion principle" to deliver the "final blow." Recall that our goal is to find the probability of the longest piece's length — that is, for a given threshold $x$, to compute $P_n(\max(x_1,x_2,\cdots,x_n) > x)$, where the event $\max(x_1,x_2,\cdots,x_n) > x$ itself is a union of multiple events:

\begin{equation}\max(x_1,x_2,\cdots,x_n) > x \quad\Leftrightarrow\quad x_1 > x \,\color{red}{\text{or}}\, x_2 > x \,\color{red}{\text{or}}\, \cdots \,\color{red}{\text{or}}\, x_n > x \end{equation}

The key point is that when $x < \frac{1}{2}$, these events are not mutually exclusive, so we cannot simply add up the probabilities of each part — we need the "inclusion-exclusion principle]":

\begin{equation}\begin{aligned} \text{exists a point greater than}x\text{probability of} = &\,\text{any one point greater than}x\text{sum of probabilities of} \\ &\,\quad \color{red}{-} \text{any two points greater than}x\text{sum of probabilities of} \\ &\, \quad\quad \color{red}{+} \text{any three points greater than}x\text{sum of probabilities of} \\ &\, \quad\quad\quad \color{red}{-} \text{any four points greater than}x\text{sum of probabilities of} \\ &\, \quad\quad\quad\quad \color{red}{+} \cdots \end{aligned}\end{equation}

By the result of the previous section, the probability that all points in a chosen subset of $k$ points exceed $x$ is $(1-kx)^{n-1}$, and the number of ways to choose $k$ points is $C_n^k$. Substituting these into the equation above gives

\begin{equation}\begin{aligned} P_n(\max(x_1,x_2,\cdots,x_n) > x) =&\, \sum_{k=1, 1 - kx > 0}^n (-1)^{k-1} C_n^k (1-kx)^{n-1} \\ =&\, C_n^1 (1 - x)^{n-1} - C_n^2 (1 - 2x)^{n-1} + \cdots \end{aligned}\end{equation}

Analyzing the answer

For the problem at the start of this post, i.e., $x = 1 - \frac{\theta}{2\pi}$, when $x > \frac{1}{2}$ (i.e., $\theta < \pi$), all the subsequent terms $1 - k x$ become negative and hence don't actually exist, so the answer is the simplest possible:

\begin{equation}C_n^1 (1 - x)^{n-1} = n \left(\frac{\theta}{2\pi}\right)^{n-1}\end{equation}

When $x < \frac{1}{2}$, the number of terms we need to add or drop depends on the exact size of $x$: the smaller $x$ is, the relatively more terms there are. This is exactly what Teacher Li Yongle's article meant by "once $\theta$ exceeds 180 degrees, things get very complicated."

We can also compute its expectation, which is the question discussed in the Zhihu thread. There's also an interesting special case: clearly when $x < \frac{1}{n}$, we always have $1 - kx > 0$, meaning every single term must be used:

\begin{equation}P_n(\max(x_1,x_2,\cdots,x_n) > x) = \sum_{k=1}^n (-1)^{k-1} C_n^k (1-kx)^{n-1}\end{equation}

However, by the "pigeonhole principle," we know that once a unit-length segment is divided into $n$ pieces, the longest piece must have length at least $\frac{1}{n}$. This means $P_n(\max(x_1,x_2,\cdots,x_n) > \frac{1}{n}) = 1$, and therefore, when $x < \frac{1}{n}$, it must be the case that

\begin{equation}\sum_{k=1}^n (-1)^{k-1} C_n^k (1-kx)^{n-1} = 1\end{equation}

Moreover, since the left-hand side is simply a plain algebraic polynomial, it must be analytic, and so the identity above must actually hold for all $x$. Readers who are curious are welcome to try proving this directly from a purely algebraic point of view.

Summary

This post discussed a general solution to the generalized "four ducks share a semicircle" problem, the main idea being the inclusion-exclusion principle.