Perfect sampling using bounding chains
Author:
Open Access
- 1 May 2004
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 14 (2) , 734-753
Abstract
Bounding chains are a technique that offers three benefits to Markov chain practitioners: a theoretical bound on the mixing time of the chain under restricted conditions, experimental bounds on the mixing time of the chain that are provably accurate and construction of perfect sampling algorithms when used in conjunction with protocols such as coupling from the past. Perfect sampling algorithms generate variates exactly from the target distribution without the need to know the mixing time of a Markov chain at all. We present here the basic theory and use of bounding chains for several chains from the literature, analyzing the running time when possible. We present bounding chains for the transposition chain on permutations, the hard core gas model, proper colorings of a graph, the antiferromagnetic Potts model and sink free orientations of a graph.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Perfect sampling using bounding chainsThe Annals of Applied Probability, 2004
- On Markov Chains for Independent SetsJournal of Algorithms, 2000
- On Exact Simulation of Markov Random Fields Using Coupling from the PastScandinavian Journal of Statistics, 1999
- Exact sampling from anti‐monotone systemsStatistica Neerlandica, 1998
- Percolation and the hard-core lattice gas modelStochastic Processes and their Applications, 1994
- Loss NetworksThe Annals of Applied Probability, 1991
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- Random walks on finite groups and rapidly mixing markov chains1983
- On the random-cluster modelPhysica, 1972
- Monte Carlo sampling methods using Markov chains and their applicationsBiometrika, 1970