title: Convergence and coupling for spin glasses and hard spheres.
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 nontrivial 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.
authors.affiliation: Laboratoire de Physique Statistique, Ecole Normale Supérieure, CNRS, Paris, France.
authors.forename: Cédric
authors.initials: C
authors.lastname: Chanal
authors.forename: Werner
authors.initials: W
authors.lastname: Krauth