4 ms·

You've made the same error as the OP. The volume of a unit n-dimensional sphere decreases exponentially in n. But that doesn't mean you need to increase r exp

by shasta 11y ago

You've made the same error as the OP. The volume of a unit n-dimensional sphere decreases exponentially in n. But that doesn't mean you need to increase r exponentially to compensate - in the volume formula, the r also has an exponent of n. The distance between opposite corners of a unit cube in n-dimensional space is root(n). That's hardly exponential.

jfoutz 11y ago
Huh. I always thought n! grew faster than c^n which would be even worse than exponential. Maybe enough cancels out to make it simpler than it appears. edit Actually, for even dimensions it's pretty clear. n = dimension/2 pi^n / n! factorial wins. The problem is worse than exponentiation.
- arielb1 11y ago
  But if you have r=sqrt(n) that works out fine.
- ph0rque 11y ago
  At some point, I wondered if n! is proportional to n^n. Turns out, it is: n! ~= (2 * pi * n)^1/2 * (n/e)^n (https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation)
  - madcaptenor 11y ago
    Not exactly "proportional", because you have that pesky e in the denominator. But that's the right idea. Basically, to get n! you're multiplying together n things that are sort of n-ish, so you'd expect n! ~ n^n. (When the numbers get really big, like in statistical mechanics, I've seen the approximation log n! ~ n log n.) The next step is to figure that you're multiplying together n things that are on average n/2, so n! ~ (n/2)^n. But then it really turns out that you should have been using a geometric average (since you're multiplying), not an arithmetic one, so n! must be smaller yet. (I don't know a way to get (n/e)^n without doing an integral, though.)
    - ph0rque 11y ago
      Right, proportional in the sense that for both n! and n^n, the fastest-growing component is ~n^n. (I was curious in the context of which grew faster for larger values of n in the big O notation).

by shasta 11y ago

jfoutz 11y ago

Huh. I always thought n! grew faster than c^n which would be even worse than exponential. Maybe enough cancels out to make it simpler than it appears. edit Actually, for even dimensions it's pretty clear. n = dimension/2 pi^n / n! factorial wins. The problem is worse than exponentiation.

arielb1 11y ago
But if you have r=sqrt(n) that works out fine.
ph0rque 11y ago
At some point, I wondered if n! is proportional to n^n. Turns out, it is: n! ~= (2 * pi * n)^1/2 * (n/e)^n (https://en.wikipedia.org/wiki/Stirling%27s_approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation)
- madcaptenor 11y ago
  Not exactly "proportional", because you have that pesky e in the denominator. But that's the right idea. Basically, to get n! you're multiplying together n things that are sort of n-ish, so you'd expect n! ~ n^n. (When the numbers get really big, like in statistical mechanics, I've seen the approximation log n! ~ n log n.) The next step is to figure that you're multiplying together n things that are on average n/2, so n! ~ (n/2)^n. But then it really turns out that you should have been using a geometric average (since you're multiplying), not an arithmetic one, so n! must be smaller yet. (I don't know a way to get (n/e)^n without doing an integral, though.)
  - ph0rque 11y ago
    Right, proportional in the sense that for both n! and n^n, the fastest-growing component is ~n^n. (I was curious in the context of which grew faster for larger values of n in the big O notation).