An Upper Bound on the Convergence Time of the Gibbs Sampler in Ising Models

par/by Yuichi Shiraishi
Department of Statistical Science
Graduate University of Advanced Studies
Tokyo, Japan

We discuss the convergence time of Gibbs sampler in Ising models. We obtain an improved explicit O(N log N) upper bound on the convergence time of the Gibbs sampler in Ising models with N sites. Our results are tighter and hold for the wider range of parameter values compared to the previous results. It is generally very difficult to decide when to stop the Gibbs sampler and our upper bounds are good practical guides for it. Moreover, they also give important information about the running time of coupling from the past algorithms.