Hacker Timesnew | past | comments | ask | show | jobs | submitlogin

Great article.

A corollary of one of the facts listed there is that the ratio between the volumes of unit sphere and of the unit cube converges to 0 with d. Meaning, in high dimensions, the unit cube is all corners and no interior.

Another one is to consider the n-dimensional standard Gaussian distribution. In dimensions 1, 2 and 3 these look like a fuzzy ball around the origin. But in high dimensions, it is more like a thin shell of radius sqrt(n). You can see this as the (squared) length of a random vector from that distribution is from the Chi^2 distribution which becomes more and more concentrated in higher dimensions.



> in high dimensions, the unit cube is all corners and no interior.

Wouldn't it be rather "all faces" ?

As you say, it is useful to think about these volumes in terms of probabilities. You can pick a random point in a one-million dimensional cube by throwing one million random numbers uniformly between -1 and 1. Being near a corner means that each one of these coordinates is very close to either 1 or -1, which is extremely unlikely. Being near a face means that just one of the coordinates is near 1 or -1, which is almost sure to happen! Thus, essentially the whole volume of the cube is near its boundary.

By a similar reasoning, you can see that the volume of the sphere is negligible with respect to that of the cube. Consider your random point inside the cube, it will fall inside the sphere if x_1^2 + ... x_n^2 < 1, which is extremely unlikely if n is large: you are summing a million numbers between 0 and 1, how likely is it that the sum is smaller than 1? Very unlikely: if just one of these numbers was too close to 1, all the others must be nearly zero.


Well depends what you mean. It's a nice way of looking at the "all faces" bit.

My point is that if you instead define the "interior" as the inscribed sphere, that becomes vanishingly small.


> In dimensions 1, 2 and 3 these look like a fuzzy ball around the origin. But in high dimensions, it is more like a thin shell of radius sqrt(n).

But it’s also still like a ball. The “shell” thing is not something particular the Gaussian: the same happens for a hard ball. As the dimension increases the share of the mass of the ball close to its surface goes up.


That's true for any ball, even in 2D - most volume is by the edge. But a Gaussian in low dimensions looks "closer" to 0.


Sure, in a 2D ball most volume is by the edge and most of a 2D Gaussian is around radious sqrt(2).

In either case the “concentration” gets more and more important as the number of dimensions goes up.

(Concentration in quotes because for the Gaussian the typical density goes down.)


In the article the unit cubes have side length 1. So isn't the volume always 1, whatever the dimension?


Yes, the volume of the unit cube is 1 in any dimension, but the volume of the unit sphere goes to 0 as the dimension increases.


I believe thats because volume is a measurement of the ratio between "amount of stuff" in the hyper-object vs the amount of stuff in a hyper-cube

The amount of stuff increases with higher dimensions in a sphere, but not as fast as with a cube, hence the ratio between the two converge to zero




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: