Couplings and Monte Carlo
Course history
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.
2021 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.
2023-2024 update
In Spring 2023 and in Spring 2024 the course was used for the material of Optimization-Conscious Econometrics Summer Schools (June 5-8, 2023, and June 3-6, 2024 University of Chicago): you can find slides here: Part 1, Part 2, Part 3, Part 4.
Course description
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
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.
Introduction on Monte Carlo methods, rejection sampling, importance sampling, some MCMC methods
Couplings of random variables, the celebrated “coupling inequality”. Some examples of using couplings to derive some non-trivial results in probability (Thórisson 1995). Some connections to optimal transport (as in Monge/Kantorovich/Wasserstein distances, see Peyré & Cuturi).
Coupling of Markov chains, geometric ergodicity of MCMC algorithms (Jerrum 1998, Roberts & Rosenthal 2004, Jones & Hobert 2004)
Monte Carlo methods employing coupled Markov chains, including Coupling From The Past (Propp & Wilson 1996), debiasing techniques (Glynn & Rhee 2014, Jacob, O’Leary & Atchadé 2017), diagnostics of convergence (Johnson 1996, Biswas et al 2019), etc.