- Instructor: Tselil Schramm
- Time: Mondays & Wednesdays, 11:00–13:30 Pacific
- Location: McCullough Building, Room 126
- Office hours: Wednesdays 14:00–15:30, or by appointment
- TAs: Marius Tirlea (Office Hours TBA), Chenyang Zhong (Office Hours Tuesdays 09:00–10:30)

A detailed overview of course policies (including grading and homework) can be found in the course syllabus.

**Course text:**
We will use "Probability on Graphs," 2nd ed., by Geoffrey Grimmet.
You may use this free preprint.

**Prerequisites:**
MATH 115, "Functions of a real variable" (or equivalent), and STATS 217, "Introduction to Stochastic Processes" (or equivalent).

Building on undergraduate probability (STATS 116), and on previous exposure to Markov chains (STATS 217), we'll cover modern topics in the study of random processes on graphs and lattices, in a non-measure-theoretic way. Specifically:

- The connection between reversible Markov chains, electrical networks and flows.
- The study of random graphs, uniform spanning trees, Percolation and self-avoiding walks.
- Dynamics of interacting particles: the contact process, voter model and the exclusion process.
- Gibbs states, in particular the Ising, Potts and Random-Cluster models.

We'll see the power of simple random models to illuminate real-world phenomena arising in physical systems, epidemiology, politics, population dynamics, and more. By focusing on discrete objects, we will see complete proofs without requiring measure theory or functional analysis. In contrast with STATS 217, many of the topics we cover are at the forefront of research in discrete probability (and over the course of the term, we will state a few well known open problems and tantalizing conjectures).

Date | Topic | Grimmet Chapters | Related Reading |
---|---|---|---|

01/03 | Random walks on graphs, intro electrical networks and flows | 1.1, 1.2, 1.6 | Random walks and electric networks by Doyle and Snell |

01/05 | Effective resistance and recurrence | 1.3, 1.4 | " |

| |||

01/10 | Recurrence continued, and Polya's Theorem | 1.4, 1.5 | " |

01/12 | Uniform spanning trees and Wilson's Algorithm | 2.1, 2.2 | |

| |||

01/17 | NO CLASS, Martin Luther King Jr. Day | - | - |

01/19 | Approximate sampling of uniform spanning trees via matroid basis exchange | Lecture notes as presented in class | The lecture notes contain some references. See also the original paper and the lecture notes of Shayan Oveis Gharan |

01/24 | Percolation & phase transitions | 3.1, 3.4 | |

01/26 | Self-avoiding walks | 3.1, 3.2 | |

01/31 | Conditions for stochastic dominance & positive association | 4.1, 4.2 | |

02/02 | Conditions for negative association, concentration of martingales | 4.3, 4.4 | |

02/07 | Influence and thresholds | 4.5, 4.7 | |

02/09 | Contact model | 6.1, 6.2 | |

02/14 | Criticality for the contact model | 6.3, 6.4 | |

02/16 | Criticality continued, & contact model on trees | 6.4, 6.5 | |

02/21 | NO CLASS, President's Day | - | - |

02/23 | Ising and Potts models | 7.1, 7.3 | |

02/28 | Ising and Potts models, continued | 7.2 | |

03/02 | Random cluster model | 8.1, 8.2 | |

03/07 and 03/09 | Student presentations | - | - |

- Here is the website for the previous iteration of this course, taught by Amir Dembo.