Darts in Higher Dimensions [Numberphile]

The Game

There is a lovely puzzle hidden in the midst of darts, higher dimensional geometry, statistics, and some of the most famous numbers in math. We're going to play a game of darts where we lose the game when the dart misses the bullseye. But this bullseye is too small, so to begin let's make it the entire size of the dartboard.

ImageVideo

Each time we hit the bullseye, it will shrink depending on where the dart lands. This makes the rounds get harder and harder as we continue. A line will be drawn from the center of the dartboard to the landing point, we'll call this line h. Then we'll draw the chord perpendicular to h, whose length will define the diameter of the new bullseye.

ImageVideo

Where does the dart have to land in order for the circle to remain unchanged?

This game rewards good shots because the length of the chord will be close to the old diameter when the dart lands close to the center. When the dart lands near the edge, the new diameter will be dramatically smaller.

ImageVideo

When a dart is thrown and it doesn't land in the bullseye, the game is over. The score is the number of darts thrown, so even if the first dart misses, the minimum score is still 1. Try playing the game for yourself by clicking below.

The Puzzle

Instead of having a human playing this game, we'll create a robot who throws the darts randomly. Imagine a square that surrounds the dartboard, this robot's throws will be uniformly distributed on the square. This is not exactly a realistic distribution, which would be rotationally symmetric.

ImageVideo

To make things simpler the dartboard is the unit circle, so each side of the square has a length of 2. The x and y coordinates of the dart's landing are chosen uniformly:

x\in [-1,1] \\
y\in [-1,1]

ImageVideo

The square does not shrink with the bullseye, it always stays with the dartboard. The question to be answered is what is the expected score for this robot? As the robot plays more and more games, what is the average score?

ImageVideo

We can calculate the expected score ¹ by adding together all of the scores multiplied by the probability that the game ends on that score.

\begin{align*}
E[S] &= P(S=1)\cdot 1 + P(S=2)\cdot 2 + P(S=3)\cdot 3 + \cdots
\\ &= \sum_{i=1} P(S=i)\cdot i
\end{align*}

We'll need to find what the probabilities are for each score. In theory, it is possible to have a perfect game. An expert player could hit the origin with every dart, never shrinking the bullseye. But the probability of such a game occurring is zero. A paradoxical fact about statistics is that there exist events that are possible, but their probability is zero.

Breaking It Down

When faced with a difficult problem, we can try to get a foothold by breaking it down into smaller sub-problems. The first question we might ask is what is the probability of making the first shot? The probability P(S>1) can be found by dividing the area of the circle A=\pi r^2=\pi by the area of the square 2\cdot 2=4.

ImageVideo

The probability of making the first shot is \frac{\pi}{4}, so what is the probability of making the second shot? This is where things get more interesting because the probability of the second shot depends on where the first shot landed. The next radius r_1 forms a right triangle with the current radius and h_0, so we can use the Pythagorean theorem to calculate it.

We can build a table of the radiuses and hit distances to keep track of the information.

\begin{array}{c|c}
r & h \\
\hline \\
r_0 = 1 & h_0=\sqrt{x_0^2+y_0^2} \\\ \\
r_1 = \sqrt{r_0^2-h_0^2} & h_1=\sqrt{x_1^2+y_1^2}
\end{array}

The probability the second shot goes in P(S>2) now depends on four numbers. It may be helpful to write out what the actual requirement is: h_1<r_1. We can also rewrite it by taking the squares, because it doesn't change the truth value of the statement.

\begin{align*}
h_1^2 &< r_1^2 \\
x_1^2+y_1^2 &< r_0^2-h_0^2 \\
x_1^2+y_1^2 &< 1 - x_0^2 - y_0^2 \\
x_0^2 + y_0^2 + x_1^2+y_1^2 &< 1
\end{align*}

We're asking what is the probability that the sum of squares of four random numbers chosen in the range [-1,1] is less than 1.

ImageVideo

This question is a bit tricky because we could guarantee if all the numbers are less than 0.5 then the sum of their squares would be less than 1, but if one was 0.9 that doesn't necessarily throw it out because the others could be very small. We used geometric intuition for the first shot, thinking of it as a point inside or outside of a circle. Rather than thinking of the probabilistic event P(S>2) as two separate throws, we can also think about them as a single point in 4D space: (x_0,y_0,x_1,y_1)\in\mathbb{R}^4.

ImageVideo

Just like how choosing two random numbers and seeing if the sum of their squares is less than 1 brought us to the area of a circle, doing the same with 4 numbers brings us to the volume of a 4D ball.

\text{Volume of a 4D ball: } \frac{\pi^2}2 R^4 \\ \quad \\
\text{Volume of a 4D cube: } 2\cdot2\cdot2\cdot2 = 2^4 = 16 \\ \quad \\
P(S>2) = \frac{\pi^2}{2^4\cdot2}

Why did we skip to 4 dimensions and not 3?

The pattern of dividing the volume of higher dimensional balls by the volume of higher dimensional cubes continues when calculating the probability of larger scores.

For P(S>3) we can calculate \frac{\text{Vol}(\text{6D Ball})}{\text{Vol}(\text{6D Cube})} because the question is analogous to randomly choosing six numbers and having the sum of their squares be less than 1.

x_0^2+y_0^2+x_1^2+y_1^2+x_2^2+y_2^2 < 1

The next problem we face is how to calculate the volume of a higher dimensional ball. Luckily mathematicians have calculated them and you could look at Wikipedia's list and pick them out.

\begin{matrix}
1D & 2R & \quad & 2D & \pi R^2 \\ \quad \\
3D & \frac43\pi R^3 & \quad & 4D & \frac12\pi^2 R^4 \\ \quad \\
5D & \frac8{15}\pi^2 R^5 & \quad & 6D & \frac16\pi^3 R^6 \\ \quad \\
7D & \frac{16}{105}\pi^3 R^7 & \quad & 8D & \frac1{24}\pi^4 R^8 \\ \quad \\
9D & \frac{32}{945}\pi^4 R^9 & \quad & 10D & \frac1{120}\pi^5 R^{10} \\ \quad \\
11D & \frac{64}{10,395}\pi^5 R^{11} & \quad & 12D & \frac1{720}\pi^6 R^{12}
\end{matrix}

What we'd like is a general formula for the volume of an even dimensional ball:

\text{Vol}(2n\text{D Ball}) = \frac{\pi^n}{n!} R^{2n}

Solution

The expected value of our dart throwing robot was defined as:

E[S] = \sum_{i=1} P(S=i)\cdot i

However we've been calculating probabilities in the form of greater than P(S>i) instead of equal to P(S=i). That is completely fine because P(S=2) is equivalent to P(S>1)-P(S>2).

Now we can expand things out and let them collapse down.

\begin{align*}
E[S] =\ &P(S=1)\cdot 1 + P(S=2)\cdot 2 + P(S=3)\cdot 3 + \cdots \\
E[S] =\ &
\ 1 \cdot \left(P(S>0)-P(S>1)\right) \\
+&\ 2 \cdot \left(P(S>1)-P(S>2)\right) \\
+&\ 3 \cdot \left(P(S>2)-P(S>3)\right) \\
+&\ \cdots
\end{align*}

Notice that we're subtracting off 2 of P(S>2) but in the next term we're adding back 3 of them. Each of these terms collapse down to just the sum of each probability:

E[S] = P(S>0)+P(S>1)+P(S>2)+P(S>3)+\cdots

We can begin substituting the values we have calculated so far. Since the minimum score is 1, we will always have a score above 0, so P(S>0)=1. From dividing the area of a circle by the area of a square, we know P(S>1)=\frac{\pi}4. We had previous calculated P(S>2) = \frac{\pi^2}{2^4\cdot2}, which can also be written as P(S>2) = \left( \frac{\pi}4 \right) ^2 \cdot \frac12. By reformatting our solutions and adding them up, we can get the formula:

E[S] = 1+\frac{\pi}4+\left( \frac{\pi}4 \right) ^2 \cdot\frac1{2!}+\left( \frac{\pi}4 \right) ^3 \cdot\frac1{3!}+\cdots

This sequence of numbers is rather similar to another famous sequence: the Taylor series for powers of Euler's number is e^x=1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots

A Taylor series is evaluated as an infinite polynomial where each term gets added together and it approaches the correct value in the limit. This particular series is the definition of e^x and I would argue it is the healthy way to view e^x.

Notice how our expected value is very similar to this Taylor polynomial, and the value of x is \frac{\pi}4. So E[S]=e^{0.25\pi}\approx 2.1932...

If our dart throwing robot played a large number of games, the average of all of its scores should be around this 2.1932 figure.

Conclusion

One of the reasons I enjoy this puzzle so much is that we are playing around with higher dimensional geometry naturally. In the middle of the puzzle we were asking what is the volume of a six dimensional ball without suggesting the universe has more dimensions or something similar. That isn't necessarily why mathematicians care about higher dimensions.

What happened is that we had six numbers and we were encoding a property of those numbers in something we like to describe geometrically. Someone else was tackling this puzzle and described how they were working through intensely difficult integrals. What they were really doing was rediscovering the volume of a 4D ball. Thinking about these higher dimensional shapes came about from a 2D plane, nothing about the dartboard was four dimensional.

Mathematicians will often describe manifolds in four dimensions or how the Poincaré conjecture has been solved for everything but four dimensions. But a common misconception people will have is that mathematicians don't actually care about moving in four dimensions, it is about encoding quadruplets of points.

Another reason why this puzzle is beautiful is it helps builds a healthier relationship with e. The Taylor series is more important than the number itself, it helps explain why e^x is its own derivative, why e^{\pi i}=-1, and many other abstract concepts that go beyond simple repeated multiplication.

Another nice puzzle which distills down the essence of e without involving circles and complicating the answer with \pi is described below.

Additional Game