4 ms·

Well, when computing power is plentiful, sometimes it's easier to just simulate the heck out of it. (shrug) Back in the day, I was curious about the ratio betw

Well, when computing power is plentiful, sometimes it's easier to just simulate the heck out of it. (shrug) Back in the day, I was curious about the ratio between the volume of an N-dimensional sphere, divided by the volume of the N-dimensional cube that contains it, as a function of N. I'm sure there might be an exact solution somewhere (it's basically the volume of the N-sphere of radius 0.5) but I was too lazy to look it up. Instead, I just did a trivial one-page Monte Carlo shoot-em-up with a lot of points. It converged quickly to a good estimate. For the curious, as N goes up, the volume of the N-sphere is a smaller and smaller fraction of the volume of the N-cube containing it. It kinda blew my mind when I saw the result, but then it started to make sense (in higher dimensions there's more ways for space to be "wasted" in the corners).

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 ago
  Totally 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).

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 ago
Totally 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).