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.
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).
|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, 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|
|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|
|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|
|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.|
|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.|
|03/07 and 03/09||Student presentations||-||-|