MAT 589

MAT 589 Topics in Probability, Statistics and Dynamics: Modern discrete probability theory (Spring 2017)

Instructor Allan Sly (asly@princeton)

Class time 9:30-11:00 on Tuesdays and Thursdays at 401 Fine Hall.

Office hours
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

Percolation.
Random graphs and networks.
Spin systems and random constraint satisfaction problems.
Random walks and Markov chains.

The course will be structured around a selection of the essential techniques in the area. We will cover:

Moments and concentration.
Coupling.
Scaling limits.

Depending on time we may also cover other topics such as multi-scale methods and the analysis of Boolean functions.

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.

Grading

There will be about three problem sets over he semester, which may be done in groups. There will be no final exam.

Reference material

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.

Random Graph Dynamics by Rick Durrett.
Random Graphs and Complex Networks by Remco van der Hofstad
Markov Chains and Mixing Times by Levin, Peres and Wilmer
A Mini Course on Percolation Theory by Jeff Steif
Large Deviations Techniques and Applications by Amir Dembo and Ofer Zeitouni
Percolation by Geoffrey Grimmett
Probability on Graphs by Geoffrey Grimmett
Probability: Theory and Examples by Rick Durrett

Schedule

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

Problem Sets

There will be three problem sets for the class posted here:
Problem Set 1: Due March 17 [pdf] [Solutions]

Problem Set 2: Due April 21 [pdf]

Problem Set 3: Due May 16 [pdf]