The topic of this course will be the study of fluctuations of functions of many independent random variables. An archetypal example is the sum of independent identically distributed random variables. Concentration inequalities bound the probability that such a function differs from its expectation/median by more than a certain amount. The search for concentration inequalites has been a popular topic of research in the last deacades because of their importance in numeruos applications in discrete mathematics, statistical mechanics, information theory, high-dimensional geometry, and others.

In this course, which will closely follow the book of Boucheron, Lugosi, and Massart, we shall present several different approaches to answering the following general question: What kind of conditions should one impose on a function f of independent random variables X_{1}, ..., X_{n} in order to obtain concentration bounds for f(X_{1}, ..., X_{n}) around its mean or its median? In particular, we shall discuss: the martingale method, the entropy method, the transportation method, and concentration via isoperimetry.

Students enrolling in the course are expected to have working knowledge of basic probability theory.

S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013

D. P. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2012

October 21

Markov's inequality; variance and Chebyshev's inequality; the log moment generating function and the Crámer–Chernoff method; Crámer transforms of normal, Poisson, and Bernoulli random variables and of sums of i.i.d. random variables; sub-Gaussian random variables

October 28

Lower bounds for tail probabilities of sums of i.i.d. random variables (Crámer's theorem); equivalent characterizations of sub-Gaussian random variables; Hoeffding's inequality; Bennett's inequality; Bernstein's inequality; the Johnson–Lindenstrauss lemma

November 4

Proof of the Johnson–Lindenstrauss lemma; Noga Alon's lower bound for the dimension in the Johnson–Lindenstraus lemma; conditional expectations and L

^{2}-orthogonality of martingale differences; the Efron–Stein inequality; applications of the Efron–Stein bound for variance: functions with bounded differences, bin packing

November 11

Further applications of the Efron–Stein inequality: longest common subsequence, Rademacher averages, first passage percolation, the largest eigenvalue of a random symmetric matrix, minimum weight spanning tree; self-bounding functions

November 18

Examples of self-bounding functions: increasing subsequences, the number of distinct values in a discrete sample; a convex Poincaré inequality; the largest singular value of a random matrix; two approaches to obtaining exponential bounds on tail probabilities via the Efron–Stein inequality

November 25

Gaussian Poincaré inequality; self-information and Shannon's entropy; Kullback–Leibler divergence (relative entropy); basic properties of entropy; Han's inequality; edge-isoperimetry in the hypercube and influences

December 2

Edge-isoperimetry in the hypercube and influences: Han's inequality versus the Efron–Stein inequality; the entropy of a nonnegative random variable; entropy and concentration: a sketch of Herbst's argument; sub-additivity of entropy (discrete case); Han's inequality for relative entropies

December 9

Influences under non-uniform product distribution; dual characterization of entropy; sub-additivity of entropy (general case); logarithmic Sobolev inequality for the hypercube; Herbst's argument; concentration inequalities for functions of independent Rademacher variables

December 16

Shearer's lemma and the maximum number of independent sets in regular bipartite graphs (Kahn's theorem); Gaussian logarithmic Sobolev inequality; the Tsirelson–Ibragimov–Sudakov inequality; the bounded differenes inequality; Bregman divergence

December 23

The mean minimizes the expected Bregman divergence; the lenght of a sum of random vectors via bounded differences inequality; a modified logarithmic Sobolev inqequality; a strengthening of the bounded differences inequality; concentration of the largest eigenvalue of a symmetric random matrix; concentration inequalities for self-bounding functions; the maximum degree of G(n,p)

December 30

Isoperimetry and concentration of Lipschitz functions; Lévy's inequalities; the classical isoperimetric inequality in ℝ

^{n}; the Brunn–Minkowski inequality; vertex isoperimetry in the hypercube (Harper's theorem, without full proof); Talagrand's convex distance inequality

January 6

Concentration inequalities for functions with (non-uniformly) bounded differences via Talagrand's inequality; traveling salesman problem for random points in the unit square; coupling distance between probability measures; transportation cost inequalities and isoperimetry

January 13

Pinsker's inequality; tensorization of transportation cost; bounded differences inequality revisited; quadratic transportation cost; logarithmic moment generating function and Kullback–Leibler divergence; Marton's theorem