Establishing some order amongst exact approximations of MCMCs

Exact approximations of Markov chain Monte Carlo (MCMC) algorithms are a general class of sampling algorithms particularly well suited to Bayesian inference in complex models or computations in statistical physics where some of the quantities involved are intractable. One of the main ideas behind exact approximations consists of replacing intractable quantities required to run standard algorithms, such as the target probability density in a Metropolis-Hastings algorithm, with estimators. In this paper we discover a general framework which allows one to compare, or order, performance measures of two such approximate implementations. We focus in particular on the mean acceptance probability, the first order autocorrelation coefficient, the so-called asymptotic variance and the right spectral gap. The key notion we identify as relevant to our purpose is that of the convex order between random variables, in our case two approximations of the aforementioned quantities required to implement standard algorithms. An important point is that we show that using the variance of such approximations as a means to compare performance is not sufficient whereas the convex order turns out to be natural and powerful. Indeed the literature concerned with the convex order is vast and we detail some examples of applications by identifying extremal distributions within given classes of approximations, showing that averaging replicas improves performance in a monotonic fashion and that stratification may improve performance--it is in fact that case in almost all situations for the standard implementation of the Approximate Bayesian Computation (ABC) MCMC method. We also point to other applications and future developments.