Optimal spectral gap bounds improve spin system simulations
Beyond the Bochner Method: Optimal Spectral Gaps for Block Dynamics of Spin Systems like the $O(N)$ Model
Data Structures and Algorithms
Summary
The paper studies a way to measure how quickly certain random processes in physics and mathematics reach steady states. By improving a mathematical method called the Bochner method, the authors find more precise bounds for this speed in complex systems, including popular models like the O(N) model. Their work also gives new insights into related structures like random forests and simplicial complexes, helping understand interactions in networks and geometry. This helps computer simulations work better by knowing exactly how fast they mix.
What this means in practice
- •For statistical physics simulators: Guarantee faster and optimal mixing times for simulations of spin systems like the O(N) model with arbitrary external fields and couplings.
- •For network analysis teams: Use improved spectral gap bounds to analyze dependencies in random forests and weighted graphs for more accurate probabilistic network models.
Authors
Jonathan Leake, Anqi Li
Abstract
Let $μ$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces. We prove local-to-global spectral-gap bounds for block Glauber dynamics. Given a symmetric, entrywise nonnegative matrix $A$ with zero diagonal and $λ_{\max}(A)<1$ encoding local spectral bounds for a spin system, we derive global spectral-gap bounds for block dynamics on its marginal distributions. These bounds are sharp: the Gaussian system with covariance $(I-A)^{-1}$ attains equality for every choice of disjoint blocks. Our proof extends the Bochner method through an abstract inequality for orthogonal projections on Hilbert spaces. As an application, we prove that Glauber dynamics for the $O(N)$ model, with $N\geq 2$, arbitrary external fields, and couplings of either sign, has spectral gap at least $(1-\|J_{\mathrm{abs}}\|_{\mathrm{op}}/N)/n$, where $J$ is the interaction matrix and $J_{\mathrm{abs}}=(|J_{ij}|)$. We also obtain spectral bounds for swap walks and local spectral expansion of partite simplicial complexes. For complexes formed from disjoint groups of ranks in random flags of subspaces over $\mathbb F_q$, we obtain a one-sided local spectral expansion bound of $2\sqrt q/(q+1)$. This bound is independent of the number and sizes of each group, and is nontrivial for every prime power $q$. Finally, for random forests $F$ of any finite graph with arbitrary positive edge weights, we prove that \[ \Pr(e,f\in F)\le \frac{4}{3} \Pr(e\in F)\Pr(f\in F) \] for distinct edges $e,f$, improving the factor 2 supplied by general log-concavity bounds for matroid independent sets. The argument combines our extended Bochner method with the analysis of an auxiliary real stable polynomial.