Some topics in measure concentration I

Tim Austin
University of California, Los Angeles (UCLA)

A random variable is `concentrated' if it stays close to a fixed constant with high probability. The most basic examples are long averages of i.i.d. random variables, whose concentration is promised by the law of large numbers. However, concentration occurs in many other settings, even when exact calculations of moments or other parameters are impossible. This is because concentration often results from some natural `geometric' structure on the underlying probability space. For instance, large classes of random variables exhibit concentration because they are Lipschitz functions on certain `high-dimensional' spaces that carry both metrics and probability measures, such as Hamming cubes or high-dimensional spheres.

Lecture 1 will introduce concentration from this geometric point of view, and prove concentration inequalities for Lipschitz functions on some simple examples of such spaces. This lecture will assume some familiarity with graduate measure theory and real analysis, and a good knowledge of undergraduate probability. Measure-theoretic probability and some Riemannian geometry will be helpful, but not essential.

Presentation (PDF File)

Back to Quantitative Linear Algebra Tutorials