| Contents |
| Exact approximation 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. Perhaps surprisingly, suitable and implementable approximations turn out to lead to exact algorithms in the sense that they are guaranteed to target the probability distribution of interest without introducing any approximation. In this presentation we present 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 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 all situations for the standard implementation of the Approximate Bayesian Computation (ABC) method. We also point to other applications and future developments. |
|