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):
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).
Examples:
Markov chains (mixing time, Glauber dynamics),
percolation on lattices (uniqueness of infinite cluster) and on Galton-Watson trees,
stochastic traveling salesman.