1. CONCENTRATION FUNCTIONS AN D INEQUALITIES In this chapter, we introduce, with the first examples of spherical and Gaussian isoperimetry, the concept of measure concentration as put forward by V. Milman [M-S] and discuss its first properties. We define the notion of concentration function and connect it with Levy's deviation and concentration inequalities for Lipschitz functions that provide a main tool in applications. The notion of observable diam- eter is another more geometric view to concentration. The last two sections of this chapter are devoted to the useful tools of expansion coefficients, Laplace bounds and infimum-convolution inequalities to explore concentration properties. 1.1 First examples To introduce to the concept of measure concentration, we first briefly discuss a few examples that will be further analyzed (with references) later on. Our first illustration is suggested by the example of the standard n-sphere Sn in R n + 1 when dimension n is large. By a standard computation, uniform measure an on Sn is almost concentrated when the dimension n is large around the (every!) equator. Actually, the isoperimetric inequality on Sn expresses that spherical caps (geodesic balls) minimize the boundary measure at fixed volume. In its integrated form (see Section 2.1), given a Borel set A on § n with the same measure as a spherical cap J3, then for every r 0, crn(Ar) an(Br) where Ar {x G Sn d(x,A) r} is the (open) neighborhood of order r for the geodesic distance on Sn. One main feature of concentration with respect to isoperimetry is to analyze this inequality for the non-infinitesimal values of r 0. The explicit evaluation of the measure of spherical caps (performed below in Section 2.1) then implies that given any measurable set A with, say, an(A) | , for every r 0, a n ( A r ) l - e - ( n - 1 r 2 / 2 . (1.1) Therefore, almost all points on Sn are within (geodesic) distance -4= from A, which is of particular interest when the dimension n is large. Prom a "tomographic" point of view (developed further in Section 1.4 below), the visual diameter of § n (for crn) is of the order of 4= as n oo, which is in contrast with the diameter of § n as a metric space. l http://dx.doi.org/10.1090/surv/089/01
Previous Page Next Page