Abstract: Couplings play a central role in the analysis of Markov chain Monte Carlo algorithms and appear increasingly often in the algorithms themselves, e.g. in convergence diagnostics, parallelization, and variance reduction techniques. Existing couplings of the Metropolis-Hastings algorithm handle the proposal and acceptance steps separately and fall short of the upper bound on one-step meeting probabilities given by the coupling inequality. This paper introduces maximal couplings which achieve this bound while retaining the practical advantages of current methods. We consider the properties of these couplings and examine their behavior on a selection of numerical examples.
Introduction
In Markov chain Monte Carlo (MCMC), "coupling" involves running two distinct Markov chains simultaneously such that they eventually "meet" (reach the same state) and remain together thereafter. This technique is foundational for parallelization, variance reduction, and the creation of unbiased estimators for complex target distributions.
The theoretical gold standard for any coupling is to be maximal, meaning it achieves the highest possible probability of the two chains meeting in a single step, as constrained by the "coupling inequality." Historically, the standard approach for the Metropolis-Hastings (MH) algorithm—the "Status Quo" ($P_{SQ}$)—couples the proposal and acceptance steps independently. While computationally simple, this approach consistently falls short of the theoretical maximum meeting probability. This research introduces implementable maximal couplings that require only the standard information available to an MH algorithm: the ability to evaluate target and proposal densities.
Conceptual Framework: The Coupling Inequality
The core challenge lies in maximizing the overlap between the transition kernels of two chains starting at different points. The coupling inequality states that for any two probability measures, the probability of a meeting is bounded by the total variation distance between them.
As shown in the figure above, the transition densities $f(x, z)$ and $f(y, z)$ can be decomposed into overlapping (C) and non-overlapping (A, B) regions. A maximal coupling ensures that if a meeting does not occur within the overlapping region C, the chains are mapped to the remaining probability mass in a way that preserves the marginal distributions while maximizing the probability of future meetings.
Proposed Methods
The authors introduce three "implementable" maximal couplings that function as "black-box" solutions for existing MH setups:
- $P_{MI}$ (Full-kernel with Independent Residuals): This treats the entire MH transition as a single distribution. It uses a rejection sampling approach to force a meeting. If the first chain's move does not result in a meeting, the second chain's move is sampled independently from a "residual" distribution.
- $P_{MR}$ (Full-kernel with Reflection Residuals): Similar to $P_{MI}$, but utilizes a "reflection" technique for residuals. This encourages chains to move toward each other even when they fail to meet, which is critical for maintaining performance in high-dimensional spaces.
- $P_C$ (Coupled Transitions from Coupled Proposals): This method uses a clever Bernoulli coupling in the acceptance step to ensure the overall transition is maximal. It is computationally more efficient than the full-kernel versions as it avoids the overhead of rejection sampling loops.
Key Insights and Results
The Efficiency of Maximality
The authors demonstrate that coupling the components of an algorithm (proposal then acceptance) is mathematically guaranteed to be less efficient than coupling the whole transition at once. In a 1D Biased Random Walk example, maximal couplings reduced the average meeting time from approximately 75 iterations to 60 iterations.
Scaling and Dimensionality
A significant finding is that maximality alone is insufficient in high dimensions. In a 100-dimensional multivariate normal target study, the independent residual version ($P_{MI}$) saw meeting times explode exponentially. However, the reflection-based version ($P_{MR}$) maintained strong "contraction," keeping the chains close enough to eventually meet. This highlights that how chains fail to meet is as important as the probability that they do meet.
Practical Implementation
The $P_C$ algorithm provides the benefits of maximality without the computational "while-loop" overhead of rejection sampling. This makes it the most viable candidate for integration into existing MCMC software and high-performance computing environments.
Conclusion
By closing the gap between the "Status Quo" and the theoretical coupling inequality, these maximal couplings significantly improve the efficiency of unbiased MCMC estimators. While the "contraction" problem in high dimensions remains sensitive to the geometry of the proposal distribution, the introduction of $P_{MR}$ and $P_C$ provides a robust framework for future developments in non-convex landscapes and non-Markovian couplings.
Summary updated