6 ms·

Volume of an n-ball

90 points by sohkamyung 4y ago

deleted 4y ago
[deleted]
wging 4y ago
This is one of my favorite counterintuitive math results. > Volume of an n-ball tends to a limiting value of 0 as n goes to infinity Another way to say this is that if you inscribe a circle in a square, or a sphere in a cube, or in general an n-ball inside an n-cube, then in higher dimensions the n-ball takes up almost none of the space of the n-cube.
- an1sotropy 4y ago
  that the R=1 volume peaks at N=5 is not something I'll ever have intuition for.
  - mturmon 4y ago
    Because the location of the peak falls at a different dimension depending on the underlying units (i.e., the radius), I don’t think the numerical location of the peak is fundamental. So maybe it’s best that you don’t have intuition for it?
    - dmurray 4y ago
      The ratio of the volume of the sphere to the volume of the enclosing cube (the proportion of the box that it takes up, or the probability that a randomly chosen point inside the box is in the ball) is dimensionless, though. It's not dependent on the size of the cube.
      - mturmon 4y ago
        You can extract dimensionless quantities, but depending on the normalization, the peak will land in different "n" values. E.g., normalize by the enclosing cube (sides of length 2R) versus the enclosed cube. So I don't think there's anything special about the turnover point.
  - stadia42 4y ago
    The answers to this question provide at least some intuition: https://math.stackexchange.com/questions/15656/volumes-of-n-balls-what-is-so-special-about-n-5 https://math.stackexchange.com/questions/15656/volumes-of-n-....
- VLM 4y ago
  I've always thought that "density at the edges" would have interesting implications for moment of inertia. Euler's column formula depends on moment of inertia so that would seem to imply a "Flatland-but-in-11D-instead-of-2D" would have significant mechanical engineering problems compared to our 3-D world. I think macro-scale higher dimensions as a hard sci fi topic would also have weird aerodynamic and heat exchanger effects. How would the ratio of radiative cooling to convective cooling vary if the world had 10,11,100,100000000 dimensions instead of 3? Intuitively if we had 4 dimensions of space I think automotive-type radiators could be quite a bit smaller for a given heat exchange?
maxk42 4y ago
Very counterintuitive. I understand how the proportional space of an n-ball bounded in an n-cube can go to zero, but I don't understand how the volume of an n+1-ball can be of a smaller volume than an n-ball.
- JadeNB 4y ago
  > Very counterintuitive. I understand how the proportional space of an n-ball bounded in an n-cube can go to zero, but I don't understand how the volume of an n+1-ball can be of a smaller volume than an n-ball. It can't be, in the same sense that it's not true that π square meters (the area of a unit circle) is less than (4/3)π cubic meters (the volume of a unit sphere); they are simply not comparable quantities. What is true, as wging very nicely put it (https://news.ycombinator.com/item?id=31349002 https://news.ycombinator.com/item?id=31349002), is that the (n + 1)-ball (of radius 1) eventually takes up a smaller fraction of the (n + 1)-cube (of side 2) than the n-ball does of the n-cube. I agree that this is still probably sufficiently unintuitive that the best one can do is to argue why one shouldn't disbelieve it, not to try to make it intuitive; but nonetheless I will share one of the closest things I've seen to an explanation, which is that the number of corners in a cube grows exponentially with the dimension of the cube, so that, sooner or later, the cube is "mostly corners"—and the ball does not poke into the corners.
- zmgsabst 4y ago
  > volume of an n+1-ball can be of a smaller volume than an n-ball Volume is the ratio of the n-ball to the n-cube. Saying that n+1-ball has “smaller volume” than the n-ball is equivalent to saying that the ratio of the n+1-ball to the n+1-cube is smaller than the ratio of the n-ball to the n-cube. > I understand how the proportional space of an n-ball bounded in an n-cube can go to zero The volume comment is saying that the ratio of the n-ball to its bounding n-cube goes to zero faster than (base-2) exponential: The bounding n-cube is 2^n times the unit n-cube.
- deleted 4y ago
  [deleted]
- xbar 4y ago
  How about this example: For r=1 A two-dimensional n-ball is a circle. If you extend it into 3 dimensions, by default it is a cylinder, of h=1 and r=1. That’s not a 3-dimensional n-ball however. If you increase the dimensions of that 2-dimensional n-ball into 3 dimensions, it becomes a 3-dimensional n-ball—-a sphere of r=1. And now you have a sphere that is smaller than the circle that was extended into 3 dimensions as a cylinder. The ball-ness of the n-ball formula chopped off the corners of the cylinder. And that chopping off continues in higher dimensions.
tedunangst 4y ago
https://blogs.scientificamerican.com/roots-of-unity/why-you-should-care-about-high-dimensional-sphere-packing/ https://blogs.scientificamerican.com/roots-of-unity/why-you-... http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres https://www.youtube.com/watch?v=mceaM2_zQd8 https://www.youtube.com/watch?v=mceaM2_zQd8
cschmid 4y ago
This is pretty obvious, no? If you choose a (uniformly) random point inside an n-sphere, the components of the vector will go to zero as n gets larger -- after all, the sum of their squares has to be less than 1. A (uniformly) random point in an n-dimensional cube will have random coordinates from zero to 1, with no other constraint on their size.
- reikonomusha 4y ago
  No, it is not obvious to people who haven't been trained in college-level mathematical thinking, or people who don't think about higher-dimensional objects using the handlebars of abstraction.
  - jakear 4y ago
    Pick N random numbers between -0.5 and 0.5. Square them. Then add them up. How does the probability that {sum of these N positive values exceeds 1} change as the N increases? I think anyone with a basic understanding of arithmetic should be able to answer that.
    - wardedVibe 4y ago
      https://xkcd.com/2501/ https://xkcd.com/2501/
    - reikonomusha 4y ago
      Is it obvious to anybody with "a basic understanding of arithmetic" that this has anything to do with higher dimensional spheres? I think any great teacher can break down many complicated subjects (like the nature of the surface of a higher dimensional sphere) into a series of simpler subjects (if you have to choose a bunch of numbers so they add up to 100, will the numbers tend to be on the small side?), but that in no way implies a person capable of counting change will intuit this series of simpler subjects themselves. I must ask, somewhat rhetorically, isn't that obvious?
      - jakear 4y ago
deleted 4y ago
[deleted]
codeflo 4y ago
There’s perhaps another way to think about this. The unit “1” in terms of hypervolume is a n-hypercube with side length 1, so the question is really, how many of those hypercubes fit into an n-ball of a given radius. Now, the thing I realized is that a unit hypercube in n dimensions is an unimaginably weird object. Its side length is, by definition, 1. But as n goes to infinity, the distance between the center and the corners of this unit hypercube goes to infinity — this follows directly from the Pythagorean Theorem. The center of the hyperfaces, on the other hand, is always only 0.5 distance units away from the center of the cube. An inscribed ball touches those hyperfaces, so 0.5 is also the radius of that inscribed ball. This makes the hypercube in some sense very “spiky”, with parts of the boundary close to the center (0.5) and other parts infinitely far away. Also, there are 2^n of those corners. Indeed, and that’s just another way of stating the submission headline, most of the volume of the hypercube is near those spiky corners. Stated another way, as n goes to infinity, none of the volume of a hypercube is at a bounded distance from the center. And note that we’re still talking about a unit hypercube, so the side length in all of this always remains 1. So, if you accept the math, the question is: Is the quoted result really something unintuitive about high-dimensional balls, which are perfectly symmetrical objects? Or is the “weirdness”, in terms of human intuition, better blamed on the hypercubes we implicitly compare them to when we talk about volume?
- schoen 4y ago
  > This makes the hypercube in some sense very “spiky”, with parts of the boundary close to the center (0.5) and other parts infinitely far away. One way to make the weirdness of the "other parts infinitely far away" concrete is to recall that, say, the Empire State Building can fit entirely inside of an n-cube with sides of 1 cm, for sufficiently large n. The length of the diagonal of such a cube grows without bound, and so does any constant-dimensional cross-section. Extremely high-dimensional spaces are extremely spacious. (People experience this with ML and statistics, where random points in very high-dimensional data sets are almost certain to be extremely far apart from one another in a Euclidean metric.) > So, if you accept the math, the question is: Is the quoted result really something unintuitive about high-dimensional balls, which are perfectly symmetrical objects? Or is the “weirdness”, in terms of human intuition, better blamed on the hypercubes we implicitly compare them to when we talk about volume? That's a terrific way to put it. We can think of the n-balls as bizarrely small (and/or bizarrely round), or we can think of the n-cubes as bizarrely huge (and/or bizarrely spiky). Then we could say that the latter eventually contain absurdly much space, while the former continue to contain only a moderate, reasonable amount of space!
akomtu 4y ago
That's not surprising if you look at how a square with a circle turns into a cube with a sphere that's made of progressively smaller circles. What's surprising is that volume of a n-ball reaches maximum in 5 dimensions and surface of an n-sphere - in 7 dimensions.
bumbledraven 4y ago
Volume of a unit 4-ball without calculus A while back, I wanted a way to find the volume of a unit 4-ball without calculus, but I couldn’t find anything. I ended up coming up with the approach below, which uses probability. Comments and criticism welcome. We want to find the volume of a 4-dimensional unit ball. Let the center of the 4-ball be the origin. Enclose the 4-ball in an origin-centered, axis-aligned 4-dimensional cube of side length 2. Choose a point uniformly at random inside the 4-cube. What is the probability that the point lies within the 4-ball? If we knew this, we could find the volume of the 4-ball, because P[point inside 4-ball] = (volume of 4-ball)/(volume of 4-cube), and we know that the volume of the 4-cube is 2⁴. We will find P[point inside 4-ball]. Let (a,b,c,d) be the point's coordinates. Since they were picked uniformly at random within the 4-cube and the 4-cube's coordinates range from −1 to 1, we know that a, b, c, and d are each uniformly distributed from −1 to 1 (in symbols: a ~ U(−1,1), b ~ U(−1,1), etc.). The radius of the 4-ball is 1, so the point is inside the 4-ball just when the radius of the point is less than 1. In symbols: P[point inside 4-ball] = P[a² + b² + c² + d² < 1]. Since all four terms sum to less than 1, surely the first two do as well. Therefore, we have: P[point inside 4-ball] = P[a² + b² < 1] P[a² + b² + c² + d² < 1 | a² + b² < 1] The last two terms must also sum to less than 1, so we have: P[point inside 4-ball] = P[a² + b² < 1] P[c² + d² < 1] P[a² + b² + c² + d² < 1 | a² + b² < 1 ∧ c² + d² < 1] Now a lemma: Suppose x ~ U(−1,1) and y ~ U(−1,1). Then P[x² + y² < 1] = π/4. Proof: Since x ~ U(−1,1) and y ~ U(−1,1), P[x² + y² < 1] is the probability that (x,y) lies within an open unit disc, given that it lies within the enclosing 2x2 square. This is simply the area of a unit disc divided by the area of the enclosing 2x2 square, so we have P[a² + b² < 1] = π/4. Similarly for the probability that c² + d² < 1. Using the lemma on the first two factors, we have: P[point inside 4-ball] = (π/4)(π/4)P[a² + b² + c² + d² < 1 | a² + b² < 1 ∧ c² + d² < 1] Now for a second lemma: Suppose x ~ U(−1,1), y ~ U(−1,1), and x² + y² < 1. Then x² + y² ~ U(0,1). Proof: The assumptions can be visualized as throwing a dart randomly at an origin-centered unit disc enclosed in an origin-centered, axis-aligned 2x2 square. If the dart falls outside the disc, we throw again, until it falls within the disc. Let (x,y) be the coordinates of the point, and consider the probability that the point falls inside an origin-centered disc of area A, where 0 ≤ A < π (the area of the outer unit disc). This happens just when the radius of the point (the distance from it to the origin) is less than the radius of the inner circle. The radius of the point is √(x² + y²), and the radius of the inner circle is √(A/π). Therefore, the desired probability is P[√(x² + y²) < √(A/π)]. Squaring both sides yields P[point inside disc of area A] = P[x² + y² < A/π]. Since the area of the inner disc is A and the area of the enclosing unit disc is π, we have P[point inside disc of area A] = A/π, or P[x² + y² < A/π] = A/π, for 0 ≤ A/π ≤ 1. By the definition of a uniform distribution over the reals, P[X < x] = x for 0 ≤ x ≤ 1 if and only if X ~ U(0,1). Hence, we have shown that x² + y² ~ U(0,1). Now back to the main problem. Write u = a² + b² and v = c² + d². Since a ~ U(−1,1), b ~ U(−1,1), and a² + b² < 1, we know, by the second lemma, that a² + b² ~ U(0,1). Similarly, we know that c² + d² ~ U(0,1). Therefore, we can write: P[point inside 4-ball] = (π/4)(π/4)P[u + v < 1 | u ~ U(0,1) ∧ v ~ U(0,1)] The value of the probability expression in that formula is simply the area below the triangle in a square, or 1/2, so we have: P[point inside 4-ball] = (π/4)(π/4)(1/2) = π²/32 Applying this to our original formula yields: (volume of unit 4-ball) = (π²/32)×(2⁴) = π²/2.
fxj 4y ago
In high-dimensional spaces almost all points of a compact object are located on the surface of the object.
- wikfwikf 4y ago
  I don't think this is true if you are taking the common but technically precise mathematical meanings of 'almost all' and 'the surface'.
jstx1 4y ago
Grant from 3blue1brown talking about this on Numberphile: Darts in Higher Dimensions - https://www.youtube.com/watch?v=6_yU9eJ0NxA https://www.youtube.com/watch?v=6_yU9eJ0NxA
mfsch 4y ago
The spiky shape of the n-cube can be used as an illustration of the “myth of averages”, i.e. the observation that basically no person can be considered “average” or “typical” as soon as you consider a number of dimensions (famously observed by the US Air Force when trying to adjust fighter jet cockpits to the average dimensions of pilots [1]). If you consider n variables along which people and their experience can vary, the space that is “reasonably close” to the average (e.g. an n-ball or even an n-cube with side length 1−ε) becomes vanishingly small compared to the full space. I find this is an important concept to keep in mind when designing systems and products. When you reach a certain complexity, most cases are edge cases and designing only for the “typical” case serves almost nobody. [1]: https://99percentinvisible.org/episode/on-average/ https://99percentinvisible.org/episode/on-average/
- et2o 4y ago
  Fascinating observation. Thanks for sharing. Given that this problem space still exists I wonder what the best approach might be other than taking the mean
kloch 4y ago
Here is the construction of the n-ball volume and n-sphere surface area constants up to n=26. Those denominators get crazy. double nbv[27]; double nss[27]; // n-ball volume constants (index is exponent and n-ball dimension) // nbv[n] = nss[n-1]/n (n > 0) // nbv[n] = 2pi * nbv[n-2]/n (n > 1) nbv[0]= 1.0; nbv[1]= 2.0; nbv[2]= M_PI; nbv[3]= 4.0 * M_PI / 3.0; nbv[4]= pow(M_PI, 2.0) / 2.0; nbv[5]= 8.0 * pow(M_PI, 2.0) / 15.0; nbv[6]= pow(M_PI, 3.0) / 6.0; nbv[7]= 16.0 * pow(M_PI, 3.0) / 105.0; nbv[8]= pow(M_PI, 4.0) / 24.0; nbv[9]= 32.0 * pow(M_PI, 4.0) / 945.0; nbv[10]= pow(M_PI, 5.0) / 120.0; nbv[11]= 64.0 * pow(M_PI, 5.0) / 10395.0; nbv[12]= pow(M_PI, 6.0) / 720.0; nbv[13]= 128.0 * pow(M_PI, 6.0) / 135135.0; nbv[14]= pow(M_PI, 7.0) / 5040.0; nbv[15]= 256.0 * pow(M_PI, 7.0) / 2027025.0; nbv[16]= pow(M_PI, 8.0) / 40320.0; nbv[17]= 512.0 * pow(M_PI, 8.0) / 34459425.0; nbv[18]= pow(M_PI, 9.0) / 362880.0; nbv[19]=1024.0 * pow(M_PI, 9.0) / 654729075.0; nbv[20]= pow(M_PI, 10.0) / 3628800.0; nbv[21]=2048.0 * pow(M_PI, 10.0) / 13749310575.0; nbv[22]= pow(M_PI, 11.0) / 39916800.0; nbv[23]=4096.0 * pow(M_PI, 11.0) / 316234143225.0; nbv[24]= pow(M_PI, 12.0) / 479001600.0; nbv[25]=8192.0 * pow(M_PI, 12.0) / 7905853580625.0; nbv[26]= pow(M_PI, 13.0) / 6227020800.0; // n-sphere surface area constants (index is exponent and n-sphere dimension and n-ball dimension - 1) // nss[n] = 2pi * nbv[n-1] (n > 0) nss[0]= 2.0; nss[1]= 2.0 * M_PI; nss[2]= 4.0 * M_PI; nss[3]= 2.0 * pow(M_PI, 2.0); nss[4]= 8.0 * pow(M_PI, 2.0) / 3.0; nss[5]= pow(M_PI, 3.0); nss[6]= 16.0 * pow(M_PI, 3.0) / 15.0; nss[7]= pow(M_PI, 4.0) / 3.0; nss[8]= 32.0 * pow(M_PI, 4.0) / 105.0; nss[9]= pow(M_PI, 5.0) / 12.0; nss[10]= 64.0 * pow(M_PI, 5.0) / 945.0; nss[11]= pow(M_PI, 6.0) / 60.0; nss[12]= 128.0 * pow(M_PI, 6.0) / 10395.0; nss[13]= pow(M_PI, 7.0) / 360.0; nss[14]= 256.0 * pow(M_PI, 7.0) / 135135.0; nss[15]= pow(M_PI, 8.0) / 2520.0; nss[16]= 512.0 * pow(M_PI, 8.0) / 2027025.0; nss[17]= pow(M_PI, 9.0) / 20160.0; nss[18]= 1024.0 * pow(M_PI, 9.0) / 34459425.0; nss[19]= pow(M_PI, 10.0) / 181440.0; nss[20]= 2048.0 * pow(M_PI, 10.0) / 654729075.0; nss[21]= pow(M_PI, 11.0) / 1814400.0; nss[22]= 4096.0 * pow(M_PI, 11.0) / 13749310575.0; nss[23]= pow(M_PI, 12.0) / 19958400.0; nss[24]= 8192.0 * pow(M_PI, 12.0) / 316234143225.0; nss[25]= pow(M_PI, 13.0) / 239500800.0; nss[26]=16384.0 * pow(M_PI, 13.0) / 7905853580625.0;
deleted 4y ago
[deleted]

90 points by sohkamyung 4y ago

deleted 4y ago

[deleted]

This is one of my favorite counterintuitive math results. > Volume of an n-ball tends to a limiting value of 0 as n goes to infinity Another way to say this is that if you inscribe a circle in a square, or a sphere in a cube, or in general an n-ball inside an n-cube, then in higher dimensions the n-ball takes up almost none of the space of the n-cube.

an1sotropy 4y ago
that the R=1 volume peaks at N=5 is not something I'll ever have intuition for.
- mturmon 4y ago
  Because the location of the peak falls at a different dimension depending on the underlying units (i.e., the radius), I don’t think the numerical location of the peak is fundamental. So maybe it’s best that you don’t have intuition for it?
  - dmurray 4y ago
    The ratio of the volume of the sphere to the volume of the enclosing cube (the proportion of the box that it takes up, or the probability that a randomly chosen point inside the box is in the ball) is dimensionless, though. It's not dependent on the size of the cube.
    - mturmon 4y ago
      You can extract dimensionless quantities, but depending on the normalization, the peak will land in different "n" values. E.g., normalize by the enclosing cube (sides of length 2R) versus the enclosed cube. So I don't think there's anything special about the turnover point.
- stadia42 4y ago
  The answers to this question provide at least some intuition: https://math.stackexchange.com/questions/15656/volumes-of-n-balls-what-is-so-special-about-n-5 https://math.stackexchange.com/questions/15656/volumes-of-n-....
VLM 4y ago
I've always thought that "density at the edges" would have interesting implications for moment of inertia. Euler's column formula depends on moment of inertia so that would seem to imply a "Flatland-but-in-11D-instead-of-2D" would have significant mechanical engineering problems compared to our 3-D world. I think macro-scale higher dimensions as a hard sci fi topic would also have weird aerodynamic and heat exchanger effects. How would the ratio of radiative cooling to convective cooling vary if the world had 10,11,100,100000000 dimensions instead of 3? Intuitively if we had 4 dimensions of space I think automotive-type radiators could be quite a bit smaller for a given heat exchange?

maxk42 4y ago

Very counterintuitive. I understand how the proportional space of an n-ball bounded in an n-cube can go to zero, but I don't understand how the volume of an n+1-ball can be of a smaller volume than an n-ball.

JadeNB 4y ago
> Very counterintuitive. I understand how the proportional space of an n-ball bounded in an n-cube can go to zero, but I don't understand how the volume of an n+1-ball can be of a smaller volume than an n-ball. It can't be, in the same sense that it's not true that π square meters (the area of a unit circle) is less than (4/3)π cubic meters (the volume of a unit sphere); they are simply not comparable quantities. What is true, as wging very nicely put it (https://news.ycombinator.com/item?id=31349002 https://news.ycombinator.com/item?id=31349002), is that the (n + 1)-ball (of radius 1) eventually takes up a smaller fraction of the (n + 1)-cube (of side 2) than the n-ball does of the n-cube. I agree that this is still probably sufficiently unintuitive that the best one can do is to argue why one shouldn't disbelieve it, not to try to make it intuitive; but nonetheless I will share one of the closest things I've seen to an explanation, which is that the number of corners in a cube grows exponentially with the dimension of the cube, so that, sooner or later, the cube is "mostly corners"—and the ball does not poke into the corners.
zmgsabst 4y ago
> volume of an n+1-ball can be of a smaller volume than an n-ball Volume is the ratio of the n-ball to the n-cube. Saying that n+1-ball has “smaller volume” than the n-ball is equivalent to saying that the ratio of the n+1-ball to the n+1-cube is smaller than the ratio of the n-ball to the n-cube. > I understand how the proportional space of an n-ball bounded in an n-cube can go to zero The volume comment is saying that the ratio of the n-ball to its bounding n-cube goes to zero faster than (base-2) exponential: The bounding n-cube is 2^n times the unit n-cube.
deleted 4y ago
[deleted]
xbar 4y ago
How about this example: For r=1 A two-dimensional n-ball is a circle. If you extend it into 3 dimensions, by default it is a cylinder, of h=1 and r=1. That’s not a 3-dimensional n-ball however. If you increase the dimensions of that 2-dimensional n-ball into 3 dimensions, it becomes a 3-dimensional n-ball—-a sphere of r=1. And now you have a sphere that is smaller than the circle that was extended into 3 dimensions as a cylinder. The ball-ness of the n-ball formula chopped off the corners of the cylinder. And that chopping off continues in higher dimensions.

tedunangst 4y ago

https://blogs.scientificamerican.com/roots-of-unity/why-you-should-care-about-high-dimensional-sphere-packing/ https://blogs.scientificamerican.com/roots-of-unity/why-you-... http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres https://www.youtube.com/watch?v=mceaM2_zQd8 https://www.youtube.com/watch?v=mceaM2_zQd8

cschmid 4y ago

This is pretty obvious, no? If you choose a (uniformly) random point inside an n-sphere, the components of the vector will go to zero as n gets larger -- after all, the sum of their squares has to be less than 1. A (uniformly) random point in an n-dimensional cube will have random coordinates from zero to 1, with no other constraint on their size.

reikonomusha 4y ago
No, it is not obvious to people who haven't been trained in college-level mathematical thinking, or people who don't think about higher-dimensional objects using the handlebars of abstraction.
- jakear 4y ago
  Pick N random numbers between -0.5 and 0.5. Square them. Then add them up. How does the probability that {sum of these N positive values exceeds 1} change as the N increases? I think anyone with a basic understanding of arithmetic should be able to answer that.
  - wardedVibe 4y ago
    https://xkcd.com/2501/ https://xkcd.com/2501/
  - reikonomusha 4y ago
    Is it obvious to anybody with "a basic understanding of arithmetic" that this has anything to do with higher dimensional spheres? I think any great teacher can break down many complicated subjects (like the nature of the surface of a higher dimensional sphere) into a series of simpler subjects (if you have to choose a bunch of numbers so they add up to 100, will the numbers tend to be on the small side?), but that in no way implies a person capable of counting change will intuit this series of simpler subjects themselves. I must ask, somewhat rhetorically, isn't that obvious?
    - jakear 4y ago

deleted 4y ago

[deleted]

codeflo 4y ago

There’s perhaps another way to think about this. The unit “1” in terms of hypervolume is a n-hypercube with side length 1, so the question is really, how many of those hypercubes fit into an n-ball of a given radius. Now, the thing I realized is that a unit hypercube in n dimensions is an unimaginably weird object. Its side length is, by definition, 1. But as n goes to infinity, the distance between the center and the corners of this unit hypercube goes to infinity — this follows directly from the Pythagorean Theorem. The center of the hyperfaces, on the other hand, is always only 0.5 distance units away from the center of the cube. An inscribed ball touches those hyperfaces, so 0.5 is also the radius of that inscribed ball. This makes the hypercube in some sense very “spiky”, with parts of the boundary close to the center (0.5) and other parts infinitely far away. Also, there are 2^n of those corners. Indeed, and that’s just another way of stating the submission headline, most of the volume of the hypercube is near those spiky corners. Stated another way, as n goes to infinity, none of the volume of a hypercube is at a bounded distance from the center. And note that we’re still talking about a unit hypercube, so the side length in all of this always remains 1. So, if you accept the math, the question is: Is the quoted result really something unintuitive about high-dimensional balls, which are perfectly symmetrical objects? Or is the “weirdness”, in terms of human intuition, better blamed on the hypercubes we implicitly compare them to when we talk about volume?

schoen 4y ago
> This makes the hypercube in some sense very “spiky”, with parts of the boundary close to the center (0.5) and other parts infinitely far away. One way to make the weirdness of the "other parts infinitely far away" concrete is to recall that, say, the Empire State Building can fit entirely inside of an n-cube with sides of 1 cm, for sufficiently large n. The length of the diagonal of such a cube grows without bound, and so does any constant-dimensional cross-section. Extremely high-dimensional spaces are extremely spacious. (People experience this with ML and statistics, where random points in very high-dimensional data sets are almost certain to be extremely far apart from one another in a Euclidean metric.) > So, if you accept the math, the question is: Is the quoted result really something unintuitive about high-dimensional balls, which are perfectly symmetrical objects? Or is the “weirdness”, in terms of human intuition, better blamed on the hypercubes we implicitly compare them to when we talk about volume? That's a terrific way to put it. We can think of the n-balls as bizarrely small (and/or bizarrely round), or we can think of the n-cubes as bizarrely huge (and/or bizarrely spiky). Then we could say that the latter eventually contain absurdly much space, while the former continue to contain only a moderate, reasonable amount of space!

akomtu 4y ago

That's not surprising if you look at how a square with a circle turns into a cube with a sphere that's made of progressively smaller circles. What's surprising is that volume of a n-ball reaches maximum in 5 dimensions and surface of an n-sphere - in 7 dimensions.

bumbledraven 4y ago

Volume of a unit 4-ball without calculus A while back, I wanted a way to find the volume of a unit 4-ball without calculus, but I couldn’t find anything. I ended up coming up with the approach below, which uses probability. Comments and criticism welcome. We want to find the volume of a 4-dimensional unit ball. Let the center of the 4-ball be the origin. Enclose the 4-ball in an origin-centered, axis-aligned 4-dimensional cube of side length 2. Choose a point uniformly at random inside the 4-cube. What is the probability that the point lies within the 4-ball? If we knew this, we could find the volume of the 4-ball, because P[point inside 4-ball] = (volume of 4-ball)/(volume of 4-cube), and we know that the volume of the 4-cube is 2⁴. We will find P[point inside 4-ball]. Let (a,b,c,d) be the point's coordinates. Since they were picked uniformly at random within the 4-cube and the 4-cube's coordinates range from −1 to 1, we know that a, b, c, and d are each uniformly distributed from −1 to 1 (in symbols: a ~ U(−1,1), b ~ U(−1,1), etc.). The radius of the 4-ball is 1, so the point is inside the 4-ball just when the radius of the point is less than 1. In symbols: P[point inside 4-ball] = P[a² + b² + c² + d² < 1]. Since all four terms sum to less than 1, surely the first two do as well. Therefore, we have: P[point inside 4-ball] = P[a² + b² < 1] P[a² + b² + c² + d² < 1 | a² + b² < 1] The last two terms must also sum to less than 1, so we have: P[point inside 4-ball] = P[a² + b² < 1] P[c² + d² < 1] P[a² + b² + c² + d² < 1 | a² + b² < 1 ∧ c² + d² < 1] Now a lemma: Suppose x ~ U(−1,1) and y ~ U(−1,1). Then P[x² + y² < 1] = π/4. Proof: Since x ~ U(−1,1) and y ~ U(−1,1), P[x² + y² < 1] is the probability that (x,y) lies within an open unit disc, given that it lies within the enclosing 2x2 square. This is simply the area of a unit disc divided by the area of the enclosing 2x2 square, so we have P[a² + b² < 1] = π/4. Similarly for the probability that c² + d² < 1. Using the lemma on the first two factors, we have: P[point inside 4-ball] = (π/4)(π/4)P[a² + b² + c² + d² < 1 | a² + b² < 1 ∧ c² + d² < 1] Now for a second lemma: Suppose x ~ U(−1,1), y ~ U(−1,1), and x² + y² < 1. Then x² + y² ~ U(0,1). Proof: The assumptions can be visualized as throwing a dart randomly at an origin-centered unit disc enclosed in an origin-centered, axis-aligned 2x2 square. If the dart falls outside the disc, we throw again, until it falls within the disc. Let (x,y) be the coordinates of the point, and consider the probability that the point falls inside an origin-centered disc of area A, where 0 ≤ A < π (the area of the outer unit disc). This happens just when the radius of the point (the distance from it to the origin) is less than the radius of the inner circle. The radius of the point is √(x² + y²), and the radius of the inner circle is √(A/π). Therefore, the desired probability is P[√(x² + y²) < √(A/π)]. Squaring both sides yields P[point inside disc of area A] = P[x² + y² < A/π]. Since the area of the inner disc is A and the area of the enclosing unit disc is π, we have P[point inside disc of area A] = A/π, or P[x² + y² < A/π] = A/π, for 0 ≤ A/π ≤ 1. By the definition of a uniform distribution over the reals, P[X < x] = x for 0 ≤ x ≤ 1 if and only if X ~ U(0,1). Hence, we have shown that x² + y² ~ U(0,1). Now back to the main problem. Write u = a² + b² and v = c² + d². Since a ~ U(−1,1), b ~ U(−1,1), and a² + b² < 1, we know, by the second lemma, that a² + b² ~ U(0,1). Similarly, we know that c² + d² ~ U(0,1). Therefore, we can write: P[point inside 4-ball] = (π/4)(π/4)P[u + v < 1 | u ~ U(0,1) ∧ v ~ U(0,1)] The value of the probability expression in that formula is simply the area below the triangle in a square, or 1/2, so we have: P[point inside 4-ball] = (π/4)(π/4)(1/2) = π²/32 Applying this to our original formula yields: (volume of unit 4-ball) = (π²/32)×(2⁴) = π²/2.

fxj 4y ago

In high-dimensional spaces almost all points of a compact object are located on the surface of the object.

wikfwikf 4y ago
I don't think this is true if you are taking the common but technically precise mathematical meanings of 'almost all' and 'the surface'.

jstx1 4y ago

Grant from 3blue1brown talking about this on Numberphile: Darts in Higher Dimensions - https://www.youtube.com/watch?v=6_yU9eJ0NxA https://www.youtube.com/watch?v=6_yU9eJ0NxA

mfsch 4y ago

The spiky shape of the n-cube can be used as an illustration of the “myth of averages”, i.e. the observation that basically no person can be considered “average” or “typical” as soon as you consider a number of dimensions (famously observed by the US Air Force when trying to adjust fighter jet cockpits to the average dimensions of pilots [1]). If you consider n variables along which people and their experience can vary, the space that is “reasonably close” to the average (e.g. an n-ball or even an n-cube with side length 1−ε) becomes vanishingly small compared to the full space. I find this is an important concept to keep in mind when designing systems and products. When you reach a certain complexity, most cases are edge cases and designing only for the “typical” case serves almost nobody. [1]: https://99percentinvisible.org/episode/on-average/ https://99percentinvisible.org/episode/on-average/

et2o 4y ago
Fascinating observation. Thanks for sharing. Given that this problem space still exists I wonder what the best approach might be other than taking the mean

kloch 4y ago

Here is the construction of the n-ball volume and n-sphere surface area constants up to n=26. Those denominators get crazy. double nbv[27]; double nss[27]; // n-ball volume constants (index is exponent and n-ball dimension) // nbv[n] = nss[n-1]/n (n > 0) // nbv[n] = 2pi * nbv[n-2]/n (n > 1) nbv[0]= 1.0; nbv[1]= 2.0; nbv[2]= M_PI; nbv[3]= 4.0 * M_PI / 3.0; nbv[4]= pow(M_PI, 2.0) / 2.0; nbv[5]= 8.0 * pow(M_PI, 2.0) / 15.0; nbv[6]= pow(M_PI, 3.0) / 6.0; nbv[7]= 16.0 * pow(M_PI, 3.0) / 105.0; nbv[8]= pow(M_PI, 4.0) / 24.0; nbv[9]= 32.0 * pow(M_PI, 4.0) / 945.0; nbv[10]= pow(M_PI, 5.0) / 120.0; nbv[11]= 64.0 * pow(M_PI, 5.0) / 10395.0; nbv[12]= pow(M_PI, 6.0) / 720.0; nbv[13]= 128.0 * pow(M_PI, 6.0) / 135135.0; nbv[14]= pow(M_PI, 7.0) / 5040.0; nbv[15]= 256.0 * pow(M_PI, 7.0) / 2027025.0; nbv[16]= pow(M_PI, 8.0) / 40320.0; nbv[17]= 512.0 * pow(M_PI, 8.0) / 34459425.0; nbv[18]= pow(M_PI, 9.0) / 362880.0; nbv[19]=1024.0 * pow(M_PI, 9.0) / 654729075.0; nbv[20]= pow(M_PI, 10.0) / 3628800.0; nbv[21]=2048.0 * pow(M_PI, 10.0) / 13749310575.0; nbv[22]= pow(M_PI, 11.0) / 39916800.0; nbv[23]=4096.0 * pow(M_PI, 11.0) / 316234143225.0; nbv[24]= pow(M_PI, 12.0) / 479001600.0; nbv[25]=8192.0 * pow(M_PI, 12.0) / 7905853580625.0; nbv[26]= pow(M_PI, 13.0) / 6227020800.0; // n-sphere surface area constants (index is exponent and n-sphere dimension and n-ball dimension - 1) // nss[n] = 2pi * nbv[n-1] (n > 0) nss[0]= 2.0; nss[1]= 2.0 * M_PI; nss[2]= 4.0 * M_PI; nss[3]= 2.0 * pow(M_PI, 2.0); nss[4]= 8.0 * pow(M_PI, 2.0) / 3.0; nss[5]= pow(M_PI, 3.0); nss[6]= 16.0 * pow(M_PI, 3.0) / 15.0; nss[7]= pow(M_PI, 4.0) / 3.0; nss[8]= 32.0 * pow(M_PI, 4.0) / 105.0; nss[9]= pow(M_PI, 5.0) / 12.0; nss[10]= 64.0 * pow(M_PI, 5.0) / 945.0; nss[11]= pow(M_PI, 6.0) / 60.0; nss[12]= 128.0 * pow(M_PI, 6.0) / 10395.0; nss[13]= pow(M_PI, 7.0) / 360.0; nss[14]= 256.0 * pow(M_PI, 7.0) / 135135.0; nss[15]= pow(M_PI, 8.0) / 2520.0; nss[16]= 512.0 * pow(M_PI, 8.0) / 2027025.0; nss[17]= pow(M_PI, 9.0) / 20160.0; nss[18]= 1024.0 * pow(M_PI, 9.0) / 34459425.0; nss[19]= pow(M_PI, 10.0) / 181440.0; nss[20]= 2048.0 * pow(M_PI, 10.0) / 654729075.0; nss[21]= pow(M_PI, 11.0) / 1814400.0; nss[22]= 4096.0 * pow(M_PI, 11.0) / 13749310575.0; nss[23]= pow(M_PI, 12.0) / 19958400.0; nss[24]= 8192.0 * pow(M_PI, 12.0) / 316234143225.0; nss[25]= pow(M_PI, 13.0) / 239500800.0; nss[26]=16384.0 * pow(M_PI, 13.0) / 7905853580625.0;

deleted 4y ago

[deleted]