Short Course Description
This course provides an introduction to modern techniques in the analysis of random structure in high dimension, with an emphasis on applications in information theory, communications, statistics, random matrix theory, combinatorics, and learning. The course will cover a subset of the following topics, time permitting: Introduction and basic inequalities (Markov, Chebyshev, Chernoff). The concentration-of measure phenomenon. Variance bounds and the Efron-Stein inequality. Introduction to Markov semigroup theory. Poincare inequalities (PI): exponential ergodicity, tensorization, the Orenstein-Uhlenbeck semigroup and the Gaussian PI, Sturm-Liouville semigroups and PI on an interval, the spectral gap. Basic Subgaussian concentration: Hoeffding lemma, McDiarmid's inequality. The Entropy method: Tensorization of entropy, Logarithmic Sobolev inequalities (LSI), Gaussian LSI. Connections to isoperimetry, hypercontractivity, and strong data processing inequalities. The Transportation method: Marton's inequality, Talagrand's inequality. Influence and threshold phenomena. Suprema of random processes.
Full Syllabus
