The Coupled Rejection Sampler

We propose a novel coupled rejection-sampling method for sampling from couplings of arbitrary distributions. The method relies on accepting or rejecting coupled samples coming from dominating marginals. Contrary to existing acceptance-rejection methods, the variance of the execution time of the proposed method is limited and stays finite as the two target marginals approach each other in the sense of the total variation norm. In the important special case of coupling multivariate Gaussians with different means and covariances, we derive positive lower bounds for the resulting coupling probability of our algorithm, and we then show how the coupling method can be optimised using convex optimisation. Finally, we show how we can modify the coupled-rejection method to propose from coupled ensemble of proposals, so as to asymptotically recover a maximal coupling. We then apply the method to derive a novel parallel coupled particle filter resampling algorithm, and show how it can be used to speed up unbiased MCMC methods based on couplings.