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

Part II Random walks on finite graphs: speed of convergence

Lecture and homework problems

Exam

Basics of probability theory and stochastic processes and of Markov Chains