News for hackers. Stuff that matters.
Re:Markov Chains vs. Simulation: Flipping a Million Little C... by gjm11 on Monday November 10, 2014 @09:44PM (#8587999)
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.

Re:Markov Chains vs. Simulation: Flipping a Million Little C... by mturmon on Tuesday November 11, 2014 @12:19AM (#8588447)
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).