Mixing of finite Markov Chains

The classical theory of Markov chains focusses on the large-time asymptotics of chains defined on a fixed set of states. More recently, motivated by applications to combinatorics, computer science and statistical physics, emphasis has shifted to asymptotics as the number of states becomes large. This unit focusses on this more modern theory, in which the central question is how the rate of mixing of a class of Markov chains behaves as the number of states increases.

Topics to be covered include: Mixing time; Coupling; Random walks on groups; Path coupling; Markov chain Monte Carlo; Metropolis and Glauber processes; Randomised algorithms and fpras; Spectral methods and relaxation time; the cutoff phenomenon.