The Concentration of Measure Phenomenon (Mathematical Surveys & Monographs, 89)

It was undoubtedly a necessary task to collect all the results on the concentration of measure during the past years in a monograph. The author did this very successfully and the book is an important contribution to the topic. It will surely influence further research in this area considerably. The book is very well written, and it was a great pleasure for the reviewer to read it. —Mathematical Reviews The observation of the concentration of measure phenomenon is inspired by isoperimetric inequalities. A familiar example is the way the uniform measure on the standard sphere $S^n$ becomes concentrated around the equator as the dimension gets large. This property may be interpreted in terms of functions on the sphere with small oscillations, an idea going back to Lévy. The phenomenon also occurs in probability, as a version of the law of large numbers, due to Emile Borel. This book offers the basic techniques and examples 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. 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 probability theory. Particular emphasis is on geometric, functional, and probabilistic tools to reach and describe measure concentration in a number of settings. The book presents concentration functions and inequalities, isoperimetric and functional examples, spectrum and topological applications, product measures, entropic and transportation methods, as well as aspects of M. Talagrand's deep investigation of concentration in product spaces and its application in discrete mathematics and probability theory, supremum of Gaussian and empirical processes, spin glass, random matrices, etc. Prerequisites are a basic background in measure theory, functional analysis, and probability theory. Cover......Page 1 Selected Titles in This Series......Page 2 Title Page......Page 3 Copyright Page......Page 4 CONTENTS......Page 5 INTRODUCTION......Page 7 1.1 First examples......Page 11 1.2 Concentration functions......Page 13 1.3 Deviation inequalities......Page 15 1.4 Observable diameter......Page 24 1.5 Expansion coefficient......Page 25 1.6 Laplace bounds and infimum-convolutions......Page 26 Notes and Remarks......Page 31 2.1 Isoperimetric examples......Page 33 2.2 Brunn-Minkowski inequalities......Page 42 2.3 Semigroup tools......Page 48 Notes and Remarks......Page 54 3.1 Spectrum and concentration......Page 57 3.2 Spectral and diameter bounds......Page 63 3.3 Levy families......Page 65 3.4 Topological applications......Page 67 3.5 Euclidean sections of convex bodies......Page 70 Notes and Remarks......Page 75 4.1 Martingale methods......Page 77 4.2 Convex hull approximation......Page 82 4.3 Control by several points......Page 89 4.4 Convex infimum-convolution......Page 92 4.5 The exponential distribution......Page 93 Notes and Remarks......Page 99 5.1 Logarithmic Sobolev inequalities and concentration......Page 101 5.2 Product measures......Page 107 5.3 Modified logarithmic Sobolev inequalities......Page 111 5.4 Discrete settings......Page 118 5.5 Covariance identities......Page 124 Notes and Remarks......Page 125 6.1 Information inequalities and concentration......Page 127 6.2 Quadratic transportation cost inequalities......Page 132 6.3 Transportation for product and non-product measures......Page 136 Notes and Remarks......Page 142 7.1 Gaussian processes......Page 143 7.2 Bounds on empirical processes......Page 148 7.3 Sharper bounds via the entropic method......Page 152 Notes and Remarks......Page 159 8.1 Concentration of harmonic measures......Page 161 8.2 Concentration for independent permutations......Page 165 8.3 Subsequences, percolation, assignment......Page 169 8.4 The spin glass free energy......Page 173 8.5 Concentration of random matrices......Page 177 Notes and Remarks......Page 180 REFERENCES......Page 181 INDEX......Page 191 The observation of the concentration of measure phenomenon is inspired by isoperimetric inequalities. A familiar example is the way the uniform measure on the standard sphere $S^n$ becomes concentrated around the equator as the dimension gets large. This property may be interpreted in terms of functions on the sphere with small oscillations, an idea going back to Levy. The phenomenon also occurs in probability, as a version of the law of large numbers, due to Emil Borel. This book offers the basic techniques and examples 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. 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 probability theory. Particular emphasis is on geometric, functional, and probabilistic tools to reach and describe measure concentration in a number of settings. The book presents concentration functions and inequalities, isoperimetric and functional examples, spectrum and topological applications, product measures, entropic and transportation methods, as well as aspects of M. Talagrand's deep investigation of concentration in product spaces and its application in discrete mathematics and probability theory, supremum of Gaussian and empirical processes, spin glass, random matrices, etc. Prerequisites are a basic background in measure theory, functional analysis, and probability theory. Michel Ledoux. Includes Bibliographical References (p. 171-179).