MTH4240 - Mixing of finite Markov Chains

There is a more recent version of this academic item available.

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 … For more content click the Read More button below. 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.

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.

Offerings

S2-01-CLAYTON-ON-CAMPUS

Rules

Enrolment Rule

Contacts

Chief Examiner(s)

Associate Professor Tim Garoni

Unit Coordinator(s)

Associate Professor Tim Garoni

Learning outcomes

On successful completion of this unit, you should be able to:

Rigorously quantify the mixing of various classes of finite Markov chains, using a variety of techniques;

Construct appropriate classes of Markov chains to approximate complex probability distributions;

Use mixing time bounds to construct efficient randomised algorithms, for problems in areas such as combinatorics, computer science and statistical physics;

Communicate sophisticated results concerning finite Markov chains and their applications.

Assessment

1 - Continuous assessment

2 - Examination (3 hours and 10 minutes)

Scheduled and non-scheduled teaching activities

Applied sessions

Lectures

Workload requirements

Workload