A Triangle, A Tetrahedron, And A Circle’s Centre

Riddler Express

Choose three points on a circle uniformly at random and connect them to form a triangle. What is the probability that the centre of the circle lies inside that triangle?

The Riddler, FiveThirtyEight, January 12, 2018(original post)

Solution

The idea. A triangle with all three vertices on a circle contains the centre $O$ if and only if no semicircle bounded by a diameter of the circle contains all three vertices on the same side. Equivalently, none of the three arcs cut out by the vertices is longer than a semicircle. We use a symmetry that turns the random angular positions into a simple paired-endpoint count.

The pairing argument. Pick the three vertices in two stages: first pick three diameters of the circle uniformly at random, then for each diameter independently flip a fair coin to choose one of its two endpoints. The three vertices so produced are uniform on the circle, and the joint distribution is the same as picking three independent uniform points.

For any fixed choice of three diameters, the eight $\pm$ coin-flip patterns produce eight candidate triangles. Among those eight, exactly one contains the centre. To see this, label the three diameters by their two endpoints $A/A'$, $B/B'$, $C/C'$. The triangle $ABC$ contains $O$ if and only if the three vertices are not all on one side of any line through $O$; among the eight sign patterns one always achieves this and its antipode (flipping all three signs) gives the same triangle reflected through $O$. The eight patterns split into four geometric triangles (each pattern and its sign-flipped twin produce the same triangle), of which exactly one encloses $O$.

So conditional on the three diameters, the probability is $1/4$; since this holds for every choice of diameters, the answer is $$\boxed{\,P = \tfrac{1}{4} = 25\%.\,}$$

(A second route: with three vertices on the circle at angles $\theta_1, \theta_2, \theta_3$ on the circumference, the triangle contains $O$ iff every arc between consecutive vertices is less than half the circle. Sort the three angles; the three arc lengths are $u_1, u_2, u_3$ with $u_1 + u_2 + u_3 = 1$ on a unit-circumference circle, uniformly distributed over the simplex. The triangle contains $O$ iff $\max u_i < 1/2$, and by inclusion-exclusion that probability is $1 - 3 \cdot (1/2)^2 = 1/4$.)

The computation

Encode the actual experiment: sample three uniform angles on the unit circle, build the triangle, and check whether the origin lies inside it.

1. Sample three angles $\theta_1, \theta_2, \theta_3$ uniformly on $[0, 2\pi)$.

2. Sort them and compute the three arc gaps.

3. Count the trial as a success if the largest gap is less than $\pi$.

import numpy as np
rng = np.random.default_rng(0)

N = 200_000
theta = np.sort(rng.random((N, 3)) * 2 * np.pi, axis=1)
gaps = np.diff(theta, axis=1)
wrap = 2 * np.pi - (theta[:, 2] - theta[:, 0])
max_gap = np.maximum.reduce([gaps[:, 0], gaps[:, 1], wrap])
print((max_gap < np.pi).mean())                          # ~0.25

The script prints $\approx 0.25$ over $200{,}000$ trials, confirming the boxed answer.

Riddler Classic

Choose four points uniformly at random on the surface of a sphere. What is the probability that the tetrahedron with those four points as vertices contains the centre of the sphere?

The Riddler, FiveThirtyEight, January 12, 2018(original post)

Solution

The same pairing argument as the Express, one dimension up.

Setup. Sample four vertices on the unit sphere by picking four diameters of the sphere uniformly at random and then, independently for each, flipping a fair coin to choose one of the two endpoints. The vertices so produced are uniform on the sphere.

For any fixed choice of four diameters, the $2^4 = 16$ coin-flip patterns produce $16$ candidate tetrahedra. Among these $16$, exactly one contains the centre $O$. The argument is the same flag-of-half-spaces argument as before: the tetrahedron $V_1 V_2 V_3 V_4$ contains $O$ iff there is no half-space through $O$ containing all four vertices on its side; for each choice of diameters, exactly one assignment of endpoint signs leaves $O$ strictly inside, and the antipodal sign-flip produces the same tetrahedron reflected. The $16$ patterns split into $8$ tetrahedra (each pattern and its antipode are the same shape), exactly one of which contains $O$.

Hence conditional on the diameter choice, the probability is $1/8$, and since this holds for every choice of diameters, $$\boxed{\,P = \tfrac{1}{8} = 12.5\%.\,}$$

(In dimension $d$, the probability that the simplex on $d + 1$ uniformly random points on $S^{d-1}$ contains the centre is $1/2^d$. This is Wendel’s $1962$ theorem; the $d = 2$ and $d = 3$ cases are the Express and Classic of this column.)

The computation

Sample four uniform points on the unit sphere, then test whether the origin lies inside the tetrahedron they span. The origin is inside iff there exist barycentric weights $w_1, \ldots, w_4 \ge 0$ summing to $1$ with $\sum w_i V_i = 0$; equivalently, solving the linear system $$\begin{bmatrix} V_1 & V_2 & V_3 & V_4 \\ 1 & 1 & 1 & 1 \end{bmatrix} w = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$ and checking $w_i \ge 0$ for all $i$.

1. Sample $4N$ standard-normal $\mathbb{R}^3$ vectors and normalise to get four points per trial.

2. For each trial, solve the $4 \times 4$ system above for the barycentric weights.

3. Count the trial a success if all four weights are non-negative.

import numpy as np
rng = np.random.default_rng(0)

N = 100_000
v = rng.standard_normal((N, 4, 3))
v /= np.linalg.norm(v, axis=2, keepdims=True)
M = np.concatenate([v.transpose(0, 2, 1),
                    np.ones((N, 1, 4))], axis=1)
rhs = np.broadcast_to(np.array([0, 0, 0, 1.0]),
                      (N, 4))[..., None]
w = np.linalg.solve(M, rhs)[..., 0]
print((w >= 0).all(axis=1).mean())                       # ~0.125

The script prints $\approx 0.125$ over $100{,}000$ trials, confirming the boxed answer.