Chanal Krauth 2010
From Werner KRAUTH
C. Chanal, W. Krauth Physical Review E 81 016705 (2010)
Abstract: We discuss convergence and coupling of Markov chains, and present general relations between the transfer matrices describing these two processes. We then analyze a recently developed local-patch algorithm, which computes rigorous upper bound for the coupling time of a Markov chain for non-trivial statistical-mechanics models. Using the "coupling from the past" protocol, this allows one to exactly sample the underlying equilibrium distribution. For spin glasses in two and three spatial dimensions, the local-patch algorithm works at lower temperatures than previous exact-sampling methods. We discuss variants of the algorithm which might allow one to reach, in three dimensions, the spin-glass transition temperature. The algorithm can be adapted to hard-sphere models. For two-dimensional hard disks, the algorithm allows us to draw exact samples at higher densities than previously possible.
Comment: Long version of the Chanal Krauth (2008) paper, containing an extension of the patch algorithm to hard spheres.
