Linkblog entry!

Earlier his week I spotted a fun article about some fascinating properties of high-dimensional volumes:

Via HN (which is, I note, occasionally an excellent source for fun math-y observations like this):

Mark Khoury blogged on counter-intuitive properties of high-dimensional spheres.

  • First, note how the volume of -dimensional sphere starts to act out weird when you add dimensions (that is, volume with the respect to -dimensional unit cube of volume units). Another way at looking at the same phenomenon: corners of hypercubes are pointy. See also this. (…both links spotted in HN discussion. Unfortunately I don’t remember Cook’s math blogging entries by heart myself…)

  • Second observation is dubbed “concentration of measure”: nearly all surface area of a very high-dimensional -sphere lies within a small distance from any equator of the sphere.

  • (Then also something about so-called kissing numbers that were not as interesting.)


This has some weird implications.

For example, suppose one wants to sample random points from a -sphere. My first idea would be to take advantage of np.random.rand in NumPy (or whatever is the equivalent the programming language I’d be working in) which produces random numbers from a uniform distribution on , and then do a simple Monte Carlo trick: sample $d$ times random number from to get a point and discard it if it’s not inside the sphere (ie doesn’t not evaluate true for ). Repeat until satisfactory number of points inside sphere attained. But as much of the mass of a high-dimensional hypercube is going to be in the corners of the cube, in high dimensions this procedure is going to be very inefficient: lots of uniform random points that are inside the cube will not be inside the sphere.

…this also has some similar implications for probability distributions such as multivariate Gaussians, but maybe that’s worth a separate post…