Perfect sampling using bounding chains.
type: Item
instance of: scholarly article
title: Perfect sampling using bounding chains.
zbMATH Open document ID: 1052.60057
DOI: 10.1214/105051604000000080
published in: The Annals of Applied Probability
publication date: 2004-09-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/0405284
review text: The basic framework of bounding chains and their application to several interesting problems drawn from statistical mechanics, graph theory and the approximation of NP-complete problems is considered. Successful application of Monte Carlo Markov chain techniques requires to find the mixing time of these chains which is, in general, extremely difficult. Bounding chains give a theoretical and experimental bound on the mixing time. Moreover, the perfect sampling algorithms generate variates exactly from the target distribution without the need to know the mixing time at all. A technique is applied to a finite Markov chain, denoted by \(M\), with a state space \(\Omega \subseteq C^V\) where \(V\) is the set of dimensions and \(C\) is the set of colors. The colorings \(c(v) \in C\) for all \(v \in V\), which satisfy some preassigned restrictions, are considered. The goal is to generate random variates from the stationary distribution \(\pi\) on the set of colorings. The bounding chain \(M'\) with state space \((2^C)^V\), where \(2^C\) is the set of subsets of \(C\), is defined by the requirement that there exists a coupling \((X_t,Y_t)\), \(t=0,1,\dots\), between \(M\) and \(M'\) such that \[ X_t(v) \in Y_t(v) \quad \forall v \in V \Rightarrow X_{t+1}(v) \in Y_{t+1}(v) \quad \forall v \in V, \quad t=0,1,\dots. \] Here \(X_t\) is a stochastic process evolving according to \(M\), so that each \(v \in V\) is given a single \(c \in C\) in \(X_t\), and \(Y_t\) is a stochastic process evolving according to \(M'\), so that each \(v \in V\) is given a subset from \(C\) in \(Y_t\). If \(Y_0\) bounds every state in \(\Omega\), then when \(Y_t\) bounds just one state \(x\) it can be accepted as the variate from the stationary distribution \(\pi\). The bounding chains are presented for 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. Estimations of running time are give…
reviewed by: Alex V. Kolnogorov
Mathematics Subject Classification ID: 60J22
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60J27
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 65C40
Mathematics Subject Classification ID: 82B80
zbMATH DE Number: 2100752
zbMATH Keywords: Monte Carlo Markov chains
zbMATH Keywords: perfect simulation
zbMATH Keywords: coupling from the past
zbMATH Keywords: mixing times
zbMATH Keywords: proper colorings
zbMATH Keywords: Potts model
zbMATH Keywords: sink free orientation
author: Mark Huber
MaRDI profile type: Publication
OpenAlex ID: W2028521956
arXiv ID: math/0405284
cites work: Q3660628
cites work: Q5501802
cites work: Generating a random sink-free orientation in quadratic time
cites work: Q4234057
cites work: Generating a random permutation with random transpositions
cites work: Q5774896
cites work: On Counting Independent Sets in Sparse Graphs
cites work: On Markov Chains for Independent Sets
cites work: Q4521550
cites work: Q4869639
cites work: Exact sampling from anti‐monotone systems
cites work: On Exact Simulation of Markov Random Fields Using Coupling from the Past
cites work: Monte Carlo sampling methods using Markov chains and their applications
cites work: Q4542517
cites work: Q4252411
cites work: Q4952677
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Loss networks
cites work: Exact sampling with coupled Markov chains and applications to statistical mechanics
cites work: Q3135094
cites work: Percolation and the hard-core lattice gas model
cites work: Improved bounds for sampling colorings
description: scientific article