Coupling in stochastic process

April 17, 2020 — November 12, 2019

metrics
probability
statistics
Figure 1

A probabilistic technique. Placeholder.

Djalil Chafaï, Coupling, divergences, and Markov kernels manufactures some concentration results.

Pierre E. Jacob, Couplings and Monte Carlo

The course was given at 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).

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.