MAT 589 Topics in Probability, Statistics and Dynamics: Modern discrete probability theory (Spring 2017)
Class time 9:30-11:00 on Tuesdays and Thursdays at 401 Fine Hall.
Tuesday 11:00-12:00 or by arrangement. Room 405 Fine Hall.
The aim of this course is to survey some of the fundamentals of modern discrete probability, particularly random processes on networks and discrete structures. We will cover the classic results and arguments of
The course will be structured around a selection of the essential techniques in the area. We will cover:
- Random graphs and networks.
- Spin systems and random constraint satisfaction problems.
- Random walks and Markov chains.
Depending on time we may also cover other topics such as multi-scale methods and the analysis of Boolean functions.
- Moments and concentration.
- Scaling limits.
The target audience is PhD students both from mathematics and other departments (e.g. ORFE, CS, EE) who expect aspects of discrete probability theory to play an important role in their research. The course will try to give as broad as possible an outline of the classic results in the area and to give familiarity with the proof techniques, tricks and heuristics of the field.
There will be about three problem sets over he semester, which may be done in groups. There will be no final exam.
The course is partially based on one developed by Sebastien Roch whose excellent lecture notes can be found here. Some good references to the various for the different models in the class are available online here.
Moments and Concentration
Feb 7: Introduction. First moment method. Percolation phase transition. Roch 2.1, 2.2
Feb 9: Second moment method. Random graph connectivity. Poisson approximation. Roch 2.1, 2.2
Feb 14: Large deviations: Cramer’s Theorem. Dembo and Ofer Zeitouni 2.2
Feb 16: Large deviations: Sanov’s Theorem. Dembo and Ofer Zeitouni 2.2
Feb 21: Azuma-Hoeffding: Roch 3.2
Feb 23: Ergodic Theorem and 0/1 Laws: Uniqueness of percolation clusters: Durrett Probability 7.1, 7.2
Feb 28: Sub-additive Ergodic Theorem: Limit shape for first passage percolation: Durrett Probability 7.4
Mar 2: Coupling: Roch 4.1, 4.2
Mar 7: Coupling and Mixing Times: Roch 4.4
Mar 9: Coupling: Roch 4.4.3, LPW Chapter 14
Mar 14: Cancelled (Snow)
Mar 16: Path Coupling, MCMC, Approximate Counting: LPW Chapter 14.3, 14.4, 15.1
Mar 28: Spectral Methods for Markov Chains: LPW Chapter 12.1, 12.2, 13.3
Mar 30: Monotone coupling and FKG: Roch 4.3
April 4: Percolation threshold and Kesten's Theorem Roch 4.3.6
April 6: Spin systems and decay of correlation
April 11: Spin systems: Gibbs measures - Grimmett Probability on Graphs Chapter 7
April 13: Spin systems: Phase transitions and slow mixing
April 18: Local Weak Convergence
April 20: Random graph component sizes (supercritical and subcritical) Roch 5.3.3
April 25: Random graph component sizes (critical) Roch 5.3.3
April 27: Scaling limits of random trees Random trees and applications Section 1
May 2: Cardy's formula: conformal invariance of critical percolation Yadin Section 10
May 4 : Cardy's formula: conformal invariance of critical percolation
There will be three problem sets for the class posted here:
Problem Set 1: Due March 17 [pdf]
Problem Set 2: Due April 21 [pdf]
Problem Set 3: Due May 16 [pdf]