What are the Odds of Forming Polygons by Accident?
Overview
For a stick of unit length, we would like to randomly choose $n-1$ independently and identically distributed (possibly coinciding) points and determine the probability that the resulting $n$ line segments (of possibly zero length) would form a non-degenerate, simple polygon. 1That is, a polygon that does not intersect itself and has no holes. We must have $n \ge 3$ since the triangle is the smallest feasible polygon.
More precisely, let $X_1, \ldots, X_{n-1}$ be $[0,1]$-valued independent random variables indicating the position of the sampled points. Each of the $X_i$’s are identically distributed having a law determined 2It is uniquely determined due to the Carathéodory Extension Theorem. by a cumulative distribution function $F$. Denote the end points of the interval by $X_0 := 0$ and $X_n := 1$.
Definition
Equivalently, we could say a valid simple $n$-gon is formed under $F$ if the maximum piece length is strictly less than $1/2$. This is a generalised polygon inequality where strictness avoids the degenerate case when the polygon collapses into a line.
Alternative view of generalised polygon inequality.
Taking this circular deformation of the unit interval gives us an equivalent view of when the generalised polygon inequality is not satisfied; i.e. when all the $X_i$’s lie on a semicircle containing $O$.
Theorem
For any distribution $F$ on $[0,1]$, let
$$ a(x) := \Prob(X_1 < x) + \Prob\!\left(X_1 \ge x + \frac{1}{2}\right), \qquad b(x) := \Prob(X_1 \le x) + \Prob\!\left(X_1 \ge x + \frac{1}{2}\right). $$Splitting $F = F_c + F_d$ into its continuous and discrete components, the probability that a polygon is formed under $F$ is
$$ \begin{split} 1 - b(0)^{n-1} &- (n-1) \int_{(0, \frac{1}{2}]} a(x)^{n-2} \, dF_c(x) \\ &- \sum_{x \in (0, \frac{1}{2}] \cap \cA(d) } [b(x)^{n-1} - a(x)^{n-1}], \end{split} $$where $\cA(F) = \cA(F_d)$ is the countable set of atoms of $F$. In particular, when $F$ is continuous, $a(x) = b(x) = 1 + F(x) - F(x + \frac{1}{2})$ and this reduces immediately to
$$ 1 - \Bigl[ 1 - F\!\left(\tfrac{1}{2}\right) \Bigr]^{n-1} - (n-1) \int_{0}^{1/2} \left[ 1 + F(x) - F\!\left(x + \frac{1}{2}\right) \right]^{n-2} dF(x). $$Proof. In fact, we can analyse the polygon inequality by smoothly deforming the unit interval so that the end points $X_0$ and $X_n$ join to form a circle. Identify the points $X_0$ and $X_n$ on the circle 3The specific choice of transformation is irrelevant, provided it preserves distances, forms a closed loop and remains a homeomorphism right up to the point $O$ where the loop is punctured. and call it $O$. We adopt the convention that co-ordinates increase in the clockwise direction.
For $x \in [0, \frac{1}{2}]$, let
- $\cS(x) = [0, x] \cup [x + \frac{1}{2}, 1]$ and
- $\cS^\circ(x) = [0, x) \cup [x + \frac{1}{2}, 1]$.
Respectively, they are the semicircles whose trailing edge is closed and whose leading edge is closed (resp. open) at $x$.
The elegance of this viewpoint is that the generalised polygon inequality is transgressed whenever all the points $X_1, \ldots, X_{n-1}$ belong to a semicircle containing $O$. This happens when either of the following mutually exclusive events occur:
- Event $A$. No $X_i$ falls in $(0, \frac{1}{2})$ (i.e. all the $X_i$’s belong to $\cS(0) = \{0\} \cup [\frac{1}{2}, 1]$; or
- Event $B$. All the $X_j$’s belong to a semicircle with trailing edge in $(0, \frac{1}{2}]$.
NB: We have paid careful attention to the endpoints since our result allows for discrete distributions.
Letting $F$ denote the distribution function of $X_1$, we get
$$ \Prob(\text{Polygon formed}) = 1 - \Prob(A \cup B) = 1 - \Prob(A) - \Prob(B) $$where the last equality follows from mutual exclusivity.
Now, since the $X_i$’s are i.i.d.
$$ \Prob(A) = \Prob\Biggl(\bigcap_{j=1}^{n-1} \big\{X_j \in \cS(0) \big\}\Biggr) = \Bigl[ \Prob\Big( X_1 \ge \frac{1}{2} \Big) + \Prob(X_1 = 0) \Bigr]^{n-1}. $$Computing $\Prob(B)$ is a little bit more involved. To this end, if we view the circle as a clock face with $\frac{1}{2}$ at 12 o’clock, $O$ at 6 o’clock, and co-ordinates increasing in the clockwise direction, let $X^*_i$ be the value of a clockwise-most cut. Denote by $I$ the index set
$$ I := \{ i \in \{1, \ldots, n-1\} \, | \, X_i = X^*_i\} $$and let $i^*$ be the smallest element of $I$. Then, by the law of total probablility,
$$ \begin{aligned} \Prob(B) &= \Prob\Biggl( \Bigl\{ X_i \in \cS(X_{i^*}) \;\;\forall i \neq i^*, \; X_{i^*} \in (0, 1/2] \Bigr\} \Biggr) \\ &= \sum_{j = 1}^{n-1}\Prob\Biggl( \Bigl\{ X_i \in \cS(X_j) \;\;\forall i \neq j, \; X_j \in (0, 1/2], \; j = i^* \Bigr\} \Biggr) \\ &= \sum_{j=1}^{n-1} \int_{(0, \frac{1}{2}]} \prod_{i < j} \Prob\bigl(X_i \in \cS^\circ(x)\bigr) \times \prod_{i > j} \Prob\bigl(X_i \in \cS(x)\bigr) \, dF(x) \\ &= \sum_{j=1}^{n-1} \int_{(0, \frac{1}{2}]} \Bigl[\Prob \bigl(X_1 \in \cS^\circ(x)\bigr) \Bigr]^{j-1} \times \Bigl[ \Prob\bigl(X_1 \in \cS(x)\bigr)\Bigr]^{n - 1 - j} \, dF(x) \\ &= \sum_{j=1}^{n-1} \int_{(0, \frac{1}{2}]} \Bigl[ \Prob(X_1 < x) + \Prob\Big(X_1 \ge x + \frac{1}{2}\Big) \Bigr]^{j-1} \times \Bigl[ \Prob(X_1 \le x) + \Prob\Big(X_1 \ge x + \frac{1}{2}\Big) \Bigr]^{n - 1 - j} \, dF(x) \\ &= \int_{(0, \frac{1}{2})} \sum_{j=1}^{n-1} a(x)^{j-1} b(x)^{n-1-j} \, dF(x). \end{aligned} $$By the Lebesgue decomposition theorem we can split $F = F_c + F_d$ into its continuous and discrete (purely atomic) components. Hence
$$ \begin{aligned} \Prob(B) = \int_{(0, \frac{1}{2})} \sum_{j=1}^{n-1} a(x)^{j-1} b(x)^{n-1-j} \, (dF_c + dF_d)(x). \end{aligned} $$Observe that
$$\sum_{j=1}^{n-1} a(x)^{j-1} b(x)^{n-1-j} = \begin{cases} (n-1) a(x)^{n-2}, & \text{if } \mathbb{P}(X_1 = x) = 0, \\ \dfrac{b(x)^{n-1} - a(x)^{n-1}}{\mathbb{P}(X_1 = x)}, & \text{if } \mathbb{P}(X_1 = x) > 0. \end{cases}$$since $b(x) - a(x) = \Prob(X_1 = x)$. The first case happens on the continuous component $F_c$ and the latter on the jumps of $F_d$. Let $\cA(F_d)$ be the set of atoms of $F_d$ Thus,
$$ \Prob(B) = \int_{(0, \frac{1}{2})} (n -1) a(x)^{n-2} \, dF_c(x) + \sum_{x \in (0, \frac{1}{2}] \cap \cA(F_d) } [b(x)^{n-1} - a(x)^{n-1}]. $$Putting this altogether we get the desired result.
■
Examples #
Uniform distribution #
Consider
$$ F(x) = \frac{4}{\pi} x \, \mathbb{1}_{\left\{ x < \frac{\pi}{4} \right\}} + \mathbb{1}_{\left\{ x > \frac{\pi}{4} \right\}}, \quad x \in [0,1]. $$This special case models the situation where all the probability mass is uniformly distributed on the interval $\left[0, \frac{\pi}{4}\right]$ (with density $f(x) = \frac{4}{\pi}$), saturating to $F(x) = 1$ for $x > \frac{\pi}{4}$.
$$ \begin{aligned} &(n-1) \int_{0}^{1/2} \left[ F(x) + 1 - F\left(x + \frac{1}{2}\right) \right]^{n-2} dF(x) \\ &\quad= (n-1) \left( \int_{0}^{\frac{\pi}{4} - \frac{1}{2}} \left( 1 - \frac{2}{\pi} \right)^{n-2} \frac{4}{\pi} \, dx + \int_{\frac{\pi}{4} - \frac{1}{2}}^{1/2} \left( \frac{4}{\pi} x \right)^{n-2} \frac{4}{\pi} \, dx \right) \\ &\quad= (n-1) \left[ \left( 1 - \frac{2}{\pi} \right)^{n-1} + \left( \frac{4}{\pi} \right)^{n-1} \frac{1}{n-1} \left( \frac{1}{2^{n-1}} - \left( \frac{\pi}{4} - \frac{1}{2} \right)^{n-1} \right) \right] \end{aligned} $$More generally, consider
$$X \sim U(a, b) \text{ with support length } b - a > \frac{1}{2}.$$$$ \text{Let } \mathcal{I} \coloneqq (n-1) \int_{0}^{1/2} \left[ F(x) + 1 - F\left(x + \frac{1}{2}\right) \right]^{n-2} dF(x). $$$$ \text{Now, for } x \in \left(0, \frac{1}{2}\right): \begin{aligned} 1 - F\left(x + \frac{1}{2}\right) &= 1 - \frac{x + \frac{1}{2} - a}{b - a} \, \mathbb{1}_{\left\{ x + \frac{1}{2} < b \right\}} - \mathbb{1}_{\left\{ x + \frac{1}{2} > b \right\}} \\ &= \left( 1 - \frac{x + \frac{1}{2} - a}{b - a} \right) \mathbb{1}_{\left\{ x < b - \frac{1}{2} \right\}}. \end{aligned} $$$$ \begin{aligned} \therefore \mathcal{I} &= (n-1) \left[ \int_{a}^{b - \frac{1}{2}} \left( \frac{x - a}{b - a} + 1 - \frac{x + \frac{1}{2} - a}{b - a} \right)^{n-2} \frac{1}{b - a} \, dx + \int_{b - \frac{1}{2}}^{1/2} \left( \frac{x - a}{b - a} \right)^{n-2} \frac{1}{b - a} \, dx \right] \\ &= (n-1) \left[ \left( \frac{b - a - \frac{1}{2}}{b - a} \right)^{n-1} (b - a)^{1 - n} + \frac{1}{n-1} \left( \left( \frac{1}{2} - a \right)^{n-1} - \left( b - a - \frac{1}{2} \right)^{n-1} \right) \right] \end{aligned} $$$$ \text{For the boundary term } \mathcal{II} \coloneqq \left[ 1 - F\left(\frac{1}{2}\right) \right]^{n-1}: \begin{aligned} \mathcal{II} &= \left( \frac{b - \frac{1}{2}}{b - a} \right)^{n-1}. \end{aligned} $$