Bounding the convergence time of the Gibbs sampler in Bayesian image restoration

Abstract

This paper shows how coupling methodology can be used to give precise, a priori bounds on the convergence time of Markov chain Monte Carlo algorithms for which a partial order exists on the state space which is preserved by the Markov chain transitions. This methodology is applied to give a bound on the convergence time of the random scan Gibbs sampler used in the Bayesian restoration of an image of N pixels. For our algorithm, in which only one pixel is updated at each iteration, the bound is a constant times N 2 . The proportionality constant is given and is easily calculated. These bounds also give an indication of the running time of coupling from the past algorithms.