Friday, January 12, 2007

Visualizing Measure Concentration

In the course of giving my talk at Weizmann, I made the usual point about trying to visualize measure concentration:

A word of caution for those attempting to visualize "measure concentration": imagining a narrowly peaked, one-dimensional distribution is tempting but wrong. This is a genuinely high-dimensional phenomenon.

I gave the example of the uniform distribution on the binary hypercube, {0,1}^n, which certainly exhibits the concentration phenomenon (via Chernoff bounds, for example) -- yet it's as flat as they come; there are no peaks here! Someone from the audience pointed out that if one looks at the distribution of a Lipschitz random variable f:{0,1}^n -> R, then it will indeed be peaked. This threw me off a bit, as it was correct and seemed to trivialize my point, which I knew had some non-trivial content.

Having thought about this off-line I've recovered that non-trivial point. For any measure on {0,1}^n there is a function f:{0,1}^n -> R whose induced random variable will be very peaked. It's also not hard to concoct very clumpy distributions which will induce peaked random variables for a wide class of functions f. The remarkable thing is that uniform distributions produce peaked Lipschitz random variables. Conversely, if one allows badly non-mixing measures on {0,1}^n, it's easy to construct non-peaked Lipschitz rv's. The philosophical take-home message is that while it's trivial to create "orderly" random variable in specific instances, it's quite remarkable to observe that a rich collection of random variables will acually be quite well-behaved under rather general conditions.

No comments: