Perfect sampling using bounding chains. (English) Zbl 1052.60057

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.


60J22 Computational methods in Markov chains
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60J27 Continuous-time Markov processes on discrete state spaces
65C05 Monte Carlo methods
65C40 Numerical analysis or methods applied to Markov chains
82B80 Numerical methods in equilibrium statistical mechanics (MSC2010)
Full Text: DOI arXiv


[1] Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. Séminaire de Probabilités XVII . Lecture Notes in Math. 986 243–297. Springer, New York. · Zbl 0514.60067
[2] Bubley, R. and Dyer, M. (1997). Graph orientations with no sink and an approximation for a hard case of \(\sharp\)SAT. In Proc. 8th ACM–SIAM Sympos. Discrete Algorithms 248–257. ACM, New York. · Zbl 1321.68378
[3] Bubley, R. and Dyer, M. (1997). Path coupling: A technique for proving rapid mixing in Markov chains. In 38th Annual Sympos. Foundations Comp. Sci. 223–231.
[4] Cohn, H., Pemantle, R. and Propp, J. (2002). Generating a random sink-free orientation in quadratic time. Electron. J. Combin. 9 \(\sharp\)R10. · Zbl 0994.60004
[5] Diaconis, P. and Saloff-Coste, L. (1995). What do we know about the Metropolis algorithm? In Proc. 27th ACM Sympos. Theory Computing 112–129. ACM, New York. · Zbl 0922.60070
[6] Diaconis, P. and Shashahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159–179. · Zbl 0485.60006
[7] Doeblin, W. (1933). Exposé de la théorie des chains simples constantes de Markov à un nombre fini d’états. Rev. Math. de l’Union Interbalkanique 2 77–105. · Zbl 0021.42201
[8] Dyer, M., Frieze, A. and Jerrum, M. (1998). On counting independent sets in sparse graphs. Technical Report ECS-LFCS-98-391, Univ. Edinburgh. · Zbl 1041.68045
[9] Dyer, M. and Greenhill, C. (2000). On Markov chains for independent sets. J. Algorithms 35 17–49. · Zbl 0961.05063
[10] Fill, J. A., Machida, M., Murdoch, D. J. and Rosenthal, J. S. (2000). Extension of Fill’s perfect rejection sampling algorithm to general chains. Random Structures Algorithms 17 290–316. · Zbl 1122.60310
[11] Fishman, G. S. (1996). Monte Carlo : Concepts , Algorithms , and Applications . Springer, New York. · Zbl 0859.65001
[12] Fortuin, C. and Kasteleyn, P. (1972). On the random cluster model I: Introduction and relation to other models. Phys. 57 536–564.
[13] Häggström, O. and Nelander, K. (1998). Exact sampling from antimonotone systems. Statist. Neerlandica 52 360–380. · Zbl 0948.60069
[14] Häggström, O. and Nelander, K. (1999). On exact simulation from Markov random fields using coupling from the past. Scand. J. Statist. 26 395–411. · Zbl 0944.60059
[15] Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57 97–109. · Zbl 0219.65008
[16] Huber, M. L. (1998). Exact sampling and approximate counting techniques. In Proc. 30th Sympos. Theory Computing 31–40. · Zbl 1028.68218
[17] Huber, M. L. (1999). Exact sampling using Swendsen–Wang. In Proc. 10th Sympos. Discrete Algorithms 921–922. · Zbl 0927.60091
[18] Huber, M. L. (1999). Perfect sampling with bounding chains. Ph.D. dissertation, Cornell Univ.
[19] Huber, M. L. (2000). A faster method for sampling independent sets. In Proc. 11th ACM–SIAM Sympos. Discrete Algorithms 625–626. ACM, New York. · Zbl 0954.65005
[20] Jerrum, M., Valiant, L. and Vazirani, V. (1986). Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 169–188. · Zbl 0597.68056
[21] Kelly, F. (1991). Loss networks. Ann. Appl. Probab. 1 319–378. JSTOR: · Zbl 0743.60099
[22] Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E. (1953). Equation of state calculation by fast computing machines. J. Chem. Phys. 21 1087–1092.
[23] Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9 223–252. · Zbl 0859.60067
[24] Sinclair, A. (1993). Algorithms for Random Generation and Counting : A Markov Chain Approach . Birkhäuser, Boston. · Zbl 0780.68096
[25] van den Berg, J. and Steif, J. (1994). Percolation and the hard-core lattice gas model. Stochastic Process. Appl. 49 179–197. · Zbl 0787.60125
[26] Vigoda, E. (2000). Improved bounds for sampling colorings. J. Math. Phys. 41 1555–1569. · Zbl 0978.60083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.