Fast convergence of the Glauber dynamics for sampling independent sets. (English) Zbl 0941.65010
The authors consider the problem of sampling independent sets of a graph with maximum degree \(\delta\). The weight of each independent set is expressed in terms of a fixed positive parameter \(\lambda\leq 2/(\delta- 2)\), where the weight of an independent set \(\sigma\) is \(\lambda^{|\sigma|}\). The Glauber dynamics is a simple Markov chain Monte Carlo method for sampling from this distribution. The authors show fast convergence (in \(O(n\log n)\) time) of this dynamics. The paper gives the more interesting proof for triangle-free graphs. The proof for arbitrary graphs is given in a companion paper [E. Vigoda, Technical Report IR-99-003, International Computer Institute, Berkely, CA (1998)]. The authors also prove complementary hardness of approximation results, which show that it is hard to sample from this distribution when \(\lambda> c/\delta\) for a constant \(c\leq 0\).
Reviewer: S.Mika (Plzeň)
MSC:
| 65C40 | Numerical analysis or methods applied to Markov chains |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60J22 | Computational methods in Markov chains |
| 65C05 | Monte Carlo methods |
Keywords:
sampling independent sets; Glauber dynamics; Markov chain Monte Carlo method; convergence; triangle-free graphsReferences:
| [1] | and Rapid convergence to equilibrium of stochastic Ising models in the Dobrushin-Shlosman regime, Percolation Theory and Ergodic Theory of Infinite Particle Systems, IMA Volumes in Mathematics and its Applications, Springer, New York, 1987, Vol. 8, pp. 1-11. · doi:10.1007/978-1-4613-8734-3_1 |
| [2] | Baxter, J Statist Phys 22 pp 465– (1980) · doi:10.1007/BF01012867 |
| [3] | van den Berg, Stochastic Process Appl 49 pp 179– (1994) · Zbl 0787.60125 · doi:10.1016/0304-4149(94)90132-5 |
| [4] | and On some tighter inapproximability results, Technical Report TR98-029, ECCC, 1998. |
| [5] | and Path coupling, Dobrushin uniqueness, and approximate counting, Proc 38th Annual Symp on Foundations of Computer Science, IEEE, New York, 1997. |
| [6] | Dobrushin, Funct Anal Appl 2 pp 302– (1968) · Zbl 0192.61702 · doi:10.1007/BF01075682 |
| [7] | Dobrushin, Comm Math Phys 102 pp 89– (1985) · doi:10.1007/BF01208821 |
| [8] | and Constructive criterion for the uniqueness of Gibbs field, Statistical Physics and Dynamical Systems, Progress in Physics, Birkhäuser, Boston, 1985, Vol. 10, pp. 347-370. · doi:10.1007/978-1-4899-6653-7_20 |
| [9] | and On Markov chains for independent sets, preprint, 1997. |
| [10] | Gibbs Measures and Phase Transitions, Studies in Mathematics, de Gruyter, Berlin, 1988, vol. 9. |
| [11] | and Exact sampling from anti-montone systems, preprint, 1997. |
| [12] | Clique is hard to approximate within n1??, Proc 37th Annual Symp on Foundations of Computer Science, IEEE, New York, 1996. |
| [13] | Jerrum, Theoret Comput Sci 43 pp 169– (1986) · Zbl 0597.68056 · doi:10.1016/0304-3975(86)90174-X |
| [14] | and Monte-Carlo algorithms for enumeration and reliability problems, Proc 24th Annual Symp on Foundations of Computer Science, IEEE, New York, 1983, pp. 56-64. |
| [15] | Kelly, Ann Appl Probab 1 pp 319– (1991) · Zbl 0743.60099 · doi:10.1214/aoap/1177005872 |
| [16] | Kirillov, J Statist Phys 56 pp 931– (1989) · doi:10.1007/BF01016786 |
| [17] | Stochastic networks: Complexity, dependence, and routing, Ph.D. thesis, Univ. Cambridge, 1990. |
| [18] | and Approximately counting up to four (extended abstract), Proc 29th Annual ACM Symp Theory of Computing, El Paso, TX, 1997, pp. 682-687. · Zbl 0963.68150 |
| [19] | Martinelli, Comm Math Phys 161 pp 447– (1994) · Zbl 0793.60110 · doi:10.1007/BF02101929 |
| [20] | Martinelli, Comm Math Phys 161 pp 487– (1994) · Zbl 0793.60111 · doi:10.1007/BF02101930 |
| [21] | and Optimization, approximation, and complexity classes (extended abstract), Proc 20th Annual ACM Symp on Theory of Computing, Association for Computing Machinery, New York, 1988. |
| [22] | Propp, Random Struct Alg 9 pp 223– (1996) · Zbl 0859.60067 · doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O |
| [23] | and Coupling from the past: a user’s guide, preprint, 1998. |
| [24] | Radulescu, J Statist Phys pp 281– (1987) · Zbl 0960.82500 · doi:10.1007/BF01009964 |
| [25] | and Analyzing Glauber dynamics by comparison of Markov chains, 3rd Latin American Symp on Theoretical Informatics, Campinas, Brazil, April 1988 (UNICAMP). |
| [26] | Algorithms for Random Generation and Counting: A Markov Chain Approach, Birkhäuser, Boston, 1993. · Zbl 0780.68096 · doi:10.1007/978-1-4612-0323-0 |
| [27] | The complexity of counting, undergraduate thesis, Harvard University, 1995. |
| [28] | Fast convergence of the Glauber dynamics for sampling independent sets: Part II, Technical Report TR-99-003, International Computer Science Institute, Berkeley, CA, January , 1998. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
