MTH5240 · Mixing of Finite Markov chains

Overview

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; Randomized algorithms and fpras; Spectral methods and relaxation time; the cutoff phenomenon.

Offerings

Assessment

The Handbook lists an examination for this unit.

Assessment details may change. Please refer to the assessment information in Moodle closer to the start of the teaching period.

Requisites

The Handbook lists no prerequisite, corequisite or prohibition for this unit.

Learning outcomes

1. Rigorously quantify the mixing of various classes of finite Markov chains, using a variety of techniques;
2. Construct appropriate classes of Markov chains to approximate complex probability distributions;
3. Use mixing time bounds to construct efficient randomized algorithms, for problems in areas such as combinatorics, computer science and statistical physics;
4. Communicate sophisticated results concerning finite Markov chains and their applications.

Workload

• 3 1-hour seminars; • 1-hour of applied classes and • 8 hours independent study per week

Student experience, not official rules. Nothing here changes what the Handbook says.