curse of dimensionality/typical set case study

[Bob Carpenter]

I finally finished the case study I've been working on:

Typical Sets and the Curse of Dimensionality
---------------------------------------------

http://mc-stan.org/documentation/case-studies/curse-dims.html

This case study illustrates the so-called “curse of dimensionality,” starting from scratch and using simple examples based on simulation. For example, generating points uniformly at random in a unit hypercube, it is easy to see how the average distance between random points increases with dimensionality. Similarly, such points tend to increasingly fall outside the hypersphere inscribed within the unit hypercube, showing that in higher dimensions, almost all of the volume is in the corners of the hypercube.

Similarly, generating standard normal variates (zero mean, unit standard deviation) leads to draws that concentrate in a thin shell of increasing distance from the mean as dimensionality increases. The squared distance of a standard normal draw from the mode follows a standard chi-square distribution with degrees of freedom equal to the dimensionality. This allows the the precise bounds of the thin shell to be calculated using tail statistics, showing just how unlikely it is to get near the mode with a random draw from a standard multivariate normal.

These properties of the standard normal distribution provides a segue into discussing the important information-theoretic concept of the typical set for a probability distribution, which is roughly defined as the central log density band into which almost all random draws from that distribution will fall. The rather surprising result is that for a normal distribution in high dimensions, the typical set does not include the volume around the mode. The density is highest around the mode, but the volume is low, and the probability mass is determined as the product of the density and the volume (or more precisely, the integral of the density over the volume).

The standard normal log density is just negative squared Euclidean distance, which provides a straightforward demonstration of why the maximum likelihood estimate for a normal regression is identical to the least squares solution.
---------------------------------------------

- Bob

P.S. I decided in the end not to rehash the discussion from Andrew's
blog which follows from this understanding of typical sets:

http://andrewgelman.com/2017/03/15/ensemble-methods-doomed-fail-high-dimensions/

I want to concentrate on things that will go into the Stan book,
though Michael will probably wind up writing about typical sets, not me!