Graph Expansion and Concentration of Measure

I'm a 'low-class' mathematician. I'm happy to learn about phenomena in their most scaled-down form, the discrete, finite case. When I heard the 'counting-coins' interpretation of Lebesgue integration, I was satisfied and closed the book (until I was assigned the rest).

The downside is, I'm unable to properly appreciate a lot of analysis. The upsides are, i) being CS-oriented, the finite cases are largely adequate; ii) sometimes I can prove them myself.

Let me describe what I think I've figured out about the phenomenon called 'Concentration of Measure' after some casual reading about it in the continuous case, here worked out in my low-class terms. Say we've got a real-valued function F with mean 0 on the Boolean n-cube, and it's 'Lipschitz' in the sense that it changes by at most +-1 across any edge. Then the 'phenomenon' is that the function is very tightly concentrated around its mean. In fact, for a fixed c > 0, the fraction of points x where F(x)> cn is bounded by an inverse-exponential function of n (one can do better regarding the deviation size, but in addition to being low-class, I'm a little lazy).

Note that Concentration of Measure here generalizes the basic Chernoff bound for unbiased voting, since F(x) = ||x|| - n/2 is Lipschitz (where ||•|| denotes Hamming weight).

Before reading on, think about possible connections to graph expansion. This was the factor that got me excited.

Suppose the statement is false; then for some c > 0, there must be a sequence of functions F_n, defined on Boolean cubes of increasing dimension n, such that the 'atypical sets' S_n = { x: F(x) > cn } are not exponentially insignificant compared to 2^n. The key observation is that, if we take

r_n = max r: S_n has at least the volume (# of points) of an r-ball in r_n,

then lim sup (r_n/n) is at least 1/2. (This because, for all s < 1/2, sn-balls are exponentially dinky in n when compared to the n-cube.)

Now we're going to use the expansion properties of the n-cube: the intuitive 'Isoperimetric Inequality', which says that a set at least as big as a k-ball taken with its vertex neighborhood are collectively at least as big as a (k+1)-ball. In other words, balls minimize (vertex-) surface area. There is a nice proof by iteratively 'squashing' a set into ball shape, which can be found here.

What's the use of this? Consider S'_n = { x: F(x) > cn/2 }. Any points within cn/2 distance of S_n are contained in S'_n (by the Lipschitz property); so, by iterative application of the Iso Inequality, S'_n must be as big as an (r_n + cn/2)-ball. Since we know r_n/n gets very close to 1/2 i.o., this tells us that S'_n is bigger than an (1/2 + c/4)*n-ball i.o.; and such balls fill all but an inverse-exponential-in-n fraction of the whole cube. Now there is no way these F_n can have mean 0. We're done.


What's used about the n-cubes in this proof, as a graph family? Nothing more nor less that they have modestly good expansion properties. We can modify this proof to show even stronger Concentration of Measure for 'typical' graphs, which are better expanders even if they are regular with constant degree. I see a weak converse, too.

Food for thought: it's not too hard to come up with a notion of expansion for e.g. smooth manifolds; but what pray tell might we mean by a 'typical' manifold, and how is its expansion?