Over-relaxation methods and Metropolis-Hastings coupled Markov chains for Monte Carlo simulation

This paper is concerned with improving the performance of Markov chain algorithms for Monte Carlo simulation. We propose a new algorithm for simulating from multivariate Gaussian densities. This algorithm combines ideas from Metropolis-coupled Markov chain Monte Carlo methods and from an existing algorithm based only on over-relaxation. The speed of convergence of the proposed and existing algorithms can be measured by the spectral radius of certain matrices. We present examples in which the proposed algorithm converges faster than the existing algorithm and the Gibbs sampler. We also derive an expression for the asymptotic variance of any linear combination of the variables simulated by the proposed algorithm. From this expression it follows that the proposed algorithm offers no asymptotic variance reduction compared with the existing algorithm. We extend the proposed algorithm to the non-Gaussian case and discuss its performance by means of examples from Bayesian image analysis. We find that better performance is obtained from a special case of the proposed algorithm, which is a modified version of the algorithm of Green and Han (1992), than from a Metropolis algorithm. Keywords: Gibbs sampler; Metropolis-coupled Markov chain Monte Carlo; Metropolis-Hastings algorithms; Rate of convergence using spectral radius; Stochastic relaxation. 1 Introductio