×

Analyzing Glauber dynamics by comparison of Markov chains. (English) Zbl 0974.60052

Summary: A popular technique for studying random properties of a combinatorial set is to design a Markov chain Monte Carlo algorithm. For many problems there are natural Markov chains connecting the set of allowable configurations which are based on local moves, or “Glauber dynamics”. Typically these single-site update algorithms are difficult to analyze, so often the Markov chain is modified to update several sites simultaneously. Recently there has been progress in analyzing these more complicated algorithms for several important combinatorial problems. In this work we use the comparison technique of Diaconis and Saloff-Coste to show that several of the natural single-point update algorithms are efficient. The strategy is to relate the mixing rate of these algorithms to the corresponding nonlocal algorithms which have already been analyzed. This allows us to give polynomial time bounds for single-point update algorithms for problems such as generating planar tilings and random triangulations of convex polygons. We also survey several other comparison techniques, along with specific applications, which have been used in the context of estimating mixing rates of Markov chains.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
68R05 Combinatorics in computer science
82C31 Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Welsh D. J. A., London Math Society Lecture Notes 241 pp 287– (1997)
[2] Sinclair A. J., Information and Computation 82 pp 93– (1989) · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9
[3] Jerrum M. R., SIAM J. Comput. 18 pp 1149– (1989) · Zbl 0723.05107 · doi:10.1137/0218077
[4] Kenyon C., Stat. Phys. 83 pp 637– (1996) · Zbl 1081.82523 · doi:10.1007/BF02183743
[5] Jerrum M. R., SIAM J. Comput. 22 pp 1087– (1993) · Zbl 0782.05076 · doi:10.1137/0222066
[6] Jerrum M., Random Structures and Algorithms 7 pp 157– (1995) · Zbl 0833.60070 · doi:10.1002/rsa.3240070205
[7] Diaconis P., Ann. Appl. Probability 3 pp 696– (1993) · Zbl 0799.60058 · doi:10.1214/aoap/1177005359
[8] Diaconis P., Ann. Appl. Probability 1 pp 36– (1991) · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[9] Holley R., Contemp. Math. 41 pp 215– (1985) · doi:10.1090/conm/041/814713
[10] Diaconis P., Ann. Appl. Probab. 6 pp 695– (1996) · Zbl 0867.60043 · doi:10.1214/aoap/1034968224
[11] van den Berg J., J. Math. Phys. 41 pp 1585– (2000) · Zbl 1034.82012 · doi:10.1063/1.533198
[12] Thurston W., Am. Math. Monthly 97 pp 757– (1990) · Zbl 0714.52007 · doi:10.2307/2324578
[13] Griffeath D., Stochastic Proc. Appl 11 pp 151– (1981) · Zbl 0463.60085 · doi:10.1016/0304-4149(81)90002-8
[14] Saloff-Coste L., Lecture Notes in Math. 1665 pp 301– (1997) · doi:10.1007/BFb0092621
[15] Miclo S., Lect. Notes Math. 1655 pp 136– (1995) · doi:10.1007/BFb0119300
[16] Diaconis P., Z. Wahrscheinlichkeitstheor. Verwandte Geb. 57 pp 159– (1981) · Zbl 0485.60006 · doi:10.1007/BF00535487
[17] Diaconis P., Ann. Prob. 21 pp 2131– (1993) · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[18] Luby M., Random Structures and Algorithms 15 pp 229– (1999) · Zbl 0941.65010 · doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<229::AID-RSA3>3.0.CO;2-X
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.