Pith. sign in

REVIEW 1 cited by

Rapid mixing of Glauber dynamics via spectral independence for all degrees

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2105.15005 v3 pith:A3YILHN5 submitted 2021-05-31 cs.DS math-phmath.MPmath.PR

Rapid mixing of Glauber dynamics via spectral independence for all degrees

classification cs.DS math-phmath.MPmath.PR
keywords deltaspectraldynamicsmixingglauberindependencefractime
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

We prove an optimal $\Omega(n^{-1})$ lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with $n$ vertices in the tree uniqueness regime. This spectral gap holds for all, including unbounded, maximum degree $\Delta$. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack $\delta\in(0,1)$: $\bullet$ $C(\delta) n^2\log n$ mixing time for the hardcore model with fugacity $\lambda\le (1-\delta)\lambda_c(\Delta)= (1-\delta)\frac{(\Delta - 1)^{\Delta - 1}}{(\Delta - 2)^\Delta}$; $\bullet$ $C(\delta) n^2$ mixing time for the Ising model with edge activity $\beta\in\left[\frac{\Delta-2+\delta}{\Delta-\delta},\frac{\Delta-\delta}{\Delta-2+\delta}\right]$; where the maximum degree $\Delta$ may depend on the number of vertices $n$, and $C(\delta)$ depends only on $\delta$. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Nonlinear Exchange Dynamics for Independent Sets

    cs.DS 2026-07 conditional novelty 7.0

    Nonlinear exchange dynamics for hard-core independent sets converge to the correct Gibbs measures and yield a fast prescribed-density sampler, with a conditional prescribed-marginal sampler.