Quicklinks: Back to my homepage

Modern Discrete Probability: An Essential Toolkit

Published by Cambridge University Press

Sebastien Roch, Department of Mathematics, UW-Madison


The goal of these notes is to give an introduction to fundamental models and techniques in graduate-level modern discrete probability. Topics 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 developing and illustrating common and important techniques. Various applications, in particular in the theoretical foundations of data science and machine learning, are also discussed along the way.

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, Fall 2020, and Fall 2023). 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):

Print copy

A hard copy of the book is available for pre-order on Amazon. The official publisher's page for the book is here. An errata for the print copy is forthcoming (email me if you find typos). To cite these notes, please use the following BibTeX entry:

series={Cambridge Series in Statistical and Probabilistic Mathematics},
title={Modern Discrete Probability: An Essential Toolkit},
publisher={Cambridge University Press},
author={Roch, Sebastien},
collection={Cambridge Series in Statistical and Probabilistic Mathematics}

Lectures Notes

Full notes in one file (12MB) (updated: dec 20, 2023)

Front matter (table of contents, preface, notation) (updated: dec 20, 2023)

Chapter 1: Introduction (updated: dec 20, 2023)

Chapter 2: Moments and tails (updated: dec 20, 2023)

Chapter 3: Martingales and potentials (updated: dec 20, 2023)

Chapter 4: Coupling (updated: dec 20, 2023)

Chapter 5: Spectral methods (updated: dec 20, 2023)

Chapter 6: Branching processes (updated: dec 20, 2023)

Back matter (appendices, bibliography, index) (updated: dec 20, 2023)


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

Last updated: dec 20, 2023.