Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRapid mixing of Glauber dynamics via spectral independence for all degrees
136
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 $deltain(0,1)$: $bullet$ $C(delta) n^2log n$ mixing time for the hardcore model with fugacity $lambdale (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 $betainleft[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.
rate research
Read More
The six-vertex model in statistical physics is a weighted generalization of the ice model on $mathbb{Z}^2$ (i.e., Eulerian orientations) and the zero-temperature three-state Potts model (i.e., proper three-colorings). The phase diagram of the model depicts its physical properties and suggests where local Markov chains will be efficient. In this paper, we analyze the mixing time of Glauber dynamics for the six-vertex model in the ordered phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result bounding the mixing time of Glauber dynamics in the ferroelectric phase. Our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models (or routings). We analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper $q$-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree $Delta$ provided $qge (alpha^*+delta)Delta$ where $alpha^*approx 1.763$ is the unique solution to $alpha^*=exp(1/alpha^*)$ and $delta>0$ is any constant. This is the first efficient algorithm for sampling proper $q$-colourings in this regime with possibly unbounded $Delta$. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].
We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent $q$-spin system on a graph $G = (V,E)$ with maximum degree $Delta$. Notably, for several interesting examples, our bound covers the entire regime of $Delta$ excluded by arguments based on coupling with the stationary distribution. As concrete applications, by combining our new lower bound with known spectral independence computations and known coupling arguments: (1) We show that for a triangle-free graph $G = (V,E)$ with maximum degree $Delta geq 3$, the Glauber dynamics for the uniform distribution on proper $k$-colorings with $k geq (1.763dots + delta)Delta$ colors has spectral gap $tilde{Omega}_{delta}(|V|^{-1})$. Previously, such a result was known either if the girth of $G$ is at least $5$ [Dyer et.~al, FOCS 2004], or under restrictions on $Delta$ [Chen et.~al, STOC 2021; Hayes-Vigoda, FOCS 2003]. (2) We show that for a regular graph $G = (V,E)$ with degree $Delta geq 3$ and girth at least $6$, and for any $varepsilon, delta > 0$, the partition function of the hardcore model with fugacity $lambda leq (1-delta)lambda_{c}(Delta)$ may be approximated within a $(1+varepsilon)$-multiplicative factor in time $tilde{O}_{delta}(n^{2}varepsilon^{-2})$. Previously, such a result was known if the girth is at least $7$ [Efthymiou et.~al, SICOMP 2019]. (3) We show for the binomial random graph $G(n,d/n)$ with $d = O(1)$, with high probability, an approximately uniformly random matching may be sampled in time $O_{d}(n^{2+o(1)})$. This improves the corresponding running time of $tilde{O}_{d}(n^{3})$ due to [Jerrum-Sinclair, SICOMP 1989; Jerrum, 2003].
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $kleq log n$, and an error parameter $epsilon > 0$, our algorithm runs in space $tilde{O}(klog (Ncdot w_{mathrm{max}}/w_{mathrm{min}}))$ where $w_{mathrm{max}}$ and $w_{mathrm{min}}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $tilde{O}(n^{1+2/k}/epsilon^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $epsilon$. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastavas effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by $k$ above, and the resulting sparsity that can be achieved.
We consider a system of classical particles, interacting via a smooth, long-range potential, in the mean-field regime, and we optimally analyze the propagation of chaos in form of sharp estimates on many-particle correlation functions. While approaches based on the BBGKY hierarchy are doomed by uncontrolled losses of derivatives, we propose a novel non-hierarchical approach that focusses on the empirical measure of the system and exploits a Glauber type calculus with respect to initial data in form of higher-order Poincare inequalities for cumulants. This main result allows to rigorously truncate the BBGKY hierarchy to an arbitrary precision on the mean-field timescale, thus justifying the Bogolyubov corrections to mean field. As corollaries, we also deduce a quantitative central limit theorem for fluctuations of the empirical measure, and we partially justify the Lenard-Balescu limit for a spatially homogeneous system away from thermal equilibrium.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
