MATHEMATICAL MODELLING OF MARKOV CHAIN MONTE CARLO - 2020/1

Module Overview

This module is designed to be an introduction to the ideas, techniques and applications of Markov Chain Monte Carlo (MCMC) methods. MCMC has been a very common, standard tool in physics, and now it is widely used in other fields as well. The goal of this module is to understand the basic idea, write a few simulation codes, and perform the simulations. In most textbooks, rather abstract arguments are given without providing simple examples, and it is not easy to understand how MCMC can actually be used practically. In this module, we use simple examples from which all the essence can be understood. In fact, the one-variable Gaussian integral via MCMC already teaches us various lessons. In all lectures, sample codes are provided, and students will develop the intuition by running them, and also by modifying them for slightly different problems.

In Part I, we learn naïve Monte Carlo. By understanding when and how a naïve method fails, we can see the importance of MCMC.

In part II, four ingredients of MCMC are given: (i) Markov Chain, (ii) irreducibility, (iii) aperiodicity, (iv) detailed balance. We will understand the meanings of these ingredients by using simple examples.

In Part III, the Metropolis algorithm, which is the simplest type of MCMC, is introduced. We apply this algorithm to simple integrals and learn how MCMC works in practice. As meaningful applications, we apply it to some Bayesian analyses. If time permits, we also consider the optimization problems such as the traveling salesman problem.

Parts IV, V and VI introduce more advanced algorithms, which are useful for realistic, large-scale problems.

Module provider

Mathematics

Module Leader

HANADA Masanori (Maths)

Number of Credits: 15

ECTS Credits: 7.5

Framework: FHEQ Level 7

Module cap (Maximum number of students): 30

Module Availability

Semester 2

Prerequisites / Co-requisites

N/A

Module content

Indicative content includes: 

I) Introduction to a naïve Monte Carlo method (which is not MCMC). Perform simple integrals in a few different methods. Understand when naïve methods can work, and when more sophisticated methods are needed. A few sample codes are provided, and it is demonstrated how the codes are compiled and the jobs are executed on a computer. [1 Week]

II) General framework of MCMC. [1 Week]

III) Metropolis algorithm, and application to simple integrals and Bayesian analysis. We will also learn basic concepts which are important in any MCMC methods, such as thermalization and error analysis. If time permits we will solve the traveling salesman problem. For a few basic problems, the students will write their own codes by modifying the sample codes, and perform the analyse by themselves. [4 weeks]

IV) Gibbs sampling algorithm. What is the advantage and disadvantage? What can we do by combining Gibbs sampling and Metropolis? The students will write their own codes by modifying the sample codes. [1 Week]

V) Metropolis-Hastings algorithm. It gives a useful framework to understand various MCMC methods, including Gibbs sampling and HMC. The students will write their own codes by modifying the sample codes. [1 Week]

VI) Hybrid Monte Carlo (HMC) algorithm. It is also called “Hamiltonian” Monte Carlo. The HMC algorithm is designed by using the intuition from physics. The essence of this algorithm is explained by using simple, everyday-experience as example. The students will write their own codes by modifying the sample codes. [3 Weeks]

Assessment pattern

Alternative Assessment

N/A

Assessment Strategy

The assessment strategy is designed to provide students with the opportunity to demonstrate

a) The ability to understand the Monte Carlo methods.
b) The ability to perform the simulations and solve concrete problems.
c) A knowledge of the subject, important definitions, and concepts

Thus, the summative assessment for this module consists of:
1) Three assessed courseworks, which consist of the coding and analysis of the simulation results; worth 15%, 15% and 35%.
2) In case the students cannot use coding software in University computer labs (especially due to a possible lockdown or other measures related to the coronavirus pandemic), other tasks may be given.
3) One final examination worth 35%

Formative assessment and feedback

There is feedback from marked coursework assignments over an 11-week period.
Verbal feedback is provided by the lecturer during seminars, and also in office hours.

Module aims

• Introduce students to the numerical simulations based on MCMC.
• Give the students some experience in actual numerical
  simulations and code writing.
• Give the students other useful skills such as the error estimate in the numerical studies.

Learning outcomes

Methods of Teaching / Learning

The learning and teaching strategy is designed to:

1) Give motivation for using MCMC to model practical problems. [Part I]

2) Convey understanding about the essence of MCMC and its practical applications [Parts II, III]

3) Show how more advanced techniques can be used to solve numerically demanding problems which otherwise would be out of reach. [Parts IV, V, VI]

4) Describe the problems solved by using MCMC

 

The learning and teaching methods include:

i) 2x1 hour lectures per week, for 11 weeks, with typeset notes to complement the course, and Q+A opportunities for students.

ii) 1x1 hour practical lesson per week to learn the practical details of MCMC. If computer labs are inaccessible, then these can be replaced by appropriate online supervised sessions.

Indicated Lecture Hours (which may also include seminars, tutorials, workshops and other contact time) are approximate and may include in-class tests where one or more of these are an assessment on the module. In-class tests are scheduled/organised separately to taught content and will be published on to student personal timetables, where they apply to taken modules, as soon as they are finalised by central administration. This will usually be after the initial publication of the teaching timetable for the relevant semester.

Reading list

https://readinglists.surrey.ac.uk
Upon accessing the reading list, please search for the module using the module code: MATM061

Other information

This module has a capped number and may not be available to ERASMUS and other international exchange students. Please check with the International Engagement Office email: ieo.incoming@surrey.ac.uk

Programmes this module appears in

Please note that the information detailed within this record is accurate at the time of publishing and may be subject to change. This record contains information for the most up to date version of the programme / module for the 2020/1 academic year.