INTRODUCTION The aim of this book is to present the basic aspects of the concentration of measure phenomenon. The concentration of measure phenomenon was put forward in the early seventies by V. Milman in the asymptotic geometry of Banach spaces. Of isoperimetric inspiration, it is of powerful interest in applications, in various areas such as geometry, functional analysis and infinite dimensional integration, discrete mathematics and complexity theory, and especially probability theory. This book is concerned with the basic techniques and examples of the concentration of measure phenomenon with no claim to be exhaustive. A particular emphasis has been put on geometric, functional and probabilistic tools to reach and describe measure concentration in a number of settings. As mentioned by M. Gromov, the concentration of measure phenomenon is an elementary, yet non-trivial, observation. It is often a high dimensional effect, or a property of a large number of variables, for which functions with small local oscillations are almost constant. A first illustration of this property is suggested by the example of the standard n-sphere Sn in R n + 1 when the dimension n is large. One striking aspect of uniform measure an on Sn in high dimension is that it is almost concentrated around the equator. More generally, as a consequence of spherical isoperimetry, given any measurable set A with, say, an(A) ^, almost all points (in the sense of the measure crn) on Sn are within (geodesic) distance -4= from A (which becomes infinitesimal as n oo). Precisely, for every r 0, an(Ar)l-e-(n-1)r2/2 where Ar = {x Sn d(x, A) r} is the neighborhood of order r 0 of A for the geodesic metric on Sn. This concentration property on the sphere may be described equivalently on functions, an idea going back to Levy. Namely, if F is a continuous function on Sn with modulus of continuity OOF{V) = sup{|F(x) F(y)\ d(x, y) 77}, then an({\F - mF\ CJF(V)}) 2^n~1^2 where mp is a median of F for an. Therefore, functions on high dimensional spheres with small local oscillations are strongly concentrated around a mean value, and are thus almost constant on almost all the space! This high dimensional concentration phenomenon was extensively used and emphasized by V. Milman in his investigation of asymptotic geometric analysis. vii
Previous Page Next Page