MTH5240 Mixing of Finite Markov chains
Faculty of Science
MTH5240 Mixing of Finite Markov chains is a level 5, 6-credit-point, postgraduate unit from the Faculty of Science, offered in 2022 in Semester 2 at Clayton. It has no prerequisites.
- Credit points
- 6
- Offered in 2022
- Semester 2
- Clayton
- Assessment
- Exam 60%
- and 1 other task
This is the 2022 handbook entry. See the 2027 entry.
Reviews
No reviews yetNo reviews yet. Be the first to review MTH5240.
Requisites
Before MTH5240
No prerequisites or corequisites besides the enrolment rules below.
After MTH5240
No unit lists MTH5240 as a prerequisite in the 2022 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; Randomized algorithms and fpras; Spectral methods and relaxation time; the cutoff phenomenon.
Offerings in 2022
| Teaching period | Campus | Mode |
|---|---|---|
| Second semester | Clayton | On campus |
Assessment
- Continuous assessmentOther40%
- Examination (3 hours and 10 minutes)ExamThreshold 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 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 and teaching
- Applied sessions12 hours
- Lectures36 hours
- 3 1-hour lectures
- 1-hour of applied classes and
- 8 hours independent study per week
Contacts
- Unit Coordinators
- Associate Professor Tim Garoni
- Chief Examiners
- Associate Professor Tim Garoni
Common questions
What are the prerequisites for MTH5240?
MTH5240 has no prerequisites, but enrolment rules apply.
When is MTH5240 offered?
In 2022, MTH5240 runs in Semester 2 at Clayton.
Does MTH5240 have an exam?
Yes. The exam is worth 60% of the final mark, alongside 1 other task.