## 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

- 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 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**