Renormalization Group Approach to Exact Sampling

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\times 64$.

Figure 1

Schematic representation of coupling from the past: The spin configuration $\mathit{\sigma }(t=0)$ is completely decorrelated from the initial configuration at $t=-\infty$. The configuration $\mathit{\sigma }(0)$ follows from the $2^N$ configurations at $t=t_0$ if the chain couples between $t=t_0$ and $t=0$.

Figure 2

Weights vs time (in sweeps) of the heat bath algorithm for an instance of the $64\times 64$ Ising spin glass at $\beta =0.5$ (configurations that couple add weights). At $t-t_0=631$, the $2^{18}$ randomly chosen initial configurations have coupled toward a single configuration. Up to time $t\simeq t_0+330$, many configurations with very small weights subsist.

Figure 3

A spin configuration $\mathit{\sigma }=\{{\sigma }_1,\dots ,{\sigma }_N\}$, and the set of configurations $S_k$ and $S_l$ on patches $k$ and $l$. The overlap region $k\cap l$ consists here of nine sites. The configuration on the center of a patch, after one sweep, depends on the patch alone.

Figure 4

Coupling of the $2^{64\times 32}$ configurations of the two-dimensional Ising spin glass on a $64\times 64$ lattice at $\beta =0.5$ followed through patches of increasing size (compare with Fig. 2).