Quicklinks: Back to my homepage

Modern Discrete Probability: An Essential Toolkit

(Lecture notes)

Sebastien Roch, UW-Madison


The goal of these notes is to give an introduction to fundamental models and techniques in graduate-level modern discrete probability. Topics covered are taken mostly from probability on graphs: percolation, random graphs, Markov random fields, random walks on graphs, etc. No attempt is made at covering these areas in depth. Rather the emphasis is on illustrating common and important techniques.

The notes are aimed at graduate students in mathematics, statistics, computer science, electrical engineering, physics, economics, etc. with previous exposure to basic probability theory (ideally measure-theoretic probability theory; at Wisconsin, Math 733; my own course notes) and stochastic processes (at Wisconsin, Math 632). These notes were developed for a one-semester course at UW-Madison (Fall 2014, Fall 2017 and Fall 2020). I also gave a version of this course at the TRIPODS Summer School on Fundamentals of Data Analysis. The slides are here.

Slides for background sections are also available below.

Much of the material covered can also be found in the following excellent texts (conveniently available online):

Lectures Notes

Notes in one file (last updated: nov 19, 2020)

Table of contents (last updated: nov 19, 2020)

Chapter 1: Introduction (last updated: sep 25, 2020)

Chapter 2: Moments and tails (last updated: oct 7, 2020)

Chapter 3: Martingales and potentials (last updated: oct 17, 2020)

Chapter 4: Coupling (last updated: nov 19, 2020)

Chapter 5: Spectral methods (last updated: nov 19, 2020)

Chapter 6: Branching processes (last updated: nov 19, 2020)

Appendix, bibliography and index (last updated: nov 19, 2020)


Slides covering mostly background material (and more) in each chapter:

Last updated: dec 14, 2020.