## 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~~ broadcast from an undisclosed location - see blackboard for the zoom link.

**Office hours**

Monday 12:30-1:30 or by arrangement. ~~Room 405 Fine Hall.~~ See blackboard announcement for zoom link.

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 coupling Roch 4.4.3, LPW Chapter 14

**Mar 4**: Coupling: Mixing times and coupling Roch 4.4.3, LPW Chapter 14

**Mar 9**: Path Coupling, MCMC, Approximate Counting: LPW Chapter 14.3, 14.4, 15.1

**Mar 11**: Spectral Methods for Markov Chains: LPW Chapter 12.1, 12.2, 13.3

**Mar 23**: Monotone coupling and FKG: Roch 4.3

**Mar 25**: Percolation threshold and Kesten's Theorem Roch: 4.3.6

**Mar 30**: Spin systems and decay of correlation

**Apr 1**: Spin systems: Phase transitions and slow mixing

**April 6**: Local Weak Convergence

**April 8 **: Random graph component sizes (supercritical and subcritical) Roch 5.3.3

**April 13**: Random graph component sizes (critical) Roch 5.3.3

**April 15**: Scaling limits of random trees Random trees and applications Section 1

**April 20**: Cardy's formula: conformal invariance of critical percolation Yadin Section 10

**April 22 **: Cardy's formula: conformal invariance of critical percolation

**April 27**: Discrete Fourier Analysis, Hypercontractivity

**April 29 **: KKL, Improved variance bounds for First Passage Percolation
## 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**

**FKG**

**Decay of Correlation**

**Scaling Limits and Local Weak Convergence**

**Cardy's Formula**

**Discrete Fourier Analysis**

## Problem Sets

**Problem Set 1**

**Problem Set 2**

**Problem Set 3**