Why You Should Never Buy High Dimensional Watermelons

I was recently reading The Art of Doing Science and Engineering by Richard Hamming (Hamming, 2020). In Chapter 9 he argues that most design problems scientists deal with involve working in $n$-dimensional space. Even though I deal with optimization and machine learning problems which can have very large number of parameters on a regular basis, Hamming’s book made me realize that I don’t have a great grasp on high dimensional objects. I may be able to visualize something in 3 dimensions, but as soon as I have to work on 4 I have to stop relying on visualization and must resort to using algebra, trigonometry, etc.

In this blog post I will show that indeed, high dimensional objects are hard to reason about by exploring the following question: What fraction of the total volume of an n-dimensional sphere lies in its shell?

I found the answer to be at odds with my intuition, hence this blog post.

The Volume of $n$-dimensional Spheres

We are concerned with computing the volume of high dimensional spheres. Before we dive into the details lets establish some notation. Let $n = 1, 2, …$ be the dimension of the space we are working in. Let $S_n(r) = \{x \in \mathbb{R}^n: \|x\| _2 = r\}$ be the $n$-dimensional sphere, $V_n$ be the volume enclosed by the sphere, and $A_n$ be its surface area.

Before we venture onto high dimensions lets review what we know in 1, 2, and 3 dimensions. In 1 dimension, $V_1(r)$ is just the length of the line segment $[-r, r]$, which is equal to $2r$. When n=2, from school you probably remember that the circumference of a circle of radius $r$ is $2 \pi r$. You also probably remember that its “area” (volume for us) is equal to $\pi r^2$, but why? This can be proved with some basic calculus. If you think about it, the volume of a circle can be computed by summing up the volumes of all the thin “shells” inside it, and each shell of radius $x$ has volume $2\pi x dx$. So

$V_2(r) = \int_{0}^r 2\pi x dx = \pi r^2.$

Similarly, $V_3(r)$ can be computed by adding up the volume of all the 3-shells of radius $x$, $A_3(x) dx$, for $x\in [0, r]$. However, we don’t have an expression for $A_3(x)$, so we must do something else.

An alternate way of thinking about the volume of a $3$-dimensional sphere is to think of it as the sum of the volume of its “slices” where each slice is a thin disk. So once again, using calculus we will be able to compute the volume. Our integral will integrate over $x\in [-r, r]$, and at every $x$ our volume will be $ \pi (r^2 - x^2) dx$ (The way I’m thinking of this integration is: draw in a piece of paper the circle $x^2 + y^2 = r^2$ and when you are at position $x$ you have a disk with volume $\pi y^2 dx$ sticking out of the page). So

\begin{align} V_3(r) &= \int_{-r}^r \pi (r^2 - x^2) dx \cr &= 2 \pi \int_{0}^r (r^2 - x^2) dx \cr &= \frac{4}{3} \pi r^3. \end{align}

Let’s recap what we have so far, we have shown that $V_1(r) = 2r$, $V_2(r) = \pi r^2$, and $V_3(r) = \frac{4}{3} \pi r^3$. So we should expect $V_n = C_n r^n$. But how do we find a general expression for $C_n$? Setting up the integral for $V_3$ required visualizing the 3-d sphere and its slices. However, I don’t trust my geometric intuition for setting up an integral for $V_4$ other than the “add up the shells” one [Side Note 1]. But as we saw when we tried to use this argument to compute $V_3$, we would need to have an expression for $A_3$, which we don’t have…

So, what now? I guess this is where being exposed to a wide variety of ideas/problems pays off, as people say: luck favors the prepared mind.

As you will see later in this post, we will be able to compute an expression for $C_n$ by making a connection with an integral that arises in probability. I must note that I did not make the connection myself, the ideas that follow are from Hamming’s book.

The Gamma Function

Let us divert our attention to the following integral, mathematicians refer to it as $\Gamma(n)$,

$\Gamma(n) := \int_{0}^{\infty} x^{n-1} e^{-x} dx.$

If you are familiar with probability, you would notice that $\Gamma(n)$ is the $(n-1)$-th moment of a standard exponential random variable. Since $\Gamma(1)$ is just the integral of the pdf, we know that $\Gamma(1)=1$. If you were curious enough to compute $\Gamma(2)$, $\Gamma(3)$, $\Gamma(4)$, $\Gamma(5)$, $\Gamma(6)$ you would notice that the corresponding values are 1, 2, 6, 24, 120, which correspond to $1!, 2!, 3!, 4!, 5!$. So, it seems we’ve found a function that when evaluated at integers produces factorials! Let us prove this is the case. Using integration by parts with $u=x^{n-1}$ and $dv = e^x dx$ we have:

\begin{align} \Gamma(n) &:= \int_{0}^{\infty} x^{n-1} e^{-x} dx \cr &= - x^{n-1} e^{-x} \big\vert_{0}^\infty - \int_{0}^{\infty} (n-1) x^{n-2} (-e^{-x}) dx \cr &= (-0 + 0) + (n-1) \Gamma(n-1) \cr &= (n-1) \Gamma(n-1). \end{align}

Since we know that $\Gamma(1)=1$ we’ve shown that indeed when we evaluate the gamma function at the positive integers we will get factorials.

In my opinion this is a pretty magical result, and not sure how you would notice this pattern unless you had a lot of free a time to compute high order moments of probability distributions. After doing some digging around the history of the Gamma function, it turns out that the connection was not made the way I just implied. It turns out Leonard Euler, engineered this function (actually a variant of it) because he was trying to extend the definition of the factorial to the reals instead of just the positive integers. If you are interested in the history of the Gamma function, I highly recommend reading (Davis, 1959).

Computing $\Gamma( \frac{1}{2} )$

Now let’s evaluate $\Gamma( \frac{1}{2} )$. Why at $\frac{1}{2}$? To be honest, I don’t know. I guess it makes sense since, with it, we could compute the value of $\Gamma$ at 1.5, 2.5, 3.5, … using the recursion $\Gamma(n) = (n-1) \Gamma(n-1)$. After all, Euler wanted to extend the factorial from the integers to the reals, so exploring what happens between two integers is reasonable.

Using the substitution $x = t^2$, $dx = 2 t dt$, we have

\begin{align} \Gamma(\frac{1}{2}) &:= \int_{0}^{\infty} x^{-\frac{1}{2}} e^{-x} dx \cr &= 2\int_{0}^{\infty} t^{-1} e^{-t^2} 2 t dt \cr & = \int_{-\infty}^{\infty} e^{-t^2} dt, \tag{1} \end{align}

where the last equality follows by the symmetry of $e^{-t^2}$ around $t=0$. Notice the term inside the integral resembles the pdf of a gausian random variable, except it’s missing some constants (that we know involve $\pi$). With this observation we should expect $\pi$ to appear soon, and with $\pi$ we should also think of circles and spheres. Now, how do we evaluate that integral? Hamming claims what follows is a standard trick but I certainly don’t remember it. Turns out its easier to compute $\Gamma(\frac{1}{2})^2$. Indeed:

\begin{align} \Gamma(\frac{1}{2})^2 &:= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-(x^2 + y^2)} dx dy \cr \end{align}

and with the $x^2 + y^2$ term you should think of the equaltion of a circle of radius $r$, $x^2 + y^2 = r^2$. This suggests changing to polar coordinates $x = r cos(\theta), y = r sin(\theta)$, remember the new differential is $\det(J) dr d\theta$ where $\det(J)$ is the determinant of the Jacobian, in this case $r$.

\begin{align} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-(x^2 + y^2)} dx dy &=\int_{0}^{2\pi} \int_{0}^\infty e^{-r^2} \det(J) dr d\theta \cr & = \int_{0}^{2\pi} \int_{0}^\infty e^{-r^2} r dr d\theta \cr &= \int_{0}^{2\pi} d\theta \int_{0}^\infty e^{-r^2} r dr \cr &= \int_{0}^\infty e^{-r^2} 2 \pi r dr \tag{this line is key!} \cr &= \int_{0}^\infty \pi e^{-u} du \cr &= \pi. \end{align}

We have shown that $\Gamma(\frac{1}{2}) = \pi^{\frac{1}{2}}$. The key insight from this proof is that we related $\Gamma(\frac{1}{2})$ to an integral we could compute that involves only the radius $r$ and the volume of the shell of a sphere. Look again closely at “this line is key!”, the $e^{-r^2}$ is equal to $e^{-(x^2+y^2)}$ because of the equation for a circle, and $2 \pi r dr$ is $A_1(r)dr$ is the volume of a shell of radius $r$.

An Expression for $C_n$

At this point we have everything we need to derive an expression for $C_n$. We will make use of the following facts:

• $\Gamma(\frac{1}{2})$ can be writen as (1).
• The volume of a sphere is equal to the sum of the volume of all its shells, i.e. the volume element of a shell is $A_n(r) dr = (\frac{d}{dr}V_n(r))dr = n C_n r^{n-1} dr$.
• The equation of an $n$-dimensional sphere of radius $r$ is equal to $x_1^2+x_2^2+…+x_n^2=r^2$.
• $\Gamma(\frac{n}{2}+1) = \frac{n}{2}\Gamma(\frac{n}{2})$, just plug in $\frac{n}{2}+1$ into the recurrence relation of the Gamma function to see this.

So, using $r^2 = t$, $dr = \frac{1}{2}t^{-\frac{1}{2}}dt$

\begin{align} \Gamma(\frac{1}{2})^n &= \int_{0}^\infty e^{-r^2} A_n(r) dr \cr &= \int_{0}^\infty e^{-r^2} n C_n r^{n-1} dr \cr &= \int_{0}^\infty e^{-t} n C_n t^{\frac{n-1}{2}} \frac{1}{2} t^{-\frac{1}{2}}dt \cr &= \frac{n C_n}{2} \int_{0}^\infty t^{\frac{n}{2}-1} e^{-t} dt \cr &= \frac{n C_n}{2} \Gamma(\frac{n}{2})\cr &= C_n \Gamma(\frac{n}{2}+1). \end{align}

Plugging in $\Gamma(\frac{1}{2}) = \pi^{\frac{1}{2}}$ and solving for $C_n$ we get

$C_n = \frac{\pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}.$

So, we are done finding a closed for expression for $C_n$, nice!

The Answer

We finally get to answer the intriguing question: “Why You Should Never Buy High Dimensional Watermelons”! We’ve shown that the volume of an $n$-dimensional sphere of radius $r$ is equal to $C_n r^n$ so the volume of an $n$ dimensional shell of thickness $\epsilon > 0$ is equal to $C_n r^n - C_n ((1-\epsilon)r)^n$. It follows that the ratio of the volume of the shell to the volume of the sphere is:

$\frac{C_n r^n - C_n (1-\epsilon)^n r^n}{C_n r^n} = 1 - (1-\epsilon)^n$

Side Note 2. Since $(1-\epsilon)^n \rightarrow 0$ as $n\rightarrow \infty$ regardless of how small $\epsilon$ is, the ratio of the volumes tends to 1 as $n\rightarrow \infty$. So, high dimensional watermelons are almost all rind and no flesh! Tough luck for high dimensional beings…

Side Notes

Side Note 1

Side note from the day after writing the section above: I actually went to bed thinking about this and I woke up realizing that maybe I do have some intuition about how to set up the integral for $V_4(r)$. To compute $V_3$, I argued you could think of it as adding up slices where each slice is a disk. So if you think about projecting the 4-sphere to the 2-d plane you will have a circle, and if you slice the circle in 2-d at $x$, its high dimensional (spherical) slice will have volume $\frac{4}{3}\pi (r^2 - x^2)^{\frac{3}{2}} dx$. So $V_4(r) = \int_{-r}^r \frac{4}{3}\pi (r^2 - x^2)^{\frac{3}{2}} dx$. Using the same line of reasoning in higher dimensions we can write:

\begin{align} V_n(r) &= \int_{-r}^r V_{n-1}(r^2 - x^2) dx. \end{align}

Computing the $V_4$ integral can be done via a trigonometric substitution and then using power reduction formulas. I’d say that you could now compute $C_n$ for any $n$ using the recursion for $V_n$ above. However we don’t really have a closed form solution for $C_n$ and I’ve never seen a way to “solve” the $V_n$ recursion.

Side Note 2

You probably noticed that in the section where we showed almost all the volume of the sphere is in it’s surface we did not use the expression for $C_n$. We could have derived this conclusion right after noticing that $V_n(r) = C_n r^n$ for some constant $C_n$. So, why did I go through all the trouble of deriving an epxression for $C_n$? Partly, because it was fun, and because I learned some new math tricks along the way. But also, in his book, Hamming notes that for spheres of radius 1, when $n=2k$, $C_{n}=\frac{\pi^k}{k!}$ so $V_{2k}(1) \rightarrow 0$ as $k\rightarrow \infty$. Read that again $V_{2k}(1) \rightarrow 0$, the volume tends to 0! This may sound shocking, it’s not. The reason is because volume is not a dimensionless quantity, think of how much “larger” a cubic meter is compared to a (linear) meter. So, at least intuitively, in high dimensions, the dimension (as in $\text{meter}^n$) of the volume makes up for the small values of $C_n$.