MATH 581F - Martingales & Concentration

Martingales & Concentration: Theory and Applications

Math 581F, Fall 2012


Instructor:Eyal Lubetzky
Email: eyal [at] math [dot] washington [dot] edu
Office hours: by appointment

Meeting Times and Locations
Wed,Fri 2:30-3:45 at LOW 116.

Course description
The applications of probability to many areas in Mathematics and in other fields have multiplied dramatically in recent years. Rich interactions with classical analysis have been found in the study of random fractals; researchers in Combinatorics, Theoretical CS, high-dimensional geometry (and, of course, Statistics) increasingly need sophisticated probabilistic tools. The aim of this course is to provide such tools, with main focus on martingales and their applications. These will include: concentration inequalities, optional stopping, L2 martingales, maximal inequalities and much more.

Topics
  1. Optional stopping theorems. Hitting times of Simple Random Walks; exponential martingales; L1 Maximal Inequality; biased random walks on Z; noise-sensitivity of Boolean functions; hitting times for binary patterns; critical random graphs.
  2. Martingale convergence theorems. Doob's upcrossing inequality; Lévy's Forward Theorem; Backward martingales; martingales in L2.
  3. Concentration. Hoeffding's inequality; large deviations for hypergeometric variables; Bernstein's inequality; Freedman's inequality; large deviations in higher dimensions; large deviations for matrices.
  4. Analytic & geometric aspects. Uniform integrability; Doob's Lp Maximal Inequality; product martingales and absolute continuity; Kakutani's theorem; weak martingales; Brownian martingales; Markov types of metric spaces.

Textbook
Probability with Martingales by David Williams, Cambridge University Press, Cambridge, 1991.