MTH4240 Mixing of finite Markov Chains
Faculty of Science
MTH4240 Mixing of finite Markov Chains is a level 4, 6-credit-point, undergraduate and postgraduate unit from the Faculty of Science, offered in 2021 in Semester 2 at Clayton. It has no prerequisites.
- Credit points
- 6
- Offered in 2021
- Semester 2
- Clayton
- Assessment
- Exam 60%
- and 1 other task
This is the 2021 handbook entry. See the 2026 entry.
Reviews
No reviews yetNo reviews yet. Be the first to review MTH4240.
Requisites
Before MTH4240
No prerequisites or corequisites besides the enrolment rules below.
After MTH4240
No unit lists MTH4240 as a prerequisite in the 2021 handbook.
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; Randomised algorithms and fpras; Spectral methods and relaxation time; the cutoff phenomenon.
Offerings in 2021
| Teaching period | Campus | Mode |
|---|---|---|
| Second semester | Clayton | On campus |
Assessment
- Continuous assessmentOtherThreshold hurdle40%
- Examination (3 hours and 10 minutes)ExamCompetency hurdle60%
Learning outcomes
When you finish this unit, you should be able to:
- 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 randomised 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 and teaching
- Lectures36 hours
- Applied sessions12 hours
- Three hours of lectures
- One hour of applied sessions, and
- Eight hours independent study per week
Contacts
- Chief Examiners
- Associate Professor Tim Garoni
- Unit Coordinators
- Associate Professor Tim Garoni
Common questions
What are the prerequisites for MTH4240?
MTH4240 has no prerequisites, but enrolment rules apply.
When is MTH4240 offered?
In 2021, MTH4240 runs in Semester 2 at Clayton.
Does MTH4240 have an exam?
Yes. The exam is worth 60% of the final mark, alongside 1 other task.