Exact sampling with coupled Markov chains and applications to statistical mechanics

By James Gary Propp, David Bruce Wilson. 1996

Subfields: Probabilistic & Bayesian Methods, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

In Information Theory

Citations in the corpus

A* Sampling (2014, methodology): “Some are specialized to speciﬁc distributions [5], but exact generic methods are based either on (adaptive) rejection sampling [6, 7, 8] or Markov Chain Monte Carlo (MCMC) methods where convergence to the stationary distribution can be guaranteed [9, 10, 11].”
Explaining the Perfect Sampler (2001, background): “Propp and Wilson (1996) argued that T = ¡ 1; ¡ 2; ¡ 4; ¡ 8; : : : is near optimal.”
The OS* Algorithm: a Joint Approach to Exact Optimization and Sampling (2012, methodology): “Note that, in certain cases, exact sampling for Ising models can be done in polynomial time [Ullrich, 2010] by using an elegant MCMC approach called coupling from the past [Propp and Wilson, 1996].”
Stochastic monotonicity and realizable monotonicity (2000, methodology): “For further discussion of these perfect sampling algorithms, see [2] and [7].”
Exact and efficient Bayesian inference for multiple changepoint problems (2006, methodology): “Although we use the phrase “perfect simulation”, we do not use coupling-from-the past (Propp and Wilson, 1996), or related ideas, which have become synonymous with this phrase.”
Information Theory, Inference, and Learning Algorithms (2004, methodology): “The Ising model is a simple model which has been around for a long time, but the task of generating samples from the distribution P (x) = P ∗(x)/Z is still an active research area; the first ‘exact’ samples from this distribution were created in the pioneering work of Propp and Wilson (1996), as we’”
General state space Markov chains and MCMC algorithms (2004, unknown): “Then t is sub-multiplicative, i.e. t(m+ n) ≤ t(m) t(n) for m,n ∈ N. (f) If µ(·) and ν(·) have densities g and h, respectively, with respect to some σ-finite measure ρ(·), and M = max(g, h) and m = min(g, h), then ‖µ(·)− ν(·)‖ = 1 2 ∫ X (M −m) dρ = 1− ∫ X mdρ.”
Perfect simulation of Hawkes processes (2005, methodology): “until Algorithm 3 terminates, there is no advantage in using a doubling scheme for n, as in the Propp–Wilson algorithm [24].”
Nested sampling for general Bayesian computation (2006, background): “For some problems, it may be possible to nd provably exact samples ( Propp and Wilson (1996) ) within a likelihood contour, and thus remove any doubt concerning imperfect sampling.”
Bayesian Parameter Estimation for Latent Markov Random Fields and Social Networks (2012, background): “However, aside from a few special cases [one of which is the Ising model, which can be sampled exactly using “coupling from the past” (Propp and Wilson 1996)], this is not generally possible for MRFs. Caimo and Friel (2011) chose to approximate the exact simulation by sampling u from f (·|θ∗) using…”
Handbook of Markov Chain Monte Carlo: Hardcover: 619 pages Publisher: Chapman and Hall/CRC Press (first edition, May 2011) Language: English ISBN-10: 1420079417 (2012, background): “The ﬁrst of these is perfect simulation, which provides an MCMC framework for producing samples exactly from the target distribution, circumventing convergence issues entirely (Propp and Wilson, 1996).”
Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes (2000, methodology): “As pointed out in [11], vertical CFTP (coupling of realizations started at a fixed time for all possible initial states) is not available if uniform ergodicity fails, so the standard CFTP recipe of [37] needs modification.”
Perfect simulation and moment properties for the Matérn type III process (2010, background): “Section 3 then presents the basic simulation algorithm, which is perfect in the sense of Propp and Wilson (1996) in that it has a random running time but returns samples drawn exactly from the desired distribution.”