5
$\begingroup$

I've been learning probability lately and I have come across this neat result (in Rick Durrett's book):

Most of the volume of the unit cube in $\mathbb{R}^n$ comes from the set $A_{n,\epsilon} := \{x \in \mathbb{R}^n \, : \,(1-\epsilon)\sqrt{\frac{n}{3}} < |x| < (1+\epsilon)\sqrt{\frac{n}{3}} \},$ which is almost the sphere of radius $\frac{n}{3}.$

At the same time, we know the two basic facts that the volume of the unit ball in $\mathbb{R}^n$ goes to zero as $n$ grows and the volume of the unit cube remains the same, but most of the volume get concentrated in the corners of the cube.

I realize that these two points are pretty different ideas altogether, but it seems strange to me that most of the volume in a high dimensional cube can be contained within a sphere and yet also be concentrated in the corners. Could someone clarify what is really going on? Or perhaps my understanding is off.. I am not very experienced in geometry at all. Thanks!

$\endgroup$
4
  • $\begingroup$ Isn't $A_{n,\epsilon}$ things concentrated nearr the edges? For small $\epsilon$, it's stuff that's very close to $1$. $\endgroup$ – Mark Aug 3 '17 at 16:34
  • $\begingroup$ I realize this is an old question, but can you explain your statement the most of the volume of the $n$-dimensional cube is concentrated in the corners (or provide a source)? It is true that most of the volume is concentrated near the faces. And since the faces are themselves $(n-1)$-dimensional cubes, the argument can be iterated to say that most of the volume is concentrated near the faces of the faces, or the faces of the faces of the faces, etc. But I don't see that this argument gets you all the way down to $0$-dimensional faces (corners), not least because of the argument... $\endgroup$ – Will Orrick Dec 30 '20 at 8:12
  • $\begingroup$ ... made in this question. A spherical shell of radius $\sqrt{n/2}$ actually contains most of the corners of the cube; the number of corners in the shell of radius $\sqrt{n/3}$ is relatively small in comparison. $\endgroup$ – Will Orrick Dec 30 '20 at 8:13
  • $\begingroup$ Related: math.stackexchange.com/questions/2644700/… $\endgroup$ – Ethan Bolker Dec 31 '20 at 19:54
2
$\begingroup$

I didn't know this result (+1), but here's how I'd interpret it geometrically:

For $0 < r < \sqrt{n}$, let $B(r)$ be the intersection of the closed ball of radius $r$ centered at the origin with the unit cube $[0, 1]^{n}$, and (for fixed positive $\epsilon \ll 1$) let $S(r)$ denote the shell $B(r + \epsilon) \setminus B(r - \epsilon)$.

Let $c_{n}$ denote the $(n - 1)$-dimensional volume of the unit sphere. When $r \leq 1 - \epsilon$, $S(r)$ is a thin spherical shell of radius $r$, whose volume is $2\epsilon c_{n} r^{n-1} + O(\epsilon^{2})$. When $r \approx \sqrt{n}$, $S(r)$ is a thin shell near the far corner $(1, 1, \dots, 1)$, whose volume is $O(\epsilon^{n})$. The volume $V(r)$ of $S(r)$ is (clearly?) a continuous function of $r$, and vanishes at the "endpoints", so it has a maximum; this happens to occur at $r = \sqrt{\frac{n}{3}}$.

More qualitatively, increasing $r$ beyond $1$ (where the sphere starts to stick out of the cube) causes the volume $V(r)$ to change for two reasons: increasing because the sphere's total volume is larger, and decreasing because more of the sphere sticks out of the cube.

(If instead you intersect the $n$-ball with the cube $[-1, 1]^{n}$, everything gets multiplied by $2^{n}$, but the ratios of volumes don't change: Both the ball and the cube comprise $2^{n}$ congruent orthants.)

$\endgroup$
1
$\begingroup$

After leaving my comments to your post asking about the meaning of "concentrated in the corners" I gave the question some more thought and now feel it potentially useful to leave this crude attempt at an answer. I want to make clear that the mention of $\sqrt{n/2}$ in my comment was referring to the cube $[0,1]^n$ and sphere centered at the origin. In this answer it will be convenient to talk about the cube $[-1,1]^n$, with sphere still centered at the origin. The former cube is one of $2^n$ cubes making up the latter cube, and the spherical shell of radius $\sqrt{\frac{n}{3}}$ intersects all $2^n$ constituent cubes equally, so that the concentration phenomenon holds whether you consider $[0,1]^n$ or $[-1,1]^n$.

Note that I am not going to address the derivation of the quoted concentration result, which is done elsewhere, for example here and here. My focus will be on intuitive understanding of how the result can be consistent with the other facts you mention.

To address your remark about the volume of the $n$-dimensional ball of unit radius going to zero, the point, of course, is that the spherical shell in the quoted result has radius that grows with the dimension, making it at least possible that the volume doesn't go to zero. Indeed, we can check that this is the case. The volume of the $n$-ball of radius $R$ is given by $$ V_n=\frac{\pi^{n/2}}{\Gamma\left(\frac{n}{2}+1\right)}R^n, $$ which does go to $0$ for any fixed $R$. By Stirling's approximation, $\Gamma\left(\frac{n}{2}+1\right)\sim\sqrt{\pi n}\left(\sqrt{\frac{n}{2e}}\right)^n$, so if we take $R=\sqrt{n/3}$ we get $$ V_n\sim\frac{1}{\sqrt{\pi n}}\left(\sqrt{\frac{2\pi e}{3}}\right)^n. $$ Since $\sqrt{\frac{2\pi e}{3}}\approx2.39$, this grows faster than $2^n$, which it needs to do to keep pace with the volume of the cube of side $2$. So there is no contradiction there.

Now for the intuitive, but crude part. If the statement that the volume of the cube is "concentrated in the corners" is just shorthand for "away from the center", then I think it's fine. But to go farther we need a more precise understanding of how the volume is really distributed. The crude model I will use is taken from Rubik's cube, where the cube of side $2$ is divided into $3^3$ cubies of side $\frac{2}{3}$. Generalize to $n$ dimensions, so that each edge of the $n$-cube is divided into equal thirds, $\left[-1,-\frac{1}{3}\right]$, $\left[-\frac{1}{3},\frac{1}{3}\right]$, $\left[\frac{1}{3},1\right]$, making a total of $3^n$ cubies. Conceptually (although if you open it up you see it's not that way inside) the Rubik's cube has four types of cubie: $8$ corner cubies, $12$ edge cubies, $6$ face cubies, and $1$ body cubie. In $n$ dimensions there will be $n+1$ different types of cubie, each type associated with a particular dimension of facet. So corner cubies are associated with $0$-dimensional facets and edge cubies with $1$-dimensional facets, but there will also be cubies associated with, say, $10$-dimensional facets. Now we can ask: which types of cubie contain most of the volume?

The answer comes from combinatorics. A $d$-dimensional facet of the $n$-cube is specified by fixing each of $n-d$ coordinates to $\pm1$ while allowing the other $d$ coordinates to vary continuously between $-1$ and $1$. The number of $d$-dimensional facets is therefore $2^{n-d}\binom{n}{d}$, which we may express as $3^n\left(\frac{1}{3}\right)^d\left(\frac{2}{3}\right)^{n-d}\binom{n}{d}$. In this expression we see the $3^n$ cubies, multiplied by a Bernoulli distribution function with mean $\frac{n}{3}$ and standard deviation $\frac{\sqrt{2n}}{3}$. For large $n$ this is close to a normal distribution and has a sharp peak around $d=\frac{n}{3}$.

Taking $n=100$ as an example, the mean is about $33.3$ and the standard deviation is about $4.7$. Taking the $3$ standard deviation rule, more than $99.7\%$ of the volume of the $100$-dimensional cube is in the cubies associated with facets of dimensions $19$ through $48$. There is a vanishingly small amount of volume associated with corner cubies. Although $2^{100}$ might seem like a big number, there's a sense in which the $100$-dimensional cube has very few corners: $33$-dimensional facets outnumber corners by a factor of $3.4\times10^{16}$. I won't go so far as to say that the statement about volume being concentrated in corners is wrong. My crude measure of proximity to corners is just one possibility, and other measures may give different results. But I am still curious about what was meant by that statement.

Now here's a key point: cubies associated with the same dimension of facet lie at the same distance from the center, and cubies associated with facets that are close in dimension are of similar distance from the center. Furthermore, the distance of a cubie depends rather strongly on the dimension of the associated facet. If we use the centers of cubies as reference points for measuring distance (so center coordinates will all be $\pm\frac{2}{3}$ or $0$), then cubies associated with $(n-1)$-dimensional facets lie at distance $\frac{2}{3}$ from the center, while corner cubies lie at distance $\frac{2}{3}\sqrt{n}$ from the center. Since the number of cubies associated with a given dimension of facet is sharply peaked, the number of cubies as a function of distance from the center is also sharply peaked, and cubies whose distance from the center is far from the peak value don't contribute much to the volume.

To make a more concrete, but crude, estimate of the distance at which most cubies lie from the center, we focus only on the peak of the distribution at dimension $n/3$ and ignore the fact that the volume of a cubie isn't all at its center. For cubies associated with facets of dimension $n/3$ the center will have $2n/3$ coordinates equal to $\pm\frac{2}{3}$ and $n/3$ coordinates equal to $0$, giving a distance $$ \sqrt{\frac{2n}{3}\cdot\left(\frac{2}{3}\right)^2+\frac{n}{3}\cdot0^2}=\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}\approx0.94\sqrt{\frac{n}{3}}. $$ So even this very crude picture produces an answer close to the quoted value.

A final remark: it may seem puzzling that $33$-dimensional facets can outnumber corners by the large factor $3.4\times10^{16}$ when each $33$-dimensional facet contains $2^{33}$ corners. The explanation for this is that each corner is shared by a huge number of other $33$-dimensional facets. For $d\le e$, an $e$-dimensional facet contains $2^{e-d}\binom{e}{d}$ $d$-dimensional facets. The number of $e$-dimensional facets incident on a given $d$-dimensional facet is $\binom{n-d}{e-d}$, which is the number of ways of choosing which of the $n-d$ fixed coordinates should be allowed to vary. The ratio of the number of $d$-dimensional facets to the number of $e$-dimensional facets is therefore $$ \frac{2^{e-d}\binom{e}{d}}{\binom{n-d}{n-e}}=\frac{2^{n-d}\binom{n}{d}}{2^{n-e}\binom{n}{e}}. $$ When $n=100$, $d=0$, and $e=33$ the factor $2^{33}\approx8.6\times10^9$ in the numerator is completely overcome by the factor $\binom{100}{67}\approx2.9\times10^{26}$.

Added: Perhaps one should be troubled by the roughness of the approximations in the penultimate paragraph and maybe should wonder what the unwanted $\sqrt{\frac{8}{9}}$ is trying to tell us. The approximation of considering only the peak of the distribution seems unlikely to pose any problem, as the peak gets sharper and sharper as $n$ grows. But using the centers of cubies in the distance calculation is a pretty poor approximation. For one thing, cubies, like all cubes, are surprisingly large when the dimension gets big. The distance from the center of a cubie to a corner, for example, is $\frac{1}{3}\sqrt{n}$. Furthermore, there is almost no volume at the center of a cubie. Dividing each cubie into sub-cubies, the center is located in the body sub-cubie, which is unique among the $3^n$ sub-cubies, and the least representative of all sub-cubies.

Fortunately, any intra-cubie distances we might need to account for are corrections to a distance which is itself large: $\sqrt{n/3}$, so our approximation can't be completely off. Furthermore, we know where most of the volume of a cubie lies: it's in the sub-cubies associated with facets of dimension $n/3$ and the centers of these sub-cubies are at distance $\frac{1}{3}\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}$ from the center of the cubie. Now the direction along which some of these sub-cubies lie will be aligned or anti-aligned with the direction along which the cubie itself lies, but this will happen a vanishingly small fraction of the time. In almost all cases, the sub-cubie direction will be uncorrelated with the cubie direction and will be nearly orthogonal to it. Therefore we may use the Pythagorean theorem to estimate the correction to the distance: $$ \left[\left(\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}\right)^2+\left(\frac{1}{3}\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}\right)^2\right]^{1/2}. $$ Of course we have just used the some rough center-point approximation on the sub-cubies, so we should correct that as well by iterating: $$ \left[\left(\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}\right)^2+\left(\frac{1}{3}\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}\right)^2+\left(\frac{1}{3^2}\sqrt{\frac{8}{9}}\sqrt{\frac{n}{3}}\right)^2+\ldots\right]^{1/2}. $$ The geometric sum $1+1/9+1/9^2+\ldots$ equals $\frac{9}{8}$, which exactly compensates for the factor $\frac{8}{9}$, giving the refined distance estimate $\sqrt{\frac{n}{3}}$, a gratifying result!

Of course I'm not suggesting that these heuristic arguments are the way one should actually do the computation: the usual rigorous derivation of the concentration result is actually much simpler, and can be found at the links I gave above. But this picture does provide a way of understanding the concentration phenomenon that is simultaneously combinatorial and geometric and, at least for me, makes things much more concrete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.