Quicklinks: Back to my homepage

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

- [vdH] Random Graphs and Complex Networks. Vol. I by van der Hofstad
- [LP] Probability on Trees and Networks by Lyons with Peres
- [LPW] Markov Chains and Mixing Times by Levin, Peres and Wilmer
- [St] A Mini Course on Percolation Theory by Steif
- [Gr] Probability on Graphs by Grimmett
- [Lu] Concentration-of-measure Inequalities by Lugosi
- [Ve] High-dimensional probability: An introduction with applications in data science by Vershynin

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)

**Review:**basics of graph theory and Markov chain theory.**Models:**percolation, random graphs, Markov random fields, random walks on networks, interacting particles on finite graphs.

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

**Techniques:**first moment method, second moment method, Chernoff-Cramer method, chaining.**Examples:**random k-SAT threshold, percolation on trees and lattices (critical value), Erdos-Renyi graph (containment, connectivity), Markov chains (Varopoulos-Carne), Johnson-Lindenstrauss, VC theory.

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

**Review:**stopping times, martingales.**Techniques:**concentration for martingales, method of bounded differences, slicing method, electrical networks.**Examples:**Markov chains (hitting times, cover times, recurrence), percolation on trees (critical regime), Erdos-Renyi graphs (chromatic number), preferential attachment graphs (degree sequence), uniform spanning trees (Wilson's method), bandit problems.

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

**Review:**definition of coupling.**Techniques:**coupling inequality, stochastic domination, correlation inequalities (FKG, Holley), couplings of Markov chains.**Examples:**harmonic functions on lattices and trees, Markov chains (mixing time, Glauber dynamics), Erdos-Renyi graph (degree sequence, Janson's inequality), percolation on lattices (RSW theory, Harris' theorem), and Ising model on lattices (extremal measures).

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

**Review:**spectral theorem, Courant-Fischer, perturbation, spectral graph theory.**Techniques:**spectral gap, canonical paths, bottleneck ratio, expander graphs.**Examples:**Markov chains (mixing time, Glauber dynamics), percolation on lattices (uniqueness of infinite cluster) and on Galton-Watson trees, stochastic traveling salesman.

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

**Review:**Galton-Watson processes, extinction.**Techniques:**Random-walk representation, duality principle, comparison to branching processes.**Examples:**percolation on trees (critical exponents) and on Galton-Watson trees, Erdos-Renyi graph (phase transition).

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

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

- Slides for Chapter 1 (Part 1), Slides for Chapter 1 (Part 2) (last updated: sep 25, 2020)
- Slides for Chapter 3 (last updated: jan 2, 2015)
- Slides for Chapter 4 (last updated: nov 29, 2014)
- Slides 1/review 1 (spectral theorem and spectral graph theory), slides 2/review 2 (matrix perturbation results), slides 3 (stochastic blockmodel and community detection), slides 4 (spectral techniques for Markov chains), for Chapter 5 (last updated: nov 30, 2020)
- Slides for Chapter 6 (last updated: nov 15, 2014)

Last updated: dec 14, 2020.