Coupling and Parallelization in Statistical Inference

Abstract

This thesis considers the design of Markov chain Monte Carlo (MCMC) estimators using couplings. Couplings play an important part in Markov chain theory, and in recent decades they have also taken on a central role in methodology. We begin this thesis by showing that a certain coupling-based construction yields unbiased estimators based on MCMC algorithms. This yields a parallelizable framework in which consistency occurs in the number of replications rather than the number of time steps. The efficiency of these estimators depends on the quality of the underlying couplings, so in the second part of this thesis we turn our attention to the question of coupling design. We focus on the popular and versatile Metropolis--Hastings (MH) algorithm and introduce a range of tools for coupling its proposal and acceptance steps. We use a mix of theory and numerical work to identify efficient couplings for use in practice. Going a step further, we introduce the first maximal couplings of the MH transition kernel. In some cases, these produce a significant improvement in meeting times compared to known methods. We conclude with a pair of characterization theorems, which give an equivalence between couplings of the MH transition kernel and pairs of proposal and acceptance couplings. These results clarify what is possible for Markovian couplings of the MH algorithm and suggest a path toward optimally efficient unbiased MCMC estimators.