Mixing time for the Ising model: a uniform lower bound for all graphs

DOI10.1214/10-AIHP402MaRDI QIDQ1944667zbMATH OpenOpenAlexFDO

Authors Jian Ding, Yuval Peres

Publication date 26 March 2013

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.5162, https://projecteuclid.org/euclid.aihp/1317906499

zbMATH Keywords

Galuber dynamicsIsing modelmixing time

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: Consider Glauber dynamics for the Ising model on a graph of $n$ vertices. Hayes and Sinclair showed that the mixing time for this dynamics is at least $nlogn/f(Delta)$, where $Delta$ is the maximum degree and $f(Delta)=Theta(Deltalo{g}^{2}Delta)$. Their result applies to more general spin systems, and in that generality, they showed that some dependence on $Delta$ is necessary. In this paper, we focus on the ferromagnetic Ising model and prove that the mixing time of Glauber dynamics on any $n$-vertex graph is at least $(1/4+o(1))nlogn$.

Review text

The authors provide the strict mathematical analysis of the Ising model on a finite graph \(G=(V,E)\) with the interaction strength \(J\) defined by the probability measure \( \mu_G(\sigma)=Z^{-1}\exp\left(\Sigma_{u,v}J_{u,v}\sigma(u)\sigma(v)\right), \sigma\in\Omega,u,v\in E \) on the configuration space \(\Omega=\{\pm1\}^V\). The theorem, which states that the spin mixing time of Glauber dynamics has the infimum \((1/4+o(1))n\log n\) over all \(n\)-vertex graphs \(G\) and all non-negative interaction matrices \(J\), is proven.

Recommendations

• The mixing time evolution of Glauber dynamics for the mean-field Ising model
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• A general lower bound for mixing of single-site dynamics on graphs
• Glauber dynamics on nonamenable graphs: boundary conditions and mixing time
• Glauber dynamics on trees: Boundary conditions and mixing time

Cites work

• A general lower bound for mixing of single-site dynamics on graphs
• Can extra updates delay mixing?
• Cutoff for the Ising model on the lattice
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Glauber dynamics on the cycle is monotone
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 3812655 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Minimization algorithms and random walk on the d-cube

Cited in

(12)

• Exact thresholds for Ising-Gibbs samplers on general graphs
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• Mixing times for a constrained Ising process on the torus at low density
• A general lower bound for mixing of single-site dynamics on graphs
• Rapid mixing of Gibbs sampling on graphs that are sparse on average
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Can extra updates delay mixing?
• Glauber dynamics for Ising model on convergent dense graph sequences
• Swendsen-Wang dynamics for general graphs in the tree uniqueness region
• Some circumstances where extra updates can delay mixing
• The structure of emulations in classical spin models: modularity and universality
• Mixing phases and metastability for the Glauber dynamics on the p-spin Curie-Weiss model

This page was built for publication: Mixing time for the Ising model: a uniform lower bound for all graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944667)