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

Instructor Allan Sly (asly@princeton)

Class time 1:30-3:00 on Tuesdays and Thursdays at 601 Fine Hall.

Office hours
Monday 12:30-1:30 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: 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 the semester plus a final longer problem set due on deans date. The first three may be done in groups while the final one should be done individually. 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.

Schedule

Moments and Concentration


Feb 3: Introduction. First moment method. Percolation phase transition. Roch 2.1, 2.2
Feb 5: Second moment method. Random graph connectivity. Poisson approximation. Roch 2.1, 2.2
Feb 10: Large deviations: Cramer's Theorem. Dembo and Ofer Zeitouni 2.2
Feb 12: Large deviations: Sanov's Theorem. Dembo and Ofer Zeitouni 2.2
Feb 17: Azuma-Hoeffding: Roch 3.2
Feb 19: Ergodic Theorem and 0/1 Laws: Uniqueness of percolation clusters: Durrett Probability 7.1, 7.2
Feb 24: Coupling: Roch 4.1, 4.2
Feb 26: Coupling and Mixing Times: Roch 4.4
Mar 2: Coupling: Mixing times and path coupling Roch 4.4.3, LPW Chapter 14
Mar 4: Path Coupling, MCMC, Approximate Counting: LPW Chapter 14.3, 14.4, 15.1

Lecture Notes


These are the handwritten notes I use to prepare my lectures. They include occasional comments to myself like, explain this better next time :)
Tails and Concentration
Ergodic Theory
Coupling
Mixing Times

Problem Sets


Problem Set 1