3 ms·
Yup, there's an exact solution. It turns out that the volume of the n-dimensional unit ball is pi^(n/2) / (n/2)!. (The factorial function generalizes to numbers
by gjm11 12y ago
Yup, there's an exact solution. It turns out that the volume of the n-dimensional unit ball is pi^(n/2) / (n/2)!. (The factorial function generalizes to numbers that aren't integers. For half-integers you get a rational number times sqrt(pi). E.g., if n=3 then we need (3/2)! which happens to equal 3/4.sqrt(pi), so the volume is 4/3.pi.)
So for large n we can use Stirling's approximation. To make the formulas a little shorter I'll write m=n/2. Then the volume of the unit n-ball is
V(n) = pi^m/m! ~ pi^m (e/m)^m 1/sqrt(2.pi.m)
whereas the volume of the smallest n-cube containing that ball is 2^n, so the ratio is
R(n) ~ (pi.e/2m)^m / sqrt(2.pi.m)
where, remember, m=n/2. Actually, at this point maybe it's nicer to put things back in terms of n:
R(n) ~ sqrt[(pi.e/n)^n/pi.n]
When n is large, you should see this as
R(n) ~ sqrt[(..../n)^n.....]
where the "...."s are the less important bits. So for large n this is going to get small.
Concrete not-so-large-n example: let's take n=10. Then R(10) ~= sqrt((pi.e/10)^10/10pi) which happens to be about 0.081. That's pretty accurate -- the exact answer is pi^5/3840, which is about 0.0797. So if you fit a 10-ball snugly inside a 10-cube it'll take up about 1/12 of the space.
What if we crank the dimension up? With n=100 the ratio is about 2x10^-55. (A naive Monte Carlo simulation will be unable to distinguish this from zero.) So if you do the ball-inside-cube thing in 100 dimensions, the ball occupies less than one billion-billion-billion-billion-billion-billionth of the volume of the cube.
High-dimensional cubes are really, really spiky.
- mturmon 12y agoTotally true. It's a useful heuristic approximation that n! ~ (n/e)^n That is, multiplying the "n" factors from 1...n is close to multiplying (n/e) upon itself "n" times. The actual Stirling approximation is just a sqrt(2 pi n) bigger than the above, and usually it's fine to throw that away (as above).