The probability that a triangle contains the origin - in any number of dimensions

Posted January 14, 2018

FiveThirtyEight's Riddler this week featured two geometry problems. The Riddler Express was a puzzle in two dimensions. Here's the puzzle:

Choose three points on a circle at random and connect them to form a triangle. What is the probability that the center of the circle is contained in that triangle?

The Riddler Classic, from Ben Weiss, was the analogous puzzle in three dimensions:

Choose four points at random (independently and uniformly distributed) on the surface of a sphere. What is the probability that the tetrahedron defined by those four points contains the center of the sphere?

While we are at it, we can ask the same question in any number of dimensions. Let's see how.

In two dimensions, we start with a circle, and in three dimensions, we start with a sphere. In \(n\) dimensions, we will start with \(S^{n - 1}\) (but we'll just call it a sphere), which is the boundary of an \(n\)-dimensional ball. Specifically, \(S^{n - 1}\) is the set of all points in \(n\) dimensional space that are distance 1 from the origin.

In two dimensions, we choose 3 points, which are the vertices of a triangle. In three dimensions, we choose 4 points, which are the vertices of a tetrahedron. In \(n\) dimensions, we will choose \(n + 1\) points. The figure that has these \(n + 1\) points as its vertices is called a simplex.

So, the \(n\)-dimensional version of this problem is:

Let \(n\) be a positive integer. Choose \(n + 1\) points at random (independently and uniformly distributed) from \(S^{n - 1}\). What is the probability that the simplex determined by those \(n + 1\) points contains the origin?

Below, I have a solution for both the two- and three-dimensional puzzles, as well as in general for the \(n\)-dimensional puzzle. For the two-dimensional problem in the Riddler Express, the probability is \(\frac{1}{4}\); for the three-dimensional problem in the Riddler Classic, the probability is \(\frac{1}{8}\); and in general for the \(n\)-dimensional problem, the probability is \(\frac{1}{2^n}\).

The first two puzzles are special cases of the third, so from now on, we will just discuss the \(n\)-dimensional problem. But here is a table for translating between 2, 3, and \(n\) dimensions:

Transforming the problem: focus on antipodal points.

We will look at a related problem about antipodal points. For a point on a sphere, its antipode is the point directly across the sphere. That is, if you happen to be standing on Earth right now, your antipode is the point where you'd end up if you dug a hole straight down through the center of the Earth and popped out the other side.

If we have \(n + 1\) points in \(n\)-dimensional space, those points are in general position if there is no \(n - 1\) dimensional subspace that contains those points.

Here's the related problem that we will solve in the next section:

Start with any (pre-set) \(n + 1\) points on \(S^{n - 1}\) in general position. Replace each point with its antipode with probability \(\frac{1}{2}\), independently for each point. What is the probability that the simplex defined by these points contains the origin?

The answer is \(\frac{1}{2^n}\), regardless of the points we start with. We will solve this problem in the next section. And here's why solving this problem resolves the original puzzle. The original puzzle asks us to choose our points uniformly and independently. Let's divide that into a two-step process:

1. Choose \(n + 1\) points uniformly and independently at random from the sphere in \(n\)-dimensional space.
2. For each point (independently), replace the point with its antipode with probability \(\frac{1}{2}\).

This two-step process is overly complicated (a simpler process would be to stop after step 1), but it works. And our solution to the modified problem tells us that if we know what happens in step 1, then as long as the chosen points are in general position, the probability that the simplex contains the origin is \(\frac{1}{2^n}\). And, the chosen points are in general position with probability 1, so we can ignore the case where they are not. So, even without knowing what happens in step 1, we can still say that the probability that the simplex contains the origin is \(\frac{1}{2^n}\).

Solving the modified problem with linear algebra

We will solve the modified problem above. Let \(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_{n + 1}\) be the \(n + 1\) points on \(S^{n + 1}\) that we start with. For each \(1 \leq i \leq n + 1\), let \(\varepsilon_i\) be \(-1\) if \(\mathbf{u}_i\) gets replaced by its antipode, and \(1\) otherwise. Let \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_{n + 1}\) be the points that we end up with after the replacements. These are the vertices of the simplex. If we think of each point as an \(n\)-dimensional vector, then each \[ \mathbf{v}_i = \varepsilon_i \mathbf{u}_i. \]

A point is in the simplex if and only if it is a convex combination (a weighted average) of the vertices. That is, a point \(\mathbf{x}\) is in the simplex if and only if there are nonnegative real numbers \(s_1, s_2, \dots, s_{n + 1}\) such that \(s_1 + s_2 + \dots + s_{n + 1} = 1\), and \[ s_1 \mathbf{v}_1 + s_2 \mathbf{v}_2 + \dots + s_{n + 1} \mathbf{v}_{n + 1} = \mathbf{x}. \]

Since \(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_{n + 1}\) are \(n + 1\) points in general position in \(n\) dimensional space, they span the whole space. And furthermore, the set of vectors \[ \mathbf{r} = (r_1, r_2, \dots, r_{n + 1}) \] such that \[ r_1 \mathbf{u}_1 + r_2 \mathbf{u}_2 + \dots + r_{n + 1} \mathbf{u}_{n + 1} = \mathbf{0} \] is a one-dimensional vector space. Thus, there are exactly two vectors \(\mathbf{r}\) that satisfy the above equation and also \[ \newcommand{abs}[1]{\lvert #1 \rvert} \abs{r_1} + \abs{r_2} + \dots + \abs{r_{n + 1}} = 1. \] Call one of these two vectors \(\hat{\mathbf{r}} = (\hat{r}_1, \hat{r}_2, \dots, \hat{r}_{n + 1})\). The other one is \(-\hat{\mathbf{r}}\). So, the only solutions for \(s_1, s_2, \dots, s_2\) to the equation \[ s_1 \mathbf{v}_1 + s_2 \mathbf{v}_2 + \dots + s_{n + 1} \mathbf{v}_{n + 1} = \mathbf{0} \] with \(\abs{s_1} + \abs{s_2} + \dots + \abs{s_{n+1}} = 1\) are \[ s_i = \epsilon_i \hat{r}_i \text{ for all } i, \] and \[ s_i = - \epsilon_i \hat{r}_i \text{ for all } i. \] The origin is in the simplex if there is a solution for \(s_i\) in which all the \(s_i\) are positive. In other words, the origin is in the simplex if and only if either

• \(\epsilon_i\) has the same sign as \(\hat{r}_i\) for all \(i\), or
• \(\epsilon_i\) and \(\hat{r}_i\) have a different sign for all \(i\).

Since each of the \(n + 1\) different \(\epsilon_i\) is chosen randomly and independently, and is equally likely to be positive or negative, the probability that one of these two situations occurs is \(\frac{2}{2^{n + 1}} = \frac{1}{2^n}\).