An upper bound on the convergence time of the Gibbs sampler in Ising models

Abstract

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.

Keywords:

• Markov chain Monte Carlo
• Gibbs sampler
• Convergence time
• Ising model
• Coupling methodology
• Coupling from the past

Acknowledgements

We wish to express our gratitude to the associate editor and the anonymous referee who made valuable comments and important suggestions for the revisions of this article. We also thank Akimichi Takemura and Shiro Ikeda for their helpful comments on this article.

Additional information

Notes on contributors

Yuichi Shiraishi

Email: [email protected]