Random Processes on Graphs and Lattices

(STATS 221, Winter 2022)

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).

Course description

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:

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).

Lectures and Reading
Below is a preliminary schedule (subject to change), including the textbook chapters relevant to each lecture.

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 "
HW1: Exercises 1.6, 1.7, 1.11, and 1.13 in Grimmett, due 1/12
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
HW2: Exercises 2.1 and 2.5 in Grimmett, AND additional problem posted on Canvas, due 1/19
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 - -
Additional Resources