Can extra updates delay mixing?

DOI10.1007/S00220-013-1776-0zbMATH Open1277.82036arXiv1112.0603OpenAlexW2031651515MaRDI QIDQ378052FDOQ378052

Authors: Yuval Peres, Peter Winkler 

Publication date: 11 November 2013

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance or the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a Hamming metric, single-site dynamics mixes in O(n log n) steps on an n-vertex graph. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of log n compared to updates at uniform random locations on an n-vertex graph. Our result is especially effective in comparing block and single-site dynamics; it has already been used in works of Martinelli, Sinclair, Mossel, Sly, Ding, Lubetzky, and Peres in various combinations.

Full work available at URL: https://arxiv.org/abs/1112.0603

Recommendations

• Some circumstances where extra updates can delay mixing
• A general lower bound for mixing of single-site dynamics on graphs
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Dobrushin Conditions for Systematic Scan with Block Dynamics
• Dobrushin Conditions and Systematic Scan

zbMATH Keywords

Hamming distanceIsing modelMarkov random fieldsGlauber dynamics

Mathematics Subject Classification ID

Random fields (60G60) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Statistical mechanics of magnetic materials (82D40)

Cites Work

• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• Glauber dynamics on trees and hyperbolic graphs
• Title not available (Why is that?)
• Dobrushin Conditions and Systematic Scan
• Glauber dynamics on the cycle is monotone
• Glauber dynamics on trees: Boundary conditions and mixing time
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Mixing time for the Ising model: a uniform lower bound for all graphs
• Systematic scan for sampling colorings
• Random sampling for the monomer-dimer model on a lattice.
• Mixing in time and space for lattice spin systems: A combinatorial view
• Mixing time for the solid-on-solid model
• Some circumstances where extra updates can delay mixing
• Mixing time of critical Ising model on trees is polynomial in the height
• On the mixing time of the 2D stochastic Ising model with ``Plus boundary conditions at low temperature

Cited In (23)

• Mixing time of critical Ising model on trees is polynomial in the height
• Cutoff for the cyclic adjacent transposition shuffle
• Optimal strong stationary times for random walks on the chambers of a hyperplane arrangement
• Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
• Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion
• Mixing time for the Ising model: a uniform lower bound for all graphs
• A one-dimensional coagulation-fragmentation process with a dynamical phase transition
• Monotonicity for continuous-time random walks
• Mixing times for the simple exclusion process in ballistic random environment
• Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
• Title not available (Why is that?)
• Mixing times for the simple exclusion process with open boundaries
• Spectral gap and cutoff phenomenon for the Gibbs sampler of \(\nabla \varphi\) interfaces with convex potential
• The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
• The \(S_k\) shuffle block dynamics
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Some things we've learned (about Markov chain Monte Carlo)
• Cutoff for polymer pinning dynamics in the repulsive phase
• How quickly can we sample a uniform domino tiling of the \(2L\times 2L\) square via Glauber dynamics?
• Spatial mixing and the random‐cluster dynamics on lattices
• Some circumstances where extra updates can delay mixing
• Mixing time of the adjacent walk on the simplex
• Mixing time for the asymmetric simple exclusion process in a random environment

This page was built for publication: Can extra updates delay mixing?

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