Random Structures and Algorithms · 1996 · 1.1K citations · 0 references
Natural SciencesComputer ScienceMathematicsProbability TheoryStochastic ModelingStochastic ProcessesErgodic TheoryMarkov ChainsMarkov ProcessesMonte Carlo MethodsSampling TheoryStatistical MechanicsCoupling From The PastExact SamplingGibbs DistributionGibbs SamplingSampling In State SpaceState-space Structure
Sampling from a finite set according to a target distribution is common, but determining the required number of Markov chain steps is often difficult, especially when the state space lacks a preserved partial order. The authors propose a simple variant that autonomously decides when to stop and produces samples exactly from the desired distribution. Their method runs coupled Markov chains backward from a distant past to the present, determining the necessary depth during execution, and exploits preserved partial orders to improve efficiency. This approach enables exact sampling from Gibbs distributions of Ising, random‑cluster, ice, and dimer models, as well as uniform sampling from finite distributive lattices. © 1996 John Wiley & Sons, Inc.
For many applications it is useful to sample from a finite set of objects in accordance with some particular distribution. One approach is to run an ergodic (i.e., irreducible aperiodic) Markov chain whose stationary distribution is the desired distribution on this set; after the Markov chain has run for M steps, with M sufficiently large, the distribution governing the state of the chain approximates the desired distribution. Unfortunately, it can be difficult to determine how large M needs to be. We describe a simple variant of this method that determines on its own when to stop and that outputs samples in exact accordance with the desired distribution. The method uses couplings which have also played a role in other sampling schemes; however, rather than running the coupled chains from the present into the future, one runs from a distant point in the past up until the present, where the distance into the past that one needs to go is determined during the running of the algorithm itself. If the state space has a partial order that is preserved under the moves of the Markov chain, then the coupling is often particularly efficient. Using our approach, one can sample from the Gibbs distributions associated with various statistical mechanics models (including Ising, random-cluster, ice, and dimer) or choose uniformly at random from the elements of a finite distributive lattice. © 1996 John Wiley & Sons, Inc.