Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

1. Introduction.

• The proof obtains optimal mixing by showing constant-rate relative-entropy contraction, analogous to a modified log-Sobolev inequality, rather than relying only on spectral-gap decay.The approach improves prior spectral-independence results whose dependence on the uniqueness gap was substantially worse.Source: §1 · p. 3
• The work establishes O(n log n) mixing for antiferromagnetic 2-spin systems on bounded-degree graphs throughout the up-to-Δ uniqueness region.For the hard-core model, this gives O(n log n) mixing when λ ≤ (1−δ)λ_c(Δ); for Ising systems, it gives the corresponding uniqueness-range bounds for both interaction signs.Source: §1 · p. 4
• The framework extends to q-colorings of triangle-free graphs with q ≥ (α*+δ)Δ, where α*≈1.763, yielding O(n log n) mixing.It also gives O(m log n) mixing for monomer-dimer sampling on bounded-degree graphs, improving the previously stated O(n^2m log n) bound.Source: §1 · p. 5
• The results also recover O(n log n) mixing for ferromagnetic 2-spin systems in the parameter ranges previously known only with weaker bounds and yield asymptotically optimal standard and modified log-Sobolev constants.For the Ising model specifically, the constant can scale as Δ^O(1/δ) for sufficiently large n, even allowing unbounded degree.Source: §1 · pp. 4–5

1.1. Result for General Spin Systems.

• The general framework encompasses hard-core systems, Ising models, colorings, and monomer-dimer models, under the paper’s total-connectivity assumption.Total connectivity ensures feasible conditioned configurations remain connected by single-site changes, making Glauber dynamics ergodic with the Gibbs distribution as stationary measure.Source: §1.1 · p. 6
• For a general totally connected spin system on a graph of maximum degree Δ, bounded marginals and η-spectral independence imply a modified log-Sobolev constant of order 1/n and O(n log n) mixing.The influence matrix measures how fixing one vertex spin changes another vertex’s marginal, while spectral independence uniformly bounds its largest eigenvalue under conditionings.Source: §1 · p. 3, §1.1 · pp. 6–7
• The results supersede prior spin-system bounds in the bounded-degree regime because spin systems have marginal boundedness depending only on their parameters and maximum degree.The cited prior results achieved poly(∆) × n^O(η) mixing without assuming marginal boundedness.Source: §1.1 · p. 8

1.2. Result for General Simplicial Complexes.

• The main theorem requires comparing the order-(n, n−ℓ) block dynamics, with ℓ = Θ(n), to single-site Glauber dynamics; this comparison is a central technical contribution.The order-(n, n−1) down-up walk corresponds to Glauber dynamics, whereas order-(n, n−ℓ) updates uniformly random vertex subsets.Source: §1.2 · pp. 9–10
• The paper proves modified log-Sobolev inequalities and mixing bounds for arbitrary weighted simplicial-complex down-up and up-down walks using local-to-global entropy contraction.These requirements translate marginal boundedness and spectral independence into simplicial-complex conditions.Source: §1.2 · pp. 9–10
• For distributions over [q]^V, marginal boundedness transfers to the associated weighted simplicial complex with b_k = b^(n−k), while η-spectral independence yields local expansion ζ_k = η^(n−k−1).The construction represents configurations as maximal faces and partial configurations as intermediate-dimensional faces.Source: §1.2 · pp. 8–10
• Theorem 1.19 gives both walk types a modified log-Sobolev inequality whenever all marginals are bounded and every local walk has sufficient spectral expansion.The theorem applies to every order pair 0 ≤ r < s ≤ n, with an explicit constant κ(r, s).Source: §1.2 · p. 10
• Theorem 1.19 generalizes results for strongly log-concave distributions and Poincaré inequalities, addressing a local-to-global modified log-Sobolev question in the bounded-marginals setting.The paper identifies this theorem as independently interesting for future applications.Source: §1.2 · p. 10

2.1. Approximate Tensorization and Uniform Block Factorization.

• Approximate tensorization implies O(n log n) Glauber-dynamics mixing and bounds spectral, log-Sobolev, entropy-decay, concentration, and mixing-time quantities.It expresses weak dependence, with product distributions satisfying constant C1 = 1; see.Source: §2.1 · p. 11
• The paper generalizes single-site entropy factorization to ℓ-uniform blocks, corresponding to heat-bath dynamics that uniformly update ℓ vertices.Approximate tensorization is the special case ℓ = 1; the framework is motivated by high-dimensional expansion and block factorization [12].Source: §2.1 · pp. 11–12
• For b-marginally bounded Gibbs distributions on maximum-degree-∆ graphs, linear-sized ℓ-uniform block factorization implies approximate tensorization for ℓ = ⌈θn⌉.The parameter θ depends on b and ∆, and the reduction follows from a shattering argument.Source: §2.1 · p. 12

2.2. Simplicial Complexes and Entropy Contraction.

• Spectral independence plus marginal boundedness yields linear-sized block factorization for arbitrary distributions through simplicial-complex entropy contraction.Uniform block factorization is equivalent to global entropy contraction, and local spectral expansion with bounded marginals implies that contraction.Source: §2.2 · pp. 12–13

2.3. Wrapping up.

• Combining the reductions, Theorem 2.9 establishes approximate tensorization with an n-independent constant for marginally bounded, spectrally independent Gibbs distributions on bounded-degree graphs.Theorem 1.12 and the paper’s mixing results then follow; prior spectral-independence results cover antiferromagnetic 2-spin systems and sufficiently large-q colorings.Source: §2.3 · p. 15
• The monomer-dimer application proves spectral independence on bounded-degree graphs using a two-step recursion, supplying the previously missing ingredient for that model.This result is stated as Theorem 2.10.Source: §2.3 · p. 15

2.4. Outline of Paper.

• Sections 4–7 execute the reductions, prove monomer-dimer spectral independence, and complete the main mixing-time results, while Section 8 discusses open problems and Appendix A treats variance.Section 5 additionally reduces global to local entropy contraction and then to local spectral expansion under bounded marginals.Source: §2.4 · pp. 15–16

3. Preliminaries.

• For finite distributions, the section defines expectation, variance, covariance, entropy, and KL divergence via relative density.Entropy uses the convention 0 log 0 = 0, and KL divergence equals the entropy of the relative density.Source: §3 · p. 16
• It introduces the Donsker–Varadhan variational representation for KL divergence and standard Dirichlet-form, Poincaré, log-Sobolev, and entropy-decay notions.These definitions apply to ergodic reversible chains with stationary distribution µ, including Glauber dynamics.Source: §3 · pp. 16–17
• For conditioned configurations, conditional expectation and entropy satisfy µ(f) = µ[µ_S(f)] and Ent(f) = µ[Ent_S(f)] + Ent[µ_S(f)].The notation treats conditional expectation and entropy as functions of the boundary condition outside S.Source: §3 · p. 17

3.1. Implications of Approximate Tensorization.

• Approximate tensorization with constant C1 gives Glauber dynamics a Poincaré constant 1/(C1 n) and a modified log-Sobolev constant with the same 1/(C1 n) scaling.The stated consequences also include a mixing-time bound, concentration for Hamming-Lipschitz functions, and standard log-Sobolev consequences under marginal boundedness.Source: §3.1 · pp. 17–18
• The analogous ℓ-uniform block entropy factorization yields corresponding consequences for heat-bath dynamics updating ℓ vertices per step.The section notes that these implications are established results and supplies references for their proofs.Source: §3.1 · p. 18

4. Approximate Tensorization via Uniform Block Factorization.

• Assuming b-marginal boundedness and ⌈θn⌉-uniform block factorization with θ ≤ b^2/(4e∆), µ satisfies approximate tensorization with constant Θ(C), establishing Lemma 2.3.The setting is an n-vertex graph of maximum degree at most ∆.Source: §4 · pp. 18–19
• A uniformly random block induces small connected components, allowing product-measure entropy factorization on components to reduce the problem to small subgraphs and bound the constant by a converging series.Components have constant expected size and size O(log n) with high probability.Source: §4 · p. 19
• The proof combines product-measure factorization, a crude exponential bound for b-marginally bounded Gibbs distributions, and a random-subset component-size estimate.The component estimate applies to uniformly random subsets of size ⌈θn⌉ in graphs of maximum degree at most ∆.Source: §4 · p. 19

4.1. Proof of Technical Lemmas.

• Lemma 4.2 bounds the approximate tensorization constant using the spectral gap, standard log-Sobolev constant, Cheeger conductance, and total-connectivity assumption.Lemma 4.4 states that each vertex belongs to at most (e∆)k−1 connected induced k-vertex subgraphs [9, Lemma 2.1].Source: §4.1 · pp. 20–22

• The section proves Lemma 2.8 by establishing global entropy contraction under local spectral expansion.Source: §5 · p. 22

5.1 Preliminaries for simplicial complexes

• Subsection 5.1 introduces the necessary preliminaries for simplicial complexes.Source: §5 · p. 22

5.2 Local-to-global scheme

• Subsection 5.2 presents a general local-to-global scheme for proving entropy contraction.Source: §5 · p. 22

5.1.1. Global Walks.

• Global walks are defined through down-up and up-down motions on face distributions, with Glauber dynamics and heat-bath block dynamics as special cases.For a distribution μ over [q]^V, Glauber dynamics is the order-(n,n−1) down-up walk, while updating ℓ vertices is the order-(n,n−ℓ) down-up walk.Source: §5.1.1 · pp. 22–23

5.1.2. Local Walks.

• Local walks arise on links of faces, where conditioning a distribution corresponds to the induced link distribution and the local walk has stationary distribution πτ,1.The local walk Pτ is defined from the order-(1,2) up-down walk on the link and can be viewed as a weighted graph walk on link vertices and vertex-pairs.Source: §5.1.2 · pp. 23–24
• The simplicial-complex framework supports decomposing global-walk mixing properties into local-walk properties, while its links represent restrictions to conditioned configurations.The section also notes that these restriction-chain analogues overlap, unlike the partitioning condition in.Source: §5.1.2 · pp. 23–24

5.1.3. Proofs of Claim 1.16 and Lemma 2.7.

• The proofs establish the stated claims using marginal boundedness and an entropy decomposition for pure weighted simplicial complexes.For spin systems, restrictions of functions correspond exactly to functions on links, allowing Lemma 5.1 to imply Lemma 2.7.Source: §5.1.3 · pp. 24–25

5.1.4. Implications of Global Entropy Contraction.

• Global entropy contraction with rate κ yields Poincaré, modified log-Sobolev, relative-entropy decay, mixing-time, and concentration guarantees for the associated walks.The corresponding constants for the first three guarantees are λ = κ, ρ0 = κ, and α = κ; the same mixing bound applies to the up-down walk.Source: §5.1.4 · pp. 25–26

Motivation

• The entropy theorem extends the local-to-global framework previously linking local spectral expansion and variance contraction to global mixing behavior.The section presents entropy contraction as an analogous local-to-global phenomenon.Source: §5.2 · pp. 26–27

Local Entropy Contraction

• The definition restricts local contraction to local functions induced by global functions, which suffices for the order-(n, k) down-up walks studied here.This weaker formulation also facilitates deriving local entropy contraction from local spectral expansion in subsection 5.3.Source: §5.2 · pp. 26–27

Local-to-Global Entropy Contraction

• Theorem 5.4 shows that (α_0, …, α_{n−2})-local entropy contraction implies global entropy contraction for every function and every 1 ≤ k ≤ n−1.The resulting global rate is expressed through cumulative products Γ_k derived from the local parameters α_j.Source: §5.2 · p. 27

Applications

• For homogeneous strongly log-concave distributions, gives α_k = 1 for all k, so Γ_k = 1 and Theorem 5.4 recovers Lemma 11 of.The required (1, …, 1)-local entropy contraction is supplied by Lemma 10 of.Source: §5.2 · p. 27

5.3. Local Entropy Contraction via Local Spectral Expansion.

• Theorem 5.6 shows that marginal boundedness plus local spectral expansion implies local entropy contraction for every level 0 ≤ k ≤ n − 2.This implication supplies the missing ingredient needed, together with Theorem 5.4, to prove Lemma 2.8.Source: §5.3 · p. 28

5.3.1. Proof of the First Bound.

• The first bound gives α_k = 1 − Θ(ζ_k) by combining spectral control on link walks with balance of induced local functions and entropy–variance comparison.The argument uses Lemmas 5.8–5.10 for links of marginally bounded complexes; this bound is the more subtle and informative one.Source: §5.3 · p. 28, §5.3.1 · p. 29

5.3.2. Proof of the Second Bound.

• The second bound reduces entropy contraction to a standard log-Sobolev estimate, compares that constant with spectral gap, and extends the result to every link.Marginal boundedness supplies the needed lower bound on two-element marginals, and the resulting bound remains useful when the first bound is vacuous.Source: §5.3 · p. 28, §5.3.2 · pp. 32–33

6. Spectral Independence for the Monomer-Dimer Model.

• The monomer-dimer Gibbs distribution on matchings, equivalently the hard-core model on the line graph, is analyzed using an edge-based pairwise influence notion equivalent to the standard definition.The model assigns weight λ^|M| to each matching, and spectral independence requires uniformly bounding the largest eigenvalue under feasible conditioning.Source: §6 · pp. 34–35
• Theorem 6.1 establishes a spectral-independence bound for monomer-dimer models on graphs of maximum degree at most Δ, uniformly over feasible edge boundary conditions.The proof combines a graph-to-tree reduction with a bound on total edge influence in bounded-degree trees; the resulting eigenvalue control follows from maximum absolute row sums.Source: §6 · pp. 35–36

6.1. Reducing Influences in Graphs to Influences in Trees: Proof of Theorem 6.3.

• Influences in a graph are related to influences in its self-avoiding-walk tree through Proposition 6.6, proved using multivariate matching-polynomial identities.Lemma 6.8 expresses the tree matching polynomial as the graph polynomial times a factor independent of activities on edges incident to the root, enabling the influence comparison.Source: §6.1 · pp. 36–38

6.2. The Total Influence in a Tree: Proof of Theorem 6.4.

• On bounded-degree trees, total edge influence is bounded using marginal recursions, a logarithmic potential, and a gradient-norm estimate.Pairwise influences factor along the unique path between edges, while the analysis develops both one-step and two-step recursion bounds; the latter is useful when λΔ is sufficiently large.Source: §6.2 · pp. 39–40, §6.2.1 · p. 40

6.2.1. Proof of Proposition 6.9.

• The argument treats j as a child of i, with i a child of the root, and then applies induction to peel off two levels at a time.Source: §6.2.1 · p. 43

General framework

• Theorem 1.12 reduces optimal mixing to proving marginal boundedness and spectral independence for the Gibbs distribution.For up-to-∆-unique antiferromagnetic 2-spin systems with gap δ, spectral independence is O(1/δ)-bounded by, while marginal boundedness follows from worst-neighborhood analysis.Source: §7 · p. 43

Antiferromagnetic 2-spin systems

• For antiferromagnetic 2-spin systems, these properties yield the claimed O(n log(n/ε)) Glauber-dynamics mixing throughout the up-to-∆ uniqueness region.The mixing-time constant may depend on model parameters, but hard-core and Ising applications obtain parameter-independent constants by combining the theorem with Dobrushin uniqueness away from the threshold.Source: §7 · pp. 43–44

Hard-core and Ising models

• For the hard-core and Ising models, spectral independence and marginal boundedness combine with Dobrushin uniqueness to establish the respective mixing bounds across their parameter regimes.For antiferromagnetic Ising, the bounds are ∆^O(1/δ)n log(n/ε) or 2n log(n/ε); for ferromagnetic Ising, they are likewise ∆^O(1/δ)n log(n/ε) or 2n log(n/ε).Source: §7 · pp. 44–45

Random colorings

• For random colorings, spectral independence from and Ω(1/q)-marginal boundedness adapted from imply C′n log(n/ε) mixing under the stated color-degree condition.When q ≥ 3∆, Dobrushin uniqueness gives the intermediate bound 2n log(n/ε).Source: §7 · p. 45

Monomer-dimer model

• For monomer-dimer sampling, equivalence with the hard-core model on the line graph enables Theorem 1.12, using spectral independence and 2-hop marginal boundedness.Theorem 2.10 supplies spectral independence, while worst 2-hop-neighborhood analysis supplies marginal boundedness.Source: §7 · p. 45

General bounds

• Can the approximate tensorization and mixing-time bounds achieve polynomial rather than ∆^O(∆^2/δ) dependence for the hard-core model when λ ≤ (1−δ)λ_c(∆)?The target bound is poly(∆, 1/δ) n log n.Source: §8 · p. 45

Monomer-dimer model

• For the monomer-dimer model, improved spectral-independence bounds are needed because controlling the influence matrix’s ∞-norm may not yield a tight maximum-eigenvalue bound.The section notes that the total-influence bound is tight, while the corresponding maximum-eigenvalue bound is apparently not.Source: §8 · p. 46

Scope

• The appendix summarizes variance analogs of approximate tensorization, uniform block factorization, and local-to-global entropy contraction for spin systems and weighted simplicial complexes.Most main technical contributions extend to the variance setting; the simplicial-complex results were independently discovered by.Source: A. Factorization and Contraction of… · p. 50

Connection to Markov chains

• Variance is closely related to the spectral gap of the corresponding Markov chain, motivating variance-based formulations of the paper’s factorization results.The appendix introduces definitions and theorems obtained using the paper’s techniques.Source: A. Factorization and Contraction of… · p. 50

Definitions

• For a distribution µ on a finite set Ω, the variance of f is Var(f) = µ[(f − µ(f))^2] = µ(f^2) − µ(f)^2.The spectral gap is then defined for a reversible Markov chain P on Ω with stationary distribution µ.Source: A. Factorization and Contraction of… · p. 50

A.1. Spin Systems

• Variance admits approximate tensorization and uniform block factorization analogues of the corresponding entropy notions.The decomposition and product-measure tensorization results also hold for variance, as do the definitions of approximate tensorization and uniform block factorization.Source: §A.1 · p. 50
• Uniform block factorization of variance likewise corresponds to a spectral-gap bound for block dynamics that updates a random vertex subset each step.This identifies the variance block-factorization constant with the relevant block-dynamics relaxation guarantee.Source: §A.1 · p. 50
• Approximate tensorization of variance is equivalent to a Poincaré inequality, hence to a lower bound on the Glauber dynamics spectral gap.Fact A.3 states the equivalence between variance tensorization and λ(Pgl) ≥ 1/C1.Source: §A.1 · p. 50
• The paper’s main deduction from uniform block factorization to approximate tensorization, Lemma 2.3, remains valid for variance.This extends the entropy-based proof mechanism to variance without changing its role in the argument.Source: §A.1 · p. 50
• Spectrally independent distributions have optimal O(1) uniform block-factorization constants, which combined with Lemma A.4 and Fact A.3 gives an optimal Ω(1/n) Glauber spectral-gap bound.Lemma A.4 converts block factorization under the stated bounded-degree and marginal-boundedness conditions into approximate tensorization with constant O(C).Source: §A.1 · p. 51

Variance and spectral expansion

• Variance contraction is equivalent to the Poincaré inequality [50, Lemma 1.13], and global contraction is equivalent to the spectral gap of the corresponding down-up walk.The same relationship extends to the adjoint up-down walk.Source: §A.2 · p. 51

Local variance contraction

• Local variance contraction is equivalent to local spectral expansion, with parameters related by ζ_k = (1−α_k)/(1+α_k).Its definition is slightly stronger than the entropy analogue because it considers all local functions rather than only globally induced ones.Source: §A.2 · p. 51

Local-to-global variance contraction

• Theorem A.9 shows that local variance contraction on a pure weighted simplicial complex implies order-(r, s) global variance contraction and corresponding down-up and up-down walk spectral-gap bounds.The theorem is presented as the variance analogue of the earlier local-to-global entropy result.Source: §A.2 · pp. 51–52

Applications

• Theorem A.9 combined with and Theorem 2.10 yields uniform variance block factorization for linear-sized blocks with constant C = O(1).This links the local-to-global result to factorization of variance on large blocks.Source: §A.2 · p. 52

Comparison with spectral-expansion bounds

• For local spectral expanders, the resulting walk-gap bounds coincide in special cases such as ζ_k = 0, while [31] shows bound (A.1) is always no worse than (A.2).The comparison uses consistency of local variance contraction rates with the trickling-down theorem of [52].Source: §A.2 · p. 52