Renormalization group approach to exact sampling

Abstract

In this Letter, we use a general renormalization-group algorithm to implement Propp and Wilson's "coupling from the past" approach to complex physical systems. Our algorithm follows the evolution of the entire configuration space under the Markov chain Monte Carlo dynamics from parts of the configurations (patches) on increasing length scales, and it allows us to generate "exact samples" of the Boltzmann distribution, which are rigorously proven to be uncorrelated with the initial condition. We validate our approach in the two-dimensional Ising spin glass on lattices of size 64 x 64.

4 pages, 4 figures (published version)

References in corpus (3)

• How to Couple from the Past Using a Read-Once Source of Randomness
• Critical thermodynamics of the two-dimensional +/-J Ising spin glass
• Exact sampling from non-attractive distributions using summary states

Cited by in corpus (11)

• Eigenvalue method to compute the largest relaxation time of disordered systems
• Domain-wall excitations in the two-dimensional Ising spin glass
• Exact Algorithm for Sampling the 2D Ising Spin Glass
• Numerically exact correlations and sampling in the two-dimensional Ising spin glass
• Damage spreading and coupling in Markov chains
• The Fortuin-Kasteleyn and Damage Spreading transitions in Random bond Ising lattices
• Non-equilibrium dynamics of finite-dimensional disordered systems : RG flow towards an "infinite disorder" fixed point at large times
• Quantum algorithm for exact Monte Carlo sampling
• Convergence and coupling for spin glasses and hard spheres
• Damage spreading and coupling in spin glasses and hard spheres
• Four lectures on computational statistical physics