After successful completion of the course, students are able to...

...describe and analyze random walks on graphs

...describe the relationship between the geometry of the graph and the long term behavior of the random walk, in particular

...characterize recurrence and transience in terms of the electrical properties of the graph

...investigate questions of convergence towards the stationary distribution (mixing times, spectral gap) for finite-state Markov chains

This course is about Markov chains (mostly: reversible) on (large or infinite) graphs, and the focus will be on asymptotic properties, like recurrence and transience, and the approach to the stationary measure in the large-time limit. I will make connections to several central topics in (mathematical) statistical mechanics: the Gaussian free field, loop-erased random walks and uniform spanning trees, Glauber dynamics of the Ising model…

Part I Random walks and electric networks

• Discrete Dirichlet form, energy, effective resistances/conductances
• Characterization of the asymptotic behavior via the network resistance
• Gaussian Free Field on a graph
• Loop-erased random walk
• Uniform random spanning tree of a graph: Wilson’s algorithm and determinantal correlations (Burton-Pemantle theorem)

Part II Random walks on finite graphs: speed of convergence

• Mixing time T mix (reversible and non-reversible random walks)
• T mix upper bounds: path coupling and weighted distances
• Spectral gap, variational principle and time correlations
• Bounding the spectral gap: geometric comparison methods
• The cutoff phenomenon

Lecture and homework problems

Exam

Basics of probability theory and stochastic processes and  of Markov Chains