Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
From MaRDI portal
Publication:2428505
DOI10.1007/s00440-010-0329-0zbMath1250.60034arXiv1011.3058MaRDI QIDQ2428505
Prasad Tetali, Jennifer T. Chayes, Christian Borgs
Publication date: 26 April 2012
Published in: Probability Theory and Related Fields (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.3058
60J22: Computational methods in Markov chains
60K35: Interacting random processes; statistical mechanics type models; percolation theory
60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Swendsen‐Wang algorithm on the mean‐field Potts model, Unnamed Item, Rapid mixing of Swendsen–Wang dynamics in two dimensions, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Unnamed Item, Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures, Sampling from the low temperature Potts model through a Markov chain on flows, Spatial mixing and the random‐cluster dynamics on lattices, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, Low-temperature Ising dynamics with random initializations, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics, Glauber dynamics for the mean-field Potts model, The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions, Tunneling behavior of Ising and Potts models in the low-temperature regime, Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\), Algorithmic Pirogov-Sinai theory, Exponentially slow mixing in the mean-field Swendsen-Wang dynamics, Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions, Cutoff for the Swendsen-Wang dynamics on the lattice, Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019, Random-cluster dynamics in \(\mathbb {Z}^2\), Comparison of Swendsen-Wang and heat-bath dynamics, Mixing of the Glauber dynamics for the ferromagnetic Potts model
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Interfaces in the Potts model. I: Pirogov-Sinai theory of the Fortuin- Kasteleyn representation
- Faster mixing and small bottlenecks
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A unified approach to phase diagrams in field theory and statistical mechanics
- Edge-isoperimetric inequalities in the grid
- Relaxation to equilibrium for two dimensional disordered Ising systems in the Griffiths phase
- On the mixing time of a simple random walk on the super critical percolation cluster
- Glauber dynamics on trees and hyperbolic graphs
- Bound on the mass gap for finite volume stochastic Ising models at low temperature
- Discontinuity of the magnetization in one-dimensional \(1/| x-y| ^ 2\) Ising and Potts models.
- The Swendsen-Wang process does not always mix rapidly
- Mixing properties of the Swendsen–Wang process on the complete graph and narrow grids
- Lifting Markov chains to speed up mixing
- On Counting Independent Sets in Sparse Graphs
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Mathematical Aspects of Mixing Times in Markov Chains