skip to main content
10.5555/1109557.1109653acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Slow mixing of glauber dynamics via topological obstructions

Published: 22 January 2006 Publication History

Abstract

Many local Markov chains based on Glauber dynamics are known to undergo a phase transition as a parameter λ of the system is varied. For independent sets on the 2-dimensional Cartesian lattice, the Gibbs distribution assigns each independent set a weight λ[I], and the Markov chain adds or deletes a single vertex at each step, It is believed that there is a critical point λc ≈ 3.79 such that for λ < λc, local dynamics converge in polynomial time while for λ > λc they require exponential time. We introduce a new method for showing slow mixing based on the presence or absence of certain topological obstructions in the independent sets. Using elementary arguments, we show that Glauber dynamics will be slow for sampling independent sets in 2 dimensions when λ ≥ 8.066, improving on the best known bound by a factor of 10. We also show they are slow on the torus when λ ≥ 6.183.

References

[1]
R. J. Baxter, I. G. Entig, and S. K. Tsang. Hard-square lattice gas. Journal of Statistical Physics, 22: 465--489, 1989.
[2]
J. van den Berg and J. E. Steif. Percolation and the hard-core lattice model. Stochastic Processes and their Applications, 49: 179--197, 1994.
[3]
C. Borgs. Polymers, contours and their applications in discrete mathematics. Monograph in preparation, 2004.
[4]
C. Borgs, J. T. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda, and V. H. Vu. Torpid mixing of some MCMC algorithms in statistical physics. Proc. 40th IEEE Symp. on Foundations of Computer Science, 218--229, 1999.
[5]
R. L. Dobrushin. The problem of uniqueness of a Gibbsian random field and the problem of phase transitions. Functional Analysis and its Applications, 2: 302--312 1968.
[6]
R. L. Dobrushin and S. B. Shlosman. Constructive criterion for the uniqueness of Gibbs fields. In Statistical physics and dynamical systems, vol. 10 of Progress in Physics, 347--370, Birhauser, Boston, 1985.
[7]
D. Galvin. Personal communication, 2004.
[8]
D. Galvin and J. Kahn. On phase transitions in the hard-core model on Zd. To appear in Combinatorics, Probability and Computing.
[9]
R. Glauber. Time dependent statistics of the Ising model. Journal of Mathematical Physics4: 294--307, 1963.
[10]
R. Kannan, M. W. Mahoney, and R. Montenegro. Rapid mixing of several Markov chains for a hard-core model. 14th Annual ISAAC, 663--675, 2003.
[11]
M. Luby and E. Vigoda. Fast convergence of the Glauber dynamics for sampling independent sets. Random Structures and Algorithms, 229--241, 1999.
[12]
N. Madras and G. Slade. The Self-Avoiding Walk. Birkhäuser, Boston, 1993.
[13]
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21: 1087--1092, 1953.
[14]
Pönitz and Tittman. Improved upper bounds for self-avoiding walks in Zd. Electronic Journal of Combinatorics, 7, 2000.
[15]
A. J. Sinclair and M. R. Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains Information and Computation82:93--133, 1989.
[16]
P. Tetali. Personal communication, 2004.

Cited By

View all
  • (2019)Algorithmic Pirogov-Sinai theoryProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316305(1009-1020)Online publication date: 23-Jun-2019
  • (2014)Clustering and mixing times for segregation models on Z2Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634098(327-340)Online publication date: 5-Jan-2014
  • (2014)Approximating the partition function of planar two-state spin systemsJournal of Computer and System Sciences10.1016/j.jcss.2014.06.00781:1(330-358)Online publication date: 1-Oct-2014
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Algorithmic Pirogov-Sinai theoryProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316305(1009-1020)Online publication date: 23-Jun-2019
  • (2014)Clustering and mixing times for segregation models on Z2Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634098(327-340)Online publication date: 5-Jan-2014
  • (2014)Approximating the partition function of planar two-state spin systemsJournal of Computer and System Sciences10.1016/j.jcss.2014.06.00781:1(330-358)Online publication date: 1-Oct-2014
  • (2011)Cluster algorithms for discrete models of colloids with barsProceedings of the Meeting on Analytic Algorithmics and Combinatorics10.5555/2790409.2790424(135-149)Online publication date: 22-Jan-2011
  • (2011)Clustering in interfering binary mixturesProceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques10.5555/2033252.2033309(652-663)Online publication date: 17-Aug-2011
  • (2007)Slow Mixing of Markov Chains Using Fault Lines and Fat ContoursProceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-540-74208-1_39(540-553)Online publication date: 20-Aug-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media