Perfect sampling using bounding chains. (Q1879888)

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 given.