alphaFeedback

WorksComputer Science

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤12+εβ\leq \frac{1}{2}+\varepsilon

AI contributions
Not recorded for this paper
View details

Abstract

We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by λIλI (where λλ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for β≤12+εβ\leq \tfrac{1}{2}+\varepsilon, for an absolute constant ε>0\varepsilon>0. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.

Introduction

A multi-state spin system is composed of a set V={1,…,n}V = \{1,\ldots,n\} of particles. Each site ii is associated with a set of spins SvS_v. Each possible configuration of the system is an element of the set S:=S1×⋯×Sn\mathcal{S} := S_1 \times\cdots\times S_n. Let μ\mu be a probability distribution over all configurations.

Given such a μ\mu, often one is interested in estimating certain properties of μ\mu, for example, its moments or an expectation of a given function of the spins. The MCMC method is often a method of choice in practice: One designs a Markov chain with stationary distribution μ\mu. Then, proves that this chain has an efficient mixing time, namely polynomial in nn. This in turn allows one to easily generate samples of μ\mu by running the Markov chain.

The natural Markov chain is the Glauber dynamics: Given a state x∈S\mathbf{x} \in\mathcal{S}, we choose 1≤i≤n1 \le i \le n uniformly at random. Then, we forget the spin of the ii-th particle and re-sample it according to μ\mu conditioned on x−i\mathbf{x}_{-i}, i.e., for any x∈Six \in S_i, we choose xx with probability

μ(x1,…,xi−1,x,xi+1,…,xn)∑x′∈Siμ(x1,…,xi−1,x′,xi+1,…,xn)\frac{\mu(x_1,\ldots,x_{i-1},x,x_{i+1},\ldots,x_n)}{\sum_{x' \in S_i}\mu(x_1,\ldots,x_{i-1},x',x_{i+1},\ldots,x_n)}

One fundamental question is how long it takes for this chain to mix. Let 1nP\frac{1}{n}\mathcal{P} be the transition probability matrix of the Glauber dynamics Markov chain (the factor 1/n1/n is for a notational convenience as will be clear later; essentially it implies every vertex is chosen at a unit rate w.r.t. P\mathcal{P}) then the mixing time is defined to be

max⁡x∈Smin⁡{t:∥1xT(1nP)t−μ∥TV≤14}.\max_{x\in S}\min\left\{t:\left\|\mathbf{1}_x^{\mathsf{T}}\left(\frac{1}{n}\mathcal{P}\right)^t-\mu\right\|_{\mathrm{TV}}\le\frac{1}{4}\right\}.

To bound the mixing time of 1nP\frac{1}{n}\mathcal{P} a method of choice is to bound its spectral gap.

Theorem 1.1. Suppose that for any function f:S→Rf:S\to\mathbb{R} satisfying Eμf=0\mathbb{E}_{\mu}f=0,

⟨Lf,f⟩μ≥ε⟨f,f⟩μ.\langle\mathcal{L}f,f\rangle_{\mu}\ge\varepsilon\langle f,f\rangle_{\mu}.

where L=nI−P\mathcal{L}=nI-\mathcal{P} and for two functions f,g:S→Rf,g:S\to\mathbb{R}, ⟨f,g⟩μ=EX∼μ[f(X)g(X)]\langle f,g\rangle_{\mu}=\mathbb{E}_{X\sim\mu}[f(X)g(X)]. Then, the mixing time of 1nP\frac{1}{n}\mathcal{P} is bounded by

O(n⋅log⁡(1μmin⁡)ε).O\left(\frac{n\cdot\log\left(\frac{1}{\mu_{\min}}\right)}{\varepsilon}\right).

where μmin⁡=min⁡xμ(x)\mu_{\min}=\min_x\mu(x).

Over the last few decades, several techniques have been developed to bound the mixing time of such a chain such as (path) coupling, canonical paths, and spectral independence. Of particular interest to us is a family of local to global theorems that often go by the name of trickledown theorems (or more classically by the name of Dobrushin’s condition or path coupling).

In such techniques given two arbitrary particles i,ji,j one bounds the worst case interaction between i,ji,j given the status of the rest of the particles. This is classically studied as the worst case influence of jj to ii in the sense that by changing the spin of particle jj how much the distribution of ii can change in total variation distance [18, 14, 15]. More modern techniques show that it is enough to bound the worst case “spectral influence” of jj to ii; that is the maximum eigenvalue of the correlation matrix of Xi,XjX_i,X_j in the worst case when all other particles are fixed (for concreteness such a matrix is in R(Si∪Sj)×(Si∪Sj)\mathbb{R}^{(S_i\cup S_j)\times(S_i\cup S_j)} with entries corresponding to the conditional probabilities, i.e., P[Xi∣Xj=s]\mathbb{P}[X_i\mid X_j=s] for entries in the row corresponding to spin ss for site jj).

Let λi,j\lambda_{i,j} be the (spectral) influence of jj to ii and let Λ\Lambda be the matrix of all pairwise influences; then it has been shown that if ∥Λ∥op<1\|\Lambda\|_{\mathrm{op}}<1 the natural Markov chain called the Glauber dynamics mixes rapidly, see e.g., [22].

The aforementioned technique has found many applications e.g., in studying graph coloring or multi-state hard core model or even in studying graphical models [18, 19, 22, 6, 23]. Although it is very powerful, it comes short of analyzing many applications of the natural Glauber dynamics. Ideally, one would like an average local-to-global theorem which allows for an “average spectral influence” of particle jj to ii instead of taking the worst case spin of all other particles. The main result of this manuscript is such a technique that we call rank-1-perturbed trickledown theorem.

Rank-1-perturbed trickledown theorem: Given the nn-particle spin system, and function f:S1×⋯×Sn→Rf:S_1\times\cdots\times S_n\to\mathbb{R} let PifP_if be the function which averages ff on SiS_i such that the spin of all other particles are fixed, namely:

Pif(x1,…,xn)=Eμ[f(X1,…,Xn)∣Xj=xj,∀j≠i].P_if(x_1,\ldots,x_n)=\mathbb{E}_{\mu}[f(X_1,\ldots,X_n)\mid X_j=x_j,\forall j\ne i].

Let P=∑iPi\mathcal{P} = \sum_i P_i. Then, it follows that the transition probability matrix of the Glauber dynamics is 1nP\frac{1}{n}\mathcal{P}. We let Li=I−PiL_i = I - P_i and L=∑iLi\mathcal{L} = \sum_i L_i. It is not hard to see that the operator PiP_i is a projection, i.e., for any function ff, Pi2f=PifP_i^2 f = P_i f and it is self-adjoint with respect to the inner product defined below. Similarly, LiL_i's are projections. Define the inner-product

⟨f,g⟩μ=EX∼μ[f(X)g(X)].\langle f,g\rangle_\mu= \mathbb{E}_{X\sim\mu}[f(X)g(X)].

It is not hard to see that Pi,LiP_i,L_i are self-adjoint with respect to this inner-product, i.e., for two functions f,gf,g

⟨f,Pig⟩=Eμ[fEμ[g∣X−i]]=Eμ[Eμ[f∣X−i]Eμ[g∣X−i]]=Eμ[Eμ[f∣X−i]g]=⟨Pif,g⟩\langle f,P_i g\rangle= \mathbb{E}_\mu[f\mathbb{E}_\mu[g\mid X_{-i}]] = \mathbb{E}_\mu[\mathbb{E}_\mu[f\mid X_{-i}]\mathbb{E}_\mu[g\mid X_{-i}]] = \mathbb{E}_\mu[\mathbb{E}_\mu[f\mid X_{-i}]g] = \langle P_i f,g\rangle

and since Li=I−PiL_i = I - P_i, the self-adjointness of LiL_i follows. Additionally, we have the following equivalent expressions of the Dirichlet form

E(f):=Eμ[fLf]=∑iEμ[fLif]=∑iEμ[LifLif]=∑iEμ[(Lif)2].(1)\mathcal{E}(f) := \mathbb{E}_\mu[f\mathcal{L}f] = \sum_i \mathbb{E}_\mu[fL_i f] = \sum_i \mathbb{E}_\mu[L_i fL_i f] = \sum_i \mathbb{E}_\mu[(L_i f)^2]. \tag*{(1)}

Fact 1.2. If for any function f:S→Rf:S\to\mathbb{R},

⟨Lf,Lf⟩≥ε⟨Lf,f⟩=ε⋅E(f),\langle\mathcal{L}f,\mathcal{L}f\rangle\ge\varepsilon\langle\mathcal{L}f,f\rangle= \varepsilon\cdot\mathcal{E}(f),

then the spectral gap of the Glauber dynamics 1nP\frac{1}{n}\mathcal{P} is at least ε/n\varepsilon/n.

Proof. Given an arbitrary function gg, since L⪰0\mathcal{L}\succeq0, we let f=L−1/2gf = \mathcal{L}^{-1/2}g (to be precise, we need to take the pseudo-inverse of L\mathcal{L} since L\mathcal{L} has a 00 eigenvalue). Having this,

⟨Lg,g⟩=⟨Lf,Lf⟩≥ε⋅⟨Lf,f⟩=⟨g,g⟩,\langle\mathcal{L}g,g\rangle= \langle\mathcal{L}f,\mathcal{L}f\rangle\ge\varepsilon\cdot\langle\mathcal{L}f,f\rangle= \langle g,g\rangle,

where all the inner-products are with respect to μ\mu. This concludes the proof.

We emphasize that the above machinery of using the “averaged curvature condition” ([?], Equation 1.16.6, Proposition 4.8.3) was recently employed by Göbel, Jenssen, Michelen, Pappik, Perkins and Schiller [21] to re-prove a recent trickledown theorem of Chen, Chen, Chen, Yin, and Zhang [10]. Their proof was a motivation for us to consider this technique for the SK model.

Definition 1.3. We say P\mathcal{P} exhibits a rank-1-perturbed trickledown condition if there exists a family of vectors {m(X)}∈Rn\{m(X)\}\in\mathbb{R}^n, for all X∈SX\in S such that for any function f:S→Rf:S\to\mathbb{R} and any 1≤i<j≤n1\le i<j\le n and any (feasible) spin x−i−jx_{-i-j} (for all particles except i,ji,j) we have

EX∼μ[Lif(X)Ljf(X)∣x−i−j]≥−ai,jE[Lif(X)Ljf(X)mi(X)mj(X)∣x−i−j]\mathbb{E}_{X\sim\mu}[L_i f(X)L_j f(X)\mid x_{-i-j}] \ge-a_{i,j}\mathbb{E}[L_i f(X)L_j f(X)m_i(X)m_j(X)\mid x_{-i-j}]

References

  1. [1]Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence: optimal mixing of down-up random walks. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 1418–1430, New York, NY, USA, 2022. Association for Computing Machinery.DOI
  2. [2]Nima Anari, Frederic Koehler, and Thuy-Duong Vuong. Trickle-down in localization schemes and applications. In STOC’24—Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1094–1105. ACM, New York, [2024] ©2024.
  3. [3]Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. SIAM Journal on Computing, 53(6):FOCS20–1–FOCS20–37, 2024.
  4. [4]Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 323–334, 2022.
  5. [5]Roland Bauerschmidt and Thierry Bodineau. A very simple proof of the LSI for high temperature spin systems. J. Funct. Anal., 276(8):2582–2588, 2019.DOI
  6. [6]Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel ˇStefankoviˇc, and Eric Vigoda. On mixing of Markov chains: coupling, spectral independence, and entropy factorization. Electron. J. Probab., 27:Paper No. 142, 42, 2022.
  7. [8]Christer Borell. Gaussian Radon measures on locally convex spaces. Math. Scand., 38(2):265–284, 1976.
  8. [9]Z. D. Bai and Y. Q. Yin. Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix. Ann. Probab., 16(4):1729–1741, 1988.DOI
  9. [10]Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid mixing on random regular graphs beyond uniqueness. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science—FOCS 2025, pages 2170–2193. IEEE Comput. Soc. Press, Los Alamitos, CA, [2025] ©2025.
  10. [11]Yuansi Chen and Ronen Eldan. Localization schemes: a framework for proving mixing bounds for Markov chains. Duke Math. J., 174(8):1431–1510, 2025.
  11. [12]Michael Celentano. Sudakov–Fernique post-AMP, and a new proof of the local convexity of the TAP free energy. The Annals of Probability, 52(3):923 – 954, 2024.
  12. [13]B. S. Cirel’son, I. A. Ibragimov, and V. N. Sudakov. Norms of Gaussian sample functions. In Proceedings of the Third Japan-USSR Symposium on Probability Theory (Tashkent, 1975), volume Vol. 550 of Lecture Notes in Math., pages 20–41. Springer, Berlin-New York, 1976.DOI
  13. [14]Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Dobrushin conditions and systematic scan. Combin. Probab. Comput., 17(6):761–779, 2008.
  14. [15]Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Matrix norms and rapid mixing for spin systems. Ann. Appl. Probab., 19(1):71–107, 2009.
  15. [16]Jian Ding, Eyal Lubetzky, and Yuval Peres. The mixing time evolution of Glauber dynamics for the mean-field Ising model. Comm. Math. Phys., 289(2):725–764, 2009.DOI
  16. [17]Ewan Davies, Holden Lee, Juspreet Singh Sandhu, and Jonathan Shi. Weak Poincaré Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model, 2026.arxiv.org/abs/2607.08160
  17. [18]Roland L Dobrushin. Prescribing a system of random variables by conditional distributions. Theory of Probability & Its Applications, 15(3):458–486, 1970.DOI
  18. [19]R. L. Dobrushin and S. B. Shlosman. Constructive criterion for the uniqueness of Gibbs field. In Statistical physics and dynamical systems (Kőszeg, 1984), volume 10 of Progr. Phys., pages 347–370. Birkhäuser Boston, Boston, MA, 1985.DOI
  19. [20]Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. A spectral condition for spectral gap: fast mixing in high-temperature Ising models. Probability Theory and Related Fields, 182(3):1035–1051, 2022.arxiv.org/abs/2007.08200
  20. [21]Andreas Göbel, Matthew Jenssen, Marcus Michelen, Marcus Pappik, Will Perkins, and Leon Schiller. A simple proof of rapid mixing on random regular graphs beyond uniqueness, 2026.arxiv.org/abs/2606.27545
  21. [22]Thomas P Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 39–46. IEEE, 2006.DOI
  22. [23]Jonathan Leake and Shayan Oveis Gharan. Trickle-down theorems via c-lorentzian polynomials ii: Pairwise spectral influence and improved dobrushin’s condition. arXiv preprint arXiv:2510.06549, 2025.arxiv.org/abs/2510.06549
  23. [24]David A. Levin, Malwina J. Luczak, and Yuval Peres. Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability. Probab. Theory Related Fields, 146(1-2):223–265, 2010.
  24. [25]M Mezard, G Parisi, and M Virasoro. Spin Glass Theory and Beyond. WORLD SCI-ENTIFIC, 1986.
  25. [26]Izhar Oppenheim. Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps. Discrete Comput. Geom., 59(2):293–330, March 2018.
  26. [27]Mark Sellke. Statistics 291: Lecture 4: Geometric and Statistical Consequences of Annealed Free Energy, February 2024. Lecture notes, scribed by Zad Chin.
  27. [28]H. Sompolinsky and Annette Zippelius. Dynamic theory of the spin-glass phase. Phys. Rev. Lett., 47:359–362, Aug 1981.DOI
  28. [29]Richard A. Vitale. Some comparisons for Gaussian processes. Proc. Amer. Math. Soc., 128(10):3043–3046, 2000.
  29. [30]Sihan Wang. Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β < 1/2. arXiv preprint arXiv:2608.22159, 2026.arxiv.org/abs/2608.22159

Paper details

vlnc:W_j4q3zw6g
v1 · latestHistory (1)

published ·

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Computer Science

Not recorded for this paper · View statement →

Looking for related papers…
Contents