MAT 589 Topics in Probability, Statistics and Dynamics: Modern discrete probability theory (Spring 2020)
Class time 1:30-3:00 on Tuesdays and Thursdays at 601 Fine Hall.
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:
- 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 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.
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 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
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
Problem Set 1