Couplings and Monte Carlo

This page acts as a syllabus for a course on couplings and their use in Monte Carlo, both in theory and in methods.

Update: In Spring 2023 the course was used for the material of Optimization-Conscious Econometrics Summer School (June 5-8, 2023, University of Chicago): you can find slides here on MCMC and couplings. 

Update: in Spring 2021 the course was turned into STAT 248 at Harvard University. The lecture notes are available in this folder. You will also find exercises, R scripts, and the support for the video lectures. The videos are available on Youtube.  You can skip the first 11:30 minutes of the first video to get right into the material.

The description below corresponds to an earlier version of the course and is kept here only for reference. I suggest learning from the most recent version of the course, of course.

-- 

The course was given in Université Paris-Dauphine as part of the M.Sc. in Applied Mathematics in February 2020 over 12 hours (thanks Robin Ryder and Christian P. Robert), at the University of Bristol in March 2020 over 4 hours (thanks Anthony Lee) and at the University of Torino, as part of the M.Sc. in Stochastics and Data Science, remotely over 16 hours in May 2020 (thanks Matteo Ruggiero).  I am grateful to these people and these institutions for supporting this course, and to the students of these universities for the helpful feedback.

The course is about the method of coupling in probability and its use in Monte Carlo methods, which refer to algorithms generating samples from probability distributions of interest. The course includes an introduction to Monte Carlo methods (rejection sampling, importance sampling, MCMC), followed by an introduction to the coupling method. This includes the celebrated "coupling inequality" and various coupling interpretations of notions of distances between probability distributions, such as total variation and Wasserstein. The course then focuses on Markov chain methods and describes how couplings of Markov chains can be employed to quantify their convergence. The last part of the course covers various Monte Carlo methods that rely on explicit coupling constructions in their implementations, such as Coupling From The Past (Propp & Wilson 1996), debiasing techniques (Glynn & Rhee 2014) and some convergence diagnostics for MCMC (Johnson 1996).

Outline of the course

The course is made of two main components: a more conceptual/theoretical component, and a more algorithmic/methodological component. The lectures might alternate with topics from both components, i.e. we won't do all of the theory, and then all of the methods.

Videos

The course can be followed with videos.

The videos were made for the students of the M.Sc. in Stochastics and Data Science of the University of Torino, at the generous invitation of Matteo Ruggiero. These were made rather quickly, in the strange circumstances of the lockdown, so please be forgiving.

To contact me, send an email to: pjacob at g dot harvard dot edu.

Lecture notes

The lecture notes are available as pdf files in that folder. 

Chapter 1: Monte Carlo

Chapter 2: couplings 

Chapter 3: convergence of Markov chains 

Chapter 4: methods using coupled Markov chains

All of these lecture notes are still work in progress, please be forgiving. Any feedback would be much appreciated.

Code

[repository available here]

... eventually the repository will contain scripts that produce figures of the lecture notes, and perhaps the source code for the lecture notes themselves.  

Exercises

A good exercise would be to try to understand and reproduce each figure of the lecture notes.

For possible projects (if you need one): prepare a 15 minute presentation including your own simulations, relating to either one of the papers:

For bibliographic references, please see the lecture notes.