×

zbMATH — the first resource for mathematics

A general lower bound for mixing of single-site dynamics on graphs. (English) Zbl 1125.60075
Summary: We prove that any Markov chain that performs local, reversible updates on randomly chosen vertices of a bounded-degree graph necessarily has mixing time at least \(\Omega(n\log n)\), where \(n\) is the number of vertices. Our bound applies to the so-called Glauber dynamics that has been used extensively in algorithms for the Ising model, independent sets, graph colorings and other structures in computer science and statistical physics, and demonstrates that many of these algorithms are optimal up to constant factors within their class. Previously, no superlinear lower bound was known for this class of algorithms. Though widely conjectured, such a bound had been proved previously only in very restricted circumstances, such as for the empty graph and the path. We also show that the assumption of bounded degree is necessary by giving a family of dynamics on graphs of unbounded degree with mixing time \(O(n)\).

MSC:
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
68W20 Randomized algorithms
68W25 Approximation algorithms
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Achlioptas, D., Molloy, M., Moore, C. and van Bussel, F. (2004). Sampling grid colorings with fewer colors. LATIN 2004: Theoretical Informatics . Lecture Notes in Comput. Sci. 2976 80–89. Springer, Berlin. · Zbl 1196.05027
[2] Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. SĂ©minaire de Probabilites XVII . Lecture Notes in Math. 986 243–297. Springer, Berlin. · Zbl 0514.60067 · numdam:SPS_1983__17__243_0 · eudml:113445
[3] Aldous, D. and Fill, J. (2002). Reversible Markov chains and random walks on graphs. Unpublished manuscript. Available at www.stat.berkeley.edu/users/aldous/RWG/book.html. (References are to the September 10, 2002 version of Chapter 3.)
[4] Besag, J. (1974). Spatial interaction and the statistical analysis of lattice systems. J. Roy. Statist. Soc. Ser. B 36 192–236. JSTOR: · Zbl 0327.60067 · links.jstor.org
[5] Borgs, C., Chayes, J. T., Frieze, A. M., Kim, J. H., Tetali, P., Vigoda, E. and Vu, V. H. (1999). Torpid mixing of some Monte Carlo Markov chain algorithms from statistical physics. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science 218–229. IEEE Computer Soc., Los Alamitos, CA.
[6] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159–179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[7] Diaconis, P. and Saloff-Coste, L. (1996). Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695–750. · Zbl 0867.60043 · doi:10.1214/aoap/1034968224
[8] Dyer, M., Goldberg, L. A., Greenhill, C., Jerrum, M. and Mitzenmacher, M. (2001). An extension of path coupling and its application to the Glauber dynamics for graph colourings. SIAM J. Comput. 30 1962–1975. · Zbl 0999.05035 · doi:10.1137/S0097539700372708
[9] Dyer, M., Goldberg, L. A. and Jerrum, M. (2006). Systematic scan for sampling colourings. Ann. Appl. Probab. 16 185–230. · Zbl 1095.60024 · doi:10.1214/105051605000000683
[10] Dyer, M., Frieze, A. M. and Jerrum, M. (2002). On counting independent sets in sparse graphs. SIAM J. Comput. 31 1527–1541. · Zbl 1041.68045 · doi:10.1137/S0097539701383844
[11] Dyer, M., Sinclair, A., Vigoda, E. and Weitz, D. (2004). Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures Algorithms 24 461–479. · Zbl 1126.82021 · doi:10.1002/rsa.20004
[12] Galvin, D. and Tetali, P. (2006). Slow mixing of the Glauber dynamics for the hard-core model on regular bipartite graphs. Random Structures Algorithms 28 427–443. · Zbl 1105.05064 · doi:10.1002/rsa.20094
[13] Jerrum, M. R. (1995). A very simple algorithm for estimating the number of \(k\)-colourings of a low-degree graph. Random Structures Algorithms 7 157–165. · Zbl 0833.60070 · doi:10.1002/rsa.3240070205
[14] Martinelli, F. and Olivieri, E. (1994). Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys. 161 447–486. · Zbl 0793.60110 · doi:10.1007/BF02101929
[15] Moussouris, J. (1974). Gibbs and Markov random systems with constraints. J. Statist. Phys. 10 11–33. · doi:10.1007/BF01011714
[16] Vigoda, E. (2000). Improved bounds for sampling colorings. J. Math. Phys. 41 1555–1569. · Zbl 0978.60083 · doi:10.1063/1.533196
[17] Vigoda, E. (2001). A note on the Glauber dynamics for sampling independent sets. Electron. J. Combin. 8 . · Zbl 0967.68172 · emis:journals/EJC/Volume_8/Abstracts/v8i1r8.html · eudml:121186
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.