Random Processes on Graphs and Lattices

(STATS 221, Winter 2022)

• Instructor: Tselil Schramm
• Time: Mondays & Wednesdays, 11:00–13:30 Pacific
• Location: McCullough Building, Room 126
• Office hours: by appointment
• TA: Chenyang Zhong (Office Hours by appointment)

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:

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

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, and self-avoiding walks	3.1, 3.2, 3.3	The original paper of Broadbent and Hammersley, downloadable with your institutional ID.
01/26	The critical probability of L^2	5.3, 5.6
	HW3: Exercises 3.1, 3.5, 3.7, and 3.12 in Grimmett, due 2/2
01/31	Conditions for stochastic dominance & positive association (Holley and FKG inequalities)	4.1, 4.2	Notes from STATS 217 on continuous-time Markov Chains and generators.
02/02	Conditions for negative association, concentration of martingales (BK and Hoeffding inequalities)	4.3, 4.4
	HW4: Exercises 4.5 and 4.8 in Grimmett, AND additional problem on Canvas, due 2/9
02/07	Influence and sharp thresholds	4.5, 4.7	O'Donnell's Analysis of Boolean Functions is a great resource for further exploration of these topics. Chapters 2.2, 2.3 introduce influence, and chapters 8.4, 9.6, and 10.5 discuss sharp thresholds. You may find it useful to read chapters 1.2-1.4 before jumping in.
02/09	Contact model	6.1, 6.2, 6.3
	HW5: Project Proposal, and exercises 4.9 and 6.2 in Grimmett, due 2/16
02/14	Criticality in the contact model	6.4, 6.5	This monograph and the texts Stochastic Interacting Systems (parts I.2 and I.4) and Interacting Particle Systems (chapter 6.1) by Liggett contain a much fuller account of the material presented in class. The books are downloadable with your institutional ID.
02/16	Gibbs measures and Ising models	7.1, 7.3	For the Curie-Weiss phase transition, see this blog post based on chapter 2.5 of Information, Physics, and Computation by Mezard and Montanari.
	HW6: Exercise 7.3 in Grimmett, due 2/23
02/21	NO CLASS, President's Day	-	-
02/23	Counting and Sampling, sampling with Markov chains	-	The scribe notes from Alistair Sinclair's class are a great resource. The topics most relevant to today's content are counting<=>sampling, MCMC, mixing, and the analysis of Glauber Dynamics for coloring. See also the note on Ising models.
02/28	Random graphs (Erdos-Renyi graphs), connectivity and giant component phase transitions	11.1, 11.2	Chapter 11 of The Probabilistic Method by Alon and Spencer covers the giant component phase transition in much greater detail than Grimmett. You can access it online with your institutional ID.
03/02	Coloring in random graphs	11.3	Notes for a related lecture by Alistair Sinclair.
	HW7: Problem posted on Canvas, due 3/9
03/07 and 03/09	Student presentations	-	-

Additional Resources

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