Sampling with connections
Carlos C. Rodríguez · AIP conference proceedings · 2001
The Bayesian recipe is simple but powerful: “Compute the posterior by multiplying the likelihood by the prior.” Often Monte Carlo simulation is the only effective technique for dealing with realistic likelihoods in many dimensions. Algorithms based on Markov Chains (MCMC) are able to approximate samples from complicated distributions that are known only up to a normalization constant but most MCMC methods are asymptotic and may take a long time to converge. This paper shows how the time to convergence and the quality of the approximation can be dramatically improved by making the algorithms travel along paths in the space of distributions. More specifically. Let f and g be two probability densities (may be known only up to normalization constants) on the same probability space. We show a collection of new algorithms for approximating samples from f by sampling from g and uniforms only. These algorithms make use of a newly discovered exact rejection constant for two mixtures, ht=tf+(1−t)g between g and f. Specifically, ht+ε<(1+ε/t)ht.This bound allows exact rejection algorithms to be combined with approximate MCMC algorithms producing remarkable improvements in performance. The methods are general. There are no constraints on the forms of f or g or the number of dimensions.