Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Abstract
For general antiferromagnetic -spin systems, including the hardcore model on weighted independent sets and the antiferromagnetic Ising model, there is an for the partition function on graphs of maximum degree when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no to estimate the partition function unless . The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant . For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex on other vertices, as opposed to the total influence of other vertices on , thereby extending their work to all 2-spin models and improving the mixing time.
More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the so-called tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz’s correlation decay approach and Barvinok’s polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for the correlation decay or polynomial interpolation approach immediately imply rapid mixing of the Glauber dynamics. Our proof utilizes that the graph partition function is a divisor of the partition function for Weitz’s self-avoiding walk tree. This fact leads to new tools for the analysis of the influence of vertices, and may be of independent interest for the study of complex zeros.
1 Introduction
A remarkable connection has been established between the computational complexity of approximate counting problems in general graphs of maximum degree and the statistical physics phase transition on infinite, regular trees of degree (or up to in the more general case). This connection holds for 2-state antiferromagnetic spin systems – the hardcore model on independent sets and the Ising model are the most interesting examples of such systems.
Given an -vertex graph , configurations of the 2-spin model are the assignments of spins to the vertices. A 2-spin system is defined by three parameters: edge weights and a vertex weight . Edge parameter controls the (relative) strength of interaction between neighboring -spins, corresponds to neighboring -spins, and is the external field applied to vertices with -spins.
Every spin configuration is assigned a weight
where, for spin , is the number of monochromatic edges with spin , and is the number of vertices with spin (as is standard, the parameters are normalized so we can avoid two additional parameters). The Gibbs distribution over spin configurations is given by where is the partition function.
There are two examples of particular interest: the hardcore model and the Ising model. When and then the only configurations with non-zero weight are independent sets of and the weight of an independent set is ; this example is known as the hardcore model where the parameter corresponds to the fugacity.
In the case then the important quantity is the total number of monochromatic edges and the weight of a configuration is ; this is the classical Ising model where the parameter corresponds to the inverse temperature and is the external field ( means no external field). Note, when then the model is ferromagnetic as neighboring vertices prefer to have the same spin, and is the antiferromagnetic Ising model. In the general -spin system, the model is ferromagnetic when and antiferromagnetic when . (When we get a trivial product distribution.)
The fundamental algorithmic tasks are to sample from the Gibbs distribution and to estimate the partition function. For the approximate sampling problem we are given a graph and an and our goal is to generate a sample from a distribution which is within total variation distance of the Gibbs distribution in time . An efficient approximate sampling algorithm implies an (fully-polynomial randomized approximation scheme) for the approximate counting problem [JVV86, ŠVV09]. Recall, given an -vertex graph , and , an outputs a -approximation of with probability in time , whereas an is the deterministic analog (i.e., ).
A standard approach to the approximate sampling problem is the Markov Chain Monte Carlo (MCMC) method; in fact there is a simple Markov chain known as the Glauber dynamics. The Glauber dynamics works as follows: from a configuration at time , choose a random vertex , we then set for all , and finally we choose from the conditional distribution of . For the case of the hardcore model, then is set to occupied (i.e., spin ) with probability if no neighbors are currently occupied, and otherwise it is set to unoccupied.
It is straightforward to verify that the Glauber dynamics is ergodic with the Gibbs distribution as the unique stationary distribution. The mixing time is the minimum number of steps to guarantee, from the worst initial state , that the distribution of is within total variation distance of the Gibbs distribution. The goal is to prove that the mixing time is polynomial in , in which case the chain is said to be rapidly mixing.
For the case of the ferromagnetic Ising model (with or without an external field), a classical result of Jerrum and Sinclair [JS93] gives an for all graphs via the MCMC method. This is the only case with an efficient algorithm for general graphs. For antiferromagnetic 2-spin models the picture is closely tied to statistical physics phase transitions on the regular tree.
The uniqueness/non-uniqueness phase transition is nicely illustrated for the case of the hardcore model. Consider the infinite -regular tree rooted at , and let denote the tree truncated at the first levels. This phase transition captures whether the configuration at the leaves of “influences” the root, in the limit . For the hardcore model we can consider even height trees (corresponding to the all even boundary condition) versus odd height trees. Let denote the marginal probability that the root is occupied in the Gibbs distribution . Let and . We say that tree uniqueness holds if and tree non-uniqueness holds if they are not equal. For all there exists a critical fugacity [Kel85], where tree uniqueness holds iff .
The remarkable connection is that an algorithmic phase transition for general graphs of maximum degree occurs at this same tree critical point. For all constant , all , all , all graphs of maximum degree , [Wei06] presented an for approximating the partition function. On the other side, for all , all , [Sly10, SS14, GŠV16] proved that, unless , there is no for estimating the partition function.
One important caveat is that the running time of Weitz’s algorithm is where the approximation factor is and the constant depends polynomially on the gap (recall, ). Weitz’s correlation decay algorithm was extended to the antiferromagnetic Ising model in the tree uniqueness region by Sinclair et al. [SST14], and to all antiferromagnetic 2-spin systems in the corresponding tree uniqueness region (as we detail below) by Li, Lu, and Yin [LLY13].
An intriguing new algorithmic approach was presented by Barvinok [Bar16] and refined by Patel and Regts [PR17], utilizing the absence of zeros of the partition function in the complex plane to efficiently approximate a suitable transformation of the logarithm of the partition function using Taylor approximation. This polynomial interpolation approach was shown to be efficient in the same tree uniqueness region as for Weitz’s result by Peters and Regts [PR19], although the exponent in the running time depends exponentially on .
It was long conjectured that the simple Glauber dynamics is rapidly mixing in the tree uniqueness region. This was recently proved by Anari, Liu, and Oveis Gharan [ALO20]; they proved, for all , the mixing time is whenever . We improve this result. First, we improve the mixing time from to as detailed in the following theorem.
Theorem 1 (Hardcore model).
Let be an integer and . For every -vertex graph of maximum degree and every , the mixing time of the Glauber dynamics for the hardcore model on with fugacity is .
This bound is optimal barring further improvements in the local-to-global arguments from [AL20]. Our improved result follows from a simpler, cleaner proof approach which enables us to extend our result to a wide variety of 2-spin models, matching the key results for the correlation decay algorithm with vastly improved running times.
Our proof approach unifies the three major algorithmic tools for approximate counting: correlation decay, polynomial interpolation, and MCMC. Most known results for both correlation decay and polynomial interpolation approach are proved by showing contraction of a suitably defined potential function on the so-called tree recursions; the tree recursions arise as a result of Weitz’s self-avoiding walk tree that we will describe in more detail later in this paper. A recent work of Shao and Sun [SS20] unifies these two approaches by showing that the contraction which is normally used to prove efficiency of the correlation decay algorithm, also implies (under some additional analytic conditions) that the polynomial interpolation approach is efficient.
Here we prove that this same contraction of a potential function also implies rapid mixing of the Glauber dynamics, with our improved running time that is independent of ; see 4 and 5 for a detailed statement. Our proof utilizes several new tools concerning Weitz’s self-avoiding walk tree, which are detailed in Section 3. In particular, we show that the partition function of a graph divides the partition function of Weitz’s self-avoiding walk tree; see 8. This result is potentially of independent interest for establishing absence of zeros for the partition function with complex parameters, as it enables one to consider the self-avoiding walk tree. This result also yields a new, useful equivalence for bounding the influence in a graph in terms of the self-avoiding tree, which strengthens the previously known connection by Weitz [Wei06]; see 8 for details.
As an easy consequence we obtain rapid mixing for the Glauber dynamics for the antiferromagnetic Ising model in the tree uniqueness region. In terms of the edge activity, the two critical points for the Ising model on the -regular tree are at and ; the first lies in the antiferromagnetic regime, while the second lies in the ferromagnetic regime. If , then uniqueness holds for all external field on the -regular tree.
As mentioned earlier, for the ferromagnetic Ising model, an was known for general graphs [JS93]. Furthermore, Mossel and Sly [MS13] proved mixing time of the Glauber dynamics for the ferromagnetic Ising model when . However, rapid mixing for the antiferromagnetic Ising model in the tree uniqueness region was not known.
We provide the following mixing result for the case . Note, when there is an additional uniqueness region for certain values of the external field ; this region is covered by 3.
Theorem 2 (Antiferromagnetic Ising Model).
Let be an integer and . Assume that and . Then for every -vertex graph of maximum degree , the mixing time of the Glauber dynamics for the Ising model on with edge weight and external field is .
Our results for the hardcore and Ising models fit within a larger framework of general antiferromagnetic 2-spin systems. Recall that the antiferromagnetic case is when .
For general 2-spin systems the appropriate tree phase transition is more complicated as there are models where the tree uniqueness threshold is not monotone in . Hence the appropriate notion is “up-to- uniqueness” as considered by [LLY13]. Roughly speaking, we say uniqueness with gap holds on the -regular tree if for every integer , all vertices at distance from the root have total “influence” on the marginal of the root. We say up-to- uniqueness with gap holds if uniqueness with gap holds on the -regular tree for all ; see Section 2 for the precise definition.
Both 1 and 2 are corollaries of the following general rapid mixing result which holds for general antiferromagnetic -spin systems in the entire tree uniqueness region.
Theorem 3 (General antiferromagnetic -spin system).
Let be an integer and . Let be reals such that , , and . Assume that the parameters are up-to- unique with gap . Then for every -vertex graph of maximum degree , the mixing time of the Glauber dynamics for the antiferromagnetic -spin system on with parameters is .
We also match existing correlation decay results [GL18, SS20] for ferromagnetic 2-spin models; see Section 8 for results, and Appendix F for proofs.
1.1 Mixing by the potential method
The tree recursion is very useful in the study of approximating counting. Consider a tree rooted at . Suppose that has children, denoted by . For we define to be the subtree of rooted at that contains all descendant of . Let denote the marginal ratio of the root, and for each subtree. The tree recursion is a formula that computes given , due to the independence of ’s. More specifically, we can write where is a multivariate function such that for ,
In this paper, however, we pay particular interest in the log of marginal ratios. The reason is that we will carefully study the pairwise influence matrix of the Gibbs distribution , introduced in [ALO20] and defined as for every
In [ALO20], the authors show that if the maximum eigenvalue of is bounded appropriately, then the Glauber dynamics is rapid mixing. One crucial observation we make in this paper is that the influence of on can be viewed as the derivative of with respect to the log external field at (see 12). Thus, it is more convenient for us to work with the log ratios. To this end, we rewrite the tree recursion as where is a function such that for ,
Observe that . Moreover, we define
for , so that for each .
To prove our main results, we use the potential method, which has been widely used to establish the decay of correlation. By choosing a suitable potential function for the log ratios, we show that the total influence from a given vertex decays exponentially with the distance, and thus establish rapid mixing of the Glauber dynamics. Let us first specify our requirements on the potential. For every integer , we define a bounded interval which contains all log ratios at a vertex of degree . More specifically, we let when , and when . Furthermore, define to be the interval containing all log ratios with degree less than .
Definition 4 (-Potential function).
Let be an integer. Let be reals such that , and . Let be a differentiable and increasing function with image and derivative . For any and , we say is an -potential function with respect to and if it satisfies the following conditions:
- 1.
- 2.
In the definition of -potential, one should think of as the log marginal ratio at a vertex and the potential function is of . The following theorem establishes rapid mixing of the Glauber dynamics given an -potential function.
Theorem 5.
Let be an integer. Let be reals such that , and . Suppose that there is an -potential with respect to and for some and . Then for every -vertex graph of maximum degree , the mixing time of the Glauber dynamics for the -spin system on with parameters is .
We outline our proofs in Section 3. Note that in both 4 and 5, the constant is allowed to depend on the maximum degree and parameters in general. For example, a straightforward black-box application of the potential in [LLY13] would give for the Boundedness condition, resulting in mixing. However, this is undesirable for graphs with potentially unbounded degrees. One of our contributions is that we show the Boundedness condition holds for a universal constant independent of and . Thus, our mixing time is with no parameters in the exponent except for .
In Section 7, we give a slightly more general definition of -potentials, which relaxes the Boundedness condition, and is necessary for our analysis of antiferromagnetic -spin systems with . 5 still holds for this larger class of potentials.
We remark that in all previous works of the potential method, results and proofs are always presented in terms of , the tree recursion of , and , a potential function of . In fact, our results can also be translated into the language of . To see this, since , it is straightforward to check that if we pick , and thereby . This implies that the Contraction condition in 4 holds for if and only if the corresponding contraction condition holds for . The Boundedness condition can also be stated equivalently for . Nevertheless, in this paper we choose to work with for the following two reasons. First, as mentioned earlier, the fact that is a derivative of makes it natural to consider the tree recursion for the log ratios. Indeed, it is easier and cleaner to present our results and proofs using directly rather than switching to . Second, the potential function we will use is obtained from the exact potential in [LLY13], by the transformation .111To be more precise, we also multiply a constant factor which only simplifies our calculation and does not matter much; also notice that [LLY13] denotes the potential function by and its derivative by . It is intriguing to notice that the derivative of this potential is simply . Then the Contraction condition has a nice form: ; and the Boundedness condition only involves an upper bound on . This seems to shed some light on the mysterious potential function from [LLY13], and also indicates that is a meaningful variant of the tree recursion to consider. To add one more evidence, for a lot of cases (e.g., ) where the potential is picked, that just means we can pick to be the identity function and itself is contracting without any nontrivial potential.
Revision in July 2021.
After the publication of this paper in FOCS 2020, a small error was found in [LLY13] regarding descriptions of the uniqueness region for antiferromagnetic 2-spin systems. The error was fixed in the latest version of [LLY13]. In this revision, we update corresponding results and proofs in Section 7 and Appendix E that rely on the changes in [LLY13]; in particular, 36 is adjusted in accordance with the current description of uniqueness regions. We remark that these changes are purely technical and do not affect the validity of our main results like 5.
Acknowledgments.
We would like to thank Shayan Oveis Gharan and Nima Anari for stimulating discussions. We also thank the anonymous referees for helpful comments and suggestions. We are grateful to Yitong Yin for communicating with us about the latest update of [LLY13] and for providing helpful instructions on modifying statements and proofs of results in Appendix E, particularly 36.
2 Preliminaries
Mixing time and spectral gap
Let be the transition matrix of an ergodic (i.e., irreducible and aperiodic) Markov chain on a finite state space with stationary distribution . Let denote the distribution of the chain after steps starting from . The mixing time of is defined as
We say is reversible if for all . If is reversible, then has only real eigenvalues which can be denoted by . The spectral gap of is defined to be and the absolute spectral gap of is defined as . If is also positive semidefinite with respect to the inner product , then all eigenvalues of are nonnegative and thus . Finally, the mixing time and the absolute spectral gap are related by
(1) |
Uniqueness
Let be an integer or . Let be reals such that , , and . For , define
and denote the unique fixed point of by . For , we say the parameters are up-to- unique with gap if for all .
Ratio and influence
Consider the -spin system on a graph . Let and . For all , we define the marginal ratio at to be
For all , we define the (pairwise) influence of on by
Write for the (pairwise) influence matrix whose entries are given by .
Weitz’s self-avoiding walk tree
Let be a connected graph and be a vertex of . The self-avoiding walk (SAW) tree is defined as follows. Suppose that there is a total ordering of the vertex set . A self-avoiding walk from is a path such that for all . The SAW tree is a tree rooted at , consisting of all self-avoiding walks with , and those appended with one more vertex that closes the cycle (i.e., for some such that ). Note that a vertex of might have many copies in the SAW tree, and the degrees of vertices are preserved except for leaves. See Fig. 1 for an example.
We can define a -spin system on with the same parameters , in which some of the leaves are fixed to a particular spin. More specifically, for a self-avoiding walk appended with , we fix to be spin if with respect to the total ordering on , and spin if . For each we denote the set of all free (unfixed) copies of in by . For and a partial configuration , we define the SAW tree with conditioning by assigning the spin to every copy of from and removing all descendants of , for each . Note that in general, different copies of from can receive different spin assignments. Finally, in the case that every vertex has a distinct field , all copies of from will have the same field in the SAW tree.
3 Proof outline for main results
Step 1 ([ALO20]): Spectral Independence implies rapid mixing.
Our proof builds on [ALO20] who showed that the Glauber dynamics for sampling from the hardcore distribution on graphs of maximum degree at most mixes in steps whenever . One of the key ingredients of their proof is a notion they call spectral independence. [ALO20] shows that the spectral independence property implies rapid mixing. Note that the diagonal entries of are , as opposed to in the original definition in [ALO20].
Definition 6 (Spectral Independence [ALO20]).
We say the Gibbs distribution on an -vertex graph is -spectrally independent, if for every , of size and , one has .
Theorem 7 ([ALO20]).
If is an -spectrally independent distribution, then the Glauber dynamics for sampling from has spectral gap at least
Our primary goal now is to bound the maximum eigenvalue of .
Step 2: Self-avoiding walk trees preserve influences.
From standard linear algebra, we know that the maximum eigenvalue of is upper bounded by both the -norm , which corresponds to total influences on a vertex , and the infinity-norm , corresponding to total influences of . In [ALO20] the authors use as an upper bound on . Roughly speaking, they show that the sum of absolute influences on a fixed vertex , is upper bounded by the maximum absolute influences on in the self-avoiding walk tree rooted at , over all boundary conditions. Here in this paper, we will use to upper bound instead. In fact, much more is true if we look at the influences from in the self-avoiding tree. We show that for every vertex , the influence in is preserved in the self-avoiding walk tree rooted at , in the form of sum of influences over all copies of .
The way we establish this fact is by viewing the partition function as a polynomial in . In fact, it will be useful to consider the more general case with an arbitrary external field for every . Let denote the fields. For and , the weight of conditional on is defined to be where is the number of - edges with at least one endpoint in for . Furthermore, is the partition function conditioned on . We shall view and as some fixed constants and think of as variables. In this sense, we regard the weights as monomials in and the partition function as a polynomial in . Moreover, the marginal ratios and the influences for are all functions in . Our main result is that the partition function of divides that of for each . From that, we show that the SAW tree preserves influences of the root, as well as re-establishing Weitz’s celebrated result [Wei06], see 13.
Lemma 8.
Let be a connected graph, be a vertex and such that is connected. Let be the self-avoiding walk tree of rooted at . Then for every , divides . More precisely, there exists a polynomial independent of such that
(2) |
As a corollary, for each vertex ,
(3) |
where is the set of all free (unfixed) copies of in .
Remark 1.
We emphasize that for the purposes of bounding the total influence of a vertex in , only Eq. 3 of 8 is needed, which can be proved in a purely combinatorial fashion. However, we believe the divisibility property Eq. 2 of the multivariate partition function of and its self-avoiding walk tree may be of independent interest.
We note that a univariate version of the divisibility statement Eq. 2 has already appeared in [Ben18] for the hardcore model and [LSS19] for the zero-field Ising model in the study of complex roots of the partition function. From 8, we can get for any fixed . That means, we only need to upper bound the sum of all influences for trees, in order to get an upper bound on .
Step 3: Decay of influences given a good potential.
The tree recursion provides us a great tool for computing the (log) ratios of vertices recursively for trees. As we show in 12, the influence is in fact a version of derivative of the log marginal ratio at . Thus, the tree recursion can be used naturally to relate these influences. We then apply the potential method, which has been widely used in literature to establish the decay of correlations (strong spatial mixing). The following lemma shows that the sum of absolute influences to distance has exponential decay with , which can be thought of as the decay of pairwise influences.
Lemma 9.
If there exists an -potential function with respect to and where and , then for every , and all integers ,
where denote the set of all free vertices at distance away from .
5 is then proved by combining 7, 8 and 9. We leave its proof to Appendix A.
Step 4: Find a good potential.
As our final step, we need to find an -potential function as defined in 4. The potential we choose is exactly the one from [LLY13], adapted to the log marginal ratios and the tree recursion (see Section 6 for more details). We show that if the parameters are up-to- unique with gap and either or , then is an -potential.
Lemma 10.
Let be an integer. Let be reals such that , , and . Assume that is up-to- unique with gap . Define the function implicitly by
(4) |
If , then is an -potential function with and . If and , then is an -potential with and ; we can further take if .
We deduce 3 for the case or from 5 and 10. The proof of it can be found in Appendix A. The case that and is trickier. As discussed in Section 5 of [LLY13], when and , for some the spin system lies in the uniqueness region for arbitrary graphs, even with unbounded degrees (i.e., up-to- unique). Thus, in this case the total influences of a vertex can be as large as , resulting in mixing time. To deal with this, we consider a suitably weighted sum of absolute influences of a fixed vertex, which also upper bounds the maximum eigenvalue of the influence matrix. 4 and 5 are then modified to a slightly stronger version. The statements and proofs for this case are presented in Section 7 and Appendix D.
The rest of the paper is organized as follows. In Section 4 we prove 8 about properties of the SAW tree. In Section 5 we establish 9 regarding the decay of influences by the potential method. We verify the Contraction condition in Section 6 for our choice of potential. Section 7 is devoted to the case that and , where a more general version of 4 and 5 is required; missing proofs can be found in Appendix D. In Appendix E we verify the Boundedness condition and its generalization for our potential in all cases. We consider ferromagnetic spin systems in Section 8 and the proofs are left to Appendix F. We prove all of our main results in Appendix A.
4 Preservation of influences for self-avoiding walk trees
In this section we show that the self-avoiding walk (SAW) tree, introduced in [Wei06] (see also [SS05]), maintains all the influence of the root, and thus establishes 8. To do this, we show that the partition function of , viewed as a polynomial of the external fields , divides that of the SAW tree. From there we prove that the influence of the root vertex on another vertex in , is exactly equal to that on all copies of in the SAW tree. Using our proof approach, we show that the marginal of the root is maintained in the SAW tree, re-establishing Weitz’s celebrated result [Wei06], and also all pairwise covariances concerned with are preserved.
Theorem 11.
Let be a connected graph, be a vertex and such that is connected. Let be the self-avoiding walk tree of rooted at . Then for every , divides . More precisely, there exists a polynomial such that
Moreover, the polynomial is independent of .
Remark 2.
We remark that [Ben18] proved a univariate version of 11 for the hardcore model, and [LSS19] showed a similar result for the zero-field Ising model with a uniform edge weight. Our result holds for all -spin systems and arbitrary fields for each vertex. We can also generalize it to arbitrary edge weights for each edge in a straightforward fashion. It is crucial that the quotient polynomial is independent of the field at the root, from which we can deduce the preservation of marginal and influences of the root immediately.
Before proving 11, we first give a few consequences of it. For all , we define the marginal at as (henceforth we write for the event for convenience), and the covariance of and as
The following lemma relates the quantities we are interested in with appropriate derivatives of the (log) partition function. Parts 1 and 2 of the lemma are folklore.
Lemma 12.
For every graph , and , the following holds:
-
1.
For all ,
-
2.
For all ,
-
3.
For all ,
Proof.
The first two parts are standard. We include the proofs of these two facts in Appendix B for completeness. For Part 3, we deduce from Part 2 that
It remains to show that
which actually holds for any two binary random variables. To see this, we first compute by definition:
Meanwhile, the covariance can be written as
This shows that and thus establishes Part 3. ∎
We deduce 8 from 11 and the second item of the following lemma. The proof of 11 is presented in Section 4.1.
Lemma 13.
Let be a connected graph, be a vertex and such that is connected. Let be the self-avoiding walk tree of rooted at . Then for every we have:
-
1.
([Wei06, Theorem 3.1]) Preservation of marginal of the root :
-
2.
Preservation of covariances and influences of : for every ,
where is the set of all free (unfixed) copies of in .
Proof.
By 11, there exists a polynomial such that and is independent of . Then it follows from 12 that
and therefore . For the second item, again from 12 we get
Recall that for the spin system on the SAW tree , every free copy of from has the same external field . Then, by the chain rule of derivatives and 12, we deduce that
Finally, we have
where the last equality follows as above. ∎
4.1 Proof of 11
Before presenting our proof, let us first review the notations and definitions introduced earlier. Denote the set of fields at all vertices by . For and , the weight of conditional on is given by
where for , denotes the number of edges such that both endpoints receive the spin and at least one of them is in . The partition function conditional on is defined as . For the SAW tree, we define the conditional weights and partition function in the same way. In particular, recall that when we fix a conditioning on the SAW tree, we also remove all descendants of for each .
For every and , we shall write to represent the set of configurations such that (i.e., ) and let be sum of weights of all configurations with . We further extend this notation and write for every and . For the SAW tree we adopt the same notations as well.
Proof of 11.
We will show that there exists a polynomial , independent of , such that
(5) |
The high-level proof idea of Eq. 5 is similar to the corresponding result in [Wei06, Theorem 3.1]. Let be the number of edges with at least one endpoint in . We use induction on . When the statement is trivial since . Assume that Eq. 5 holds for all graphs and all conditioning with less than edges. Suppose that the root has neighbors . Define to be the graph obtained by replacing the vertex with vertices and then connecting for .
Consider first the case where is still connected. For each , let . Define the -spin system on with the same parameters , plus an additional conditioning that the vertices are fixed to spin while are fixed to spin ; we denote this conditioning by with . Then, can be generated by the following recursive procedure. Also see Fig. 2 for an illustration.
Algorithm:
-
1.
For each , let plus the conditioning ;
-
2.
Let be the union of and by connecting for ; output .
For the purpose of proof, we also consider the -spin system on with the same parameters , with an exception that we let the vertices have no fields (i.e., setting for instead of ). We then observe that
and the same holds with spin replaced by . For , let denote the union of the conditioning and , where . Then for every we have
Notice that both sides are independent of the field : for the left side, all ’s do not have a field for the spin system on ; for the right side, recall that we do not count the weight of fixed vertices for the conditional partition function for each . Now define by
which is independent of . Then we get
Using a similar argument, we also have
Since we assume that is connected, the graph is also connected for each . Then, by the induction hypothesis, for each there exists a polynomial such that
these polynomials are independent of since the conditional partition functions for ’s do not involve . Now if we let
then it follows from the tree recursion that
The other equality is established in the same way. This completes the proof for the case that is connected.
If has two or more connected components, then we can construct by the SAW tree of each component. Recall that is defined by splitting the vertex into copies in the graph . Suppose that has connected component for an integer . Let be the subgraphs induced by each component, along with vertices from that are adjacent to it. For each , let be the graph obtained from by contracting all copies of into one vertex , and let . Observe that once we contract the roots of , the resulting tree is .
We define the -spin system on each with the same parameters , except that the vertex does not have a field (i.e., instead of ). For , let and be the configuration restricted on . Then is connected for every and, since , each with conditioning has fewer than edges. Thus, we can apply the induction hypothesis; namely, for there exists a polynomial , which is independent of , such that
We define the polynomial to be
It is then easy to check that
and similarly . The theorem then follows. ∎
5 Influence bound for trees
In this section, we study the influences of the root on other vertices in a tree. We give an upper bound on the total influences of the root on all vertices at a fixed distance away. To do this, we apply the potential method, which has been used to establish the correlation decay property (see, e.g., [LLY12, LLY13, GL18]). Given an arbitrary potential function , our upper bound is in terms of properties of , involving bounds on and where . We then deduce 9 in the case that an -potential.
Assume that is a tree rooted at of maximum degree at most . Let and be arbitrary and fixed. Consider the -spin system on with parameters , conditioned on . We need to bound the influence from the root to another vertex . Notice that if is disconnected from when is removed, then by the Markov property of spin systems. Therefore, we may assume that, by removing all such vertices, contains only leaves of .
For a vertex , let be the subtree of rooted at that contains all descendant of ; note that . We will write for the set of all free vertices at distance away from in . We pay particular interest in the marginal ratio at in the subtree , and write for simplicity. The ’s are related by the tree recursion . If a vertex has children, denoted by , then the tree recursion is given by
where for and ,
Also recall that for , we define
and for all .
The following lemma allows us to bound the sum of all influences from the root to distance , using an arbitrary potential function.
Lemma 14.
Let be a differentiable and increasing (potential) function with image and derivative . Denote the degree of the root by . Then for every integer ,
where
Before proving 14, we first present two useful properties of the influences on trees. Firstly, it was shown in [ALO20] that the influences satisfy the following form of chain rule on trees.
Lemma 15 ([ALO20, Lemma B.2]).
Suppose that are three distinct vertices such that is on the unique path from to . Then
Secondly, for two adjacent vertices on a tree, the influence from one to the other is given by the function .
Lemma 16.
Let and be a child of in the subtree . Then
Proof.
The lemma can be proved through an explicit computation of the influence. Here we present a more delicate proof utilizing 12, which gives some insights into the relation between the influence and the function . We assume that has children in the subtree , denoted by and respectively. We also assume, as a more general setting than uniform fields, that each vertex is attached to a field of its own. Then 12 and the tree recursion imply that
where the last equality is because for and . ∎
We are now ready to prove 14.
Proof of 14.
For a vertex , denote the number of its children by ; note that . Let be the children of the root . We may assume that all these children of are free, since if is fixed then by definition. Then by 15 and 16, we get
Hence, we obtain that
(6) |
Next, we show by induction that for every vertex and every integer we have
(7) |
Observe that once we establish Eq. 7, the lemma follows immediately by plugging Eq. 7 into Eq. 6. We will use induction on to prove Eq. 7. When , if is fixed then and there is nothing to show; otherwise, Eq. 7 becomes
which holds with equality since . Now suppose that Eq. 7 holds for some integer (and for every vertex ). Let be arbitrary and denote the children of by , where (if then and Eq. 7 holds trivially). Again by 15 and 16 we have
Using the induction hypothesis, we get
where the last inequality follows from that
This establishes Eq. 7, and thus completes the proof of the lemma. ∎
We then derive 9 as a corollary.
6 Verifying a good potential: Contraction
In this section, we make a first step for proving 10. Let be an integer. Let be reals such that , , and . Recall that define our potential function through its derivative by
(1) |
We include a short proof in Appendix C to show that is well-defined. If is up-to- unique with gap , then we show that satisfies the Contraction condition for . This holds for all parameters in the uniqueness region, without requiring that . Later in Appendix E, we establish the Boundedness condition for when , completing the proof of 10. The case of is more complicated and is left to Section 7.
Before giving our proof, we first point out that the potential function is essentially the same potential function used in [LLY13] (notice that [LLY13] uses as the notation of the potential function and for its derivative). Recall that the tree recursion for the marginal ratios is given by the function where such that for all ,
The potential function from [LLY13] is defined implicitly via its derivative as
The follows lemma explains how we obtain our potential from .
Lemma 17.
We have ; namely, for all .
Proof.
It is straightforward to check that
Therefore,
Combining the results of Lemmas 12, 13 and 14 from [LLY13], we get that the potential function satisfies the following gradient bound when is in the uniqueness region. Note that this can be regarded as the Contraction condition but for and .
Theorem 18 ([LLY13]).
Let be the image of . If the parameters are up-to- unique with gap , then for every integer such that and every ,
where .
Recall our definition from Section 1.1. The tree recursion, in terms of the log marginal ratios, is described by the function where such that for every ,
Observe that , since we move from ratios to log ratios. We are now ready to establish the Contraction condition for .
Lemma 19.
Let be the image of . If the parameters are up-to- unique with gap , then for every integer such that and every ,
where .
7 Remaining antiferromagnetic cases: and
In this section, we discuss the case where and . As studied in [LLY13], in this case the uniqueness region is more complicated. For example, there exists a critical such that the -spin system with is in the uniqueness region for arbitrary graphs; namely, is up-to- unique. To deal with large degrees, we need to relax the Boundedness condition in 4 and define a more general version of -potentials. We shall see that 5 still holds for this general -potential. The reason behind it is that in order to bound the maximum eigenvalue of the influence matrix, it suffices to consider a vertex-weighted sum of absolute influences of a vertex with large degree.
Remark 20.
We give more background on the uniqueness region in Section E.1. Note that in a recent revision of [LLY13], the authors updated the descriptions of the uniqueness region for the case and , fixing a small error in the previous version. Statements and proofs in this section and Appendix E of this paper are also adjusted accordingly based on the new version of [LLY13].
Recall that our goal is to bound the maximum eigenvalue of the matrix . We can do this by upper bounding the absolute row sum for fixed , thereby giving us a valid upper bound on . However, this approach does not work when and . In this case, the potential fails to be an -potential for a universal constant independent of . In fact, no such -potentials exist as the absolute row sum can be as large as . Especially, if the parameters are up-to- unique, which means the spin system has uniqueness for arbitrary graphs, then the absolute row sum can be where . We give a specific example where this is the case.
Example 21.
Consider the antiferromagnetic 2-spin system specified by parameters , and on the star graph centered at with leaves. A simple calculation reveals that for any leaf vertex . Hence, . Now, since , we have
forcing even when lies in the uniqueness region. However, we still have since .
To solve this issue, one might want to consider the absolute column sum, involving the sum of absolute influences on a fixed vertex. However, this will not allow us to use the beautiful connection between graphs and SAW trees as showed in 8. Instead, we consider here a vertex-weighted version of the absolute row sum of , which also upper bounds the maximum eigenvalue.
Lemma 22.
Let be a positive weight function of vertices. If there is a constant such that for every we have
(8) |
then .
Proof.
Let . Then the assumption is equivalent to . It follows that . ∎
We then modify our definition of -potentials from 4 which allows a weaker Boundedness condition. We remark that the only two differences between 23 and 4 is that: we allow ; and the Boundedness condition is relaxed to what we call General Boundedness. Recall that for every , we let when , and when .
Definition 23 (General -potential function).
Let be an integer or . Let be reals such that , and . Let be a differentiable and increasing function with image and derivative . For any and , we say is a general -potential function with respect to and if it satisfies the following conditions:
- 1.
- 2.
Notice that General Boundedness is a weaker condition than Boundedness. To see this, if a potential function satisfies Boundedness with parameter , then for every and every where we have
The following theorem generalizes 5 and shows that a general -potential function is sufficient to establish rapid mixing of the Glauber dynamics.
Theorem 24.
Let be an integer or . Let be reals such that , and . Suppose that there is a general -potential with respect to and for some and . Then for every -vertex graph of maximum degree , the mixing time of the Glauber dynamics for the -spin system on with parameters is .
We then give a counterpart of 10, showing that is a general -potential when and . 3 for this case is then obtained from 24 and 25.
Lemma 25.
Let be an integer. Let be reals such that and . Assume that is up-to- unique with gap . Then the function defined implicitly by Eq. 4 is a general -potential function with and ; we can further take if .
The proof of 24 can be found in Appendix D. For 25, the Contraction condition of follows from 19, and General Boundedness is proved in Appendix E together with all other cases.
8 Ferromagnetic cases
In the ferromagnetic case, the best known correlation decay results are given in [GL18, SS20]. Using the potential functions in [GL18] and [SS20], we show the following two results, which match the known correlation decay results. In fact, the potential function from [SS20] turns out to be an -potential function for constants and .
Theorem 26.
Fix an integer , positive real numbers and , and assume satisfies one of the following three conditions:
-
1.
, and is arbitrary;
-
2.
and ;
-
3.
and .
Then the identity function (based on the potential given in [SS20]) is an -potential function for and . Furthermore, for every -vertex graph of maximum degree at most , the mixing time of the Glauber dynamics for the 2-spin system on with parameters is , for a universal constant .
Remark 3.
Condition 1 includes both the ferromagnetic case and the antiferromagnetic case . Note that in both cases is up-to- unique with gap . For the antiferromagnetic case, the identity function is an -potential with and a better contraction rate , compared with the bound of the potential given by Eq. 4 in 10. For the ferromagnetic case with (Ising model), a stronger result by [MS13] was known, which gives mixing.
The potential function from [GL18] is indeed an -potential, but must, unfortunately, depend on . We have the following result, which is weaker than the correlation decay algorithm in [GL18] for unbounded degree graphs.
Theorem 27.
Fix an integer , and nonnegative real numbers satisfying , , and . Then for every -vertex graph with maximum degree at most , the mixing time of the Glauber dynamics for the ferromagnetic 2-spin system on with parameters is , for a constant depending only on , but not .
Proofs of these theorems are provided in Appendix F.
References
- [AL20] Vedat Levi Alev and Lap Chi Lau “Improved analysis of higher order random walks and applications” In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2020, pp. 1198–1211
- [ALO20] Nima Anari, Kuikui Liu and Shayan Oveis Gharan “Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model” In arXiv preprint arXiv:2001.00303, 2020
- [Bar16] Alexander Barvinok “Combinatorics and Complexity of Partition Functions” Springer AlgorithmsCombinatorics, 2016
- [Ben18] Ferenc Bencs “On trees with real-rooted independence polynomial” In Discrete Mathematics 341.12 Elsevier, 2018, pp. 3321–3330
- [GL18] Heng Guo and Pinyan Lu “Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems” In ACM Transactions on Computation Theory 10.4, 2018
- [GŠV16] Andreas Galanis, Daniel Štefankovič and Eric Vigoda “Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models” In Combinatorics, Probability and Computing 25.4 Cambridge University Press, 2016, pp. 500–559
- [JS93] Mark Jerrum and Alistair Sinclair “Polynomial-time approximation algorithms for the Ising model” In SIAM Journal on Computing 22.5 SIAM, 1993, pp. 1087–1116
- [JVV86] Mark R Jerrum, Leslie G Valiant and Vijay V Vazirani “Random generation of combinatorial structures from a uniform distribution” In Theoretical Computer Science 43 Elsevier, 1986, pp. 169–188
- [Kel85] F.. Kelly “Stochastic Models of Computer Communication Systems” In Journal of the Royal Statistical Society. Series B (Methodological) 47.3, 1985, pp. 379–395
- [LLY12] Liang Li, Pinyan Lu and Yitong Yin “Approximate Counting via Correlation Decay in Spin Systems” In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 922–940
- [LLY13] Liang Li, Pinyan Lu and Yitong Yin “Correlation Decay Up to Uniqueness in Spin Systems” In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013, pp. 67–84
- [LSS19] Jingcheng Liu, Alistair Sinclair and Piyush Srivastava “Fisher zeros and correlation decay in the Ising model” In Journal of Mathematical Physics 60.10 AIP Publishing LLC, 2019, pp. 103304
- [MS13] Elchanan Mossel and Allan Sly “Exact thresholds for Ising-Gibbs samplers on general graphs” In Annals of Probability 41.1, 2013, pp. 294–328
- [PR17] Viresh Patel and Guus Regts “Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials” In SIAM Journal on Computing 46, 2017, pp. 1893–1919
- [PR19] Han Peters and Guus Regts “On a conjecture of Sokal concerning roots of the independence polynomial” In The Michigan Mathematical Journal 68.1, 2019, pp. 33–55
- [Sly10] Allan Sly “Computational Transition at the Uniqueness Threshold” In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 287–296
- [SS05] Alexander D. Scott and Alan D. Sokal “The Repulsive Lattice Gas, the Independent-Set Polynomial, and the Lovász Local Lemma” In Journal of Statistical Physics 118.5, 2005, pp. 1151–1261
- [SS14] Allan Sly and Nike Sun “The Computational Hardness of Counting in Two-Spin Models on -Regular Graphs” In The Annals of Probability 42.6, 2014, pp. 2383–2416
- [SS20] Shuai Shao and Yuxin Sun “Contraction: A Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems” In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), 2020, pp. 96:1–15
- [SST14] Alistair Sinclair, Piyush Srivastava and Marc Thurley “Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs” In Journal of Statistical Physics 155.4, 2014, pp. 666–686
- [ŠVV09] Daniel Štefankovič, Santosh Vempala and Eric Vigoda “Adaptive simulated annealing: A near-optimal connection between sampling and counting” In Journal of the ACM 56.3, 2009, pp. 1–36
- [Wei06] Dror Weitz “Counting Independent Sets Up to the Tree Threshold” In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 140–149
Appendix A Proof of main results
Proof of 5.
Note that since the transition matrix for the Glauber dynamics has all nonnegative eigenvalues, we have that and so in order to deduce mixing, it suffices to lower bound . We do this by employing 7. It suffices to show -spectrally independence for sufficiently small .
To bound , it suffices to bound for all graphs with vertices and all boundary conditions on a subset of vertices. We claim the following:
(9) |
where is a constant depending only on . The first upper bound is deduced by
(8; ) | ||||
(split the sum by levels) | ||||
(9) | ||||
The second upper bound is more trivial. Intuitively, it means each absolute pairwise influence is at most some constant and hence the sum of absolute influences is upper bounded by . The following two claims, whose proofs are provided in Section A.2, give a more precise statement.
Claim 28 (Antiferromagnetic Case).
Fix an integer and real numbers , and assume , , and . Then for every -vertex graph of maximum degree at most , the antiferromagnetic -spin system on with parameters is -spectrally independent, for a constant depending only on . Furthermore, if is up-to- unique, then we can drop the dependence on .
Claim 29 (Ferromagnetic Case).
Fix an integer and positive real numbers , and assume and . Then for every -vertex graph of maximum degree at most , the ferromagnetic -spin system on with parameters is -spectrally independent, for a constant depending only on .
Proof of 3.
We leverage 5 and 24, which shows mixing as long as there is an -potential, or mixing if there is a general -potential. We use the potential given by Eq. 4, which is an adaptation of the potential function in [LLY13] to the log marginal ratios. When is up-to- unique with gap , it is an -potential or a general -potential by 10 and 25, with and a universal constant specified by the range of parameters. The theorem then follows. ∎
Proof of 1.
By 30 later in Section A.1, implies up-to- uniqueness with gap . Since , we can again appeal to 10 to obtain an -potential with and . 1 then follows by 5 with mixing. ∎
Proof of 2.
By 31 later in Section A.1, implies up-to- uniqueness with gap . Again, appealing to 10, we obtain an -potential with and . 2 then follows by 5 with mixing.
Though we technically get by using the [LLY13] potential, we can improve it to mixing by using the trivial identity function as the potential. See the first case of 26 (proved in Section F.1) and Remark 3. ∎
A.1 Uniqueness gaps in terms of parameter paps
In this section we state and prove 30 and 31, which relate the parameter gaps with the uniqueness gaps.
Claim 30 (Hardcore Model; Lemma C.1 from [ALO20]).
Fix an integer , , and . If , then is up-to- unique with gap .
Claim 31 (Large ).
Fix an integer , and . If , then is up-to- unique with gap for all . Note if , this is precisely the condition .
Proof.
Consider the univariate recursion for the marginal ratios with children . Differentiating, we have
At the unique fixed point , we have so
By 37, we have the upper bound
Since we assumed , we obtain
As this is at most for all , we have up-to- uniqueness with gap . ∎
A.2 Spectral independence bounds for constant-size graphs
In this section, we prove spectral independence bounds for graphs with fewer than -many vertices, since for graphs with such few vertices, our bounds based on contraction of the tree recursions become trivial.
Proof of 28.
If denotes the marginal ratio of a vertex , then . In the case , we have as well; if , we have . It follows that we immediately have the bounds
for all . Note that these constants are less than , and only depend on , yielding the first claim.
Now, we proceed to remove the dependence on when up-to- uniqueness holds. We have the following cases:
-
1.
If , we immediately obtain a bound of which is independent of .
-
2.
If and , then . Since is up-to- unique, we must have . It follows that .
-
3.
If and , then
- 4.
Proof of 29.
The proof is identical to the antiferromagnetic case and we omit it here. ∎
Appendix B Proof of 12 (Parts 1 and 2)
Proof of 12 (Parts 1 and 2).
To see the first equality, we compute directly and get
For Part 2, using the result above, we can also get
Appendix C A technical lemma for
The following lemma implies that the potential given by Eq. 4 is well-defined.
Lemma 32.
For all such that , we have
Proof.
For the side we have
Similarly, for the side we have
Appendix D Mixing by the potential method: Proof of 24
In this section, we prove 24 in the same way of 5, as outlined in Section 3. The major difference here is that we consider a weighted sum of absolute influences where is a weight function. This is sufficient for us to bound the eigenvalue of the influence matrix, as indicated by 22. We will choose the weight of a vertex to be , the degree of . The following lemma provides us an upper bound on the weighted sum of absolute influences to distance , given a general -potential. In particular, it generalizes 9.
Lemma 33.
If there exists a general -potential function with respect to and where and , then for every , and all integers ,
where denote the set of all free vertices at distance away from .
To prove 33, we first state the following generalization of 14 for any weight function . The proof of 34 is identical to 14 and we omit here.
Lemma 34.
Let be a differentiable and increasing (potential) function with image and derivative . Denote the degree of the root by . Then for every integer ,
where
Proof of 33.
Denote the degree of a vertex by , and the degree of in the subtree by . Pick the weights of vertices to be for all . Since is a general -potential, the Contraction condition implies that
Since by the definition of , the General Boundedness condition implies that for all and ,
Therefore, we get
The lemma then follows immediately from 34. ∎
Proof of 24.
The proof of 24 is almost identical to 5. We point out that the only difference here is that we consider the weighted sum of absolute influences of a given vertex. Since the SAW tree preserve degrees of vertices, we can still apply 8. Then, combining 7, 22, 8 and 33, we complete the proof of the theorem. ∎
Appendix E Verifying a good potential: Boundedness
In this subsection, we show the Boundedness or General Boundedness condition for our potential function defined by Eq. 4 in different ranges of parameters. Combining 19, we complete the proofs of 10 and 25.
In Section E.1 we give background on the uniqueness region of the parameters , based on the work of [LLY13]. We then show Boundedness and General Boundedness in Section E.2. Proofs of technical lemmas are left to Section E.3.
E.1 Preliminaries of the uniqueness region
In this section we give a brief description of the uniqueness region of parameters . All the results here, and also their proofs, can be found in Lemma 21 from the latest version of [LLY13].
Let be an integer and be reals. We assume that , , and . For define
and denote the unique fixed point of by . Recall that the parameters are up-to- unique with gap if for all .
When , the spin system is called a hard-constraint model. In this case, there exists a critical threshold for the external field defined as
such that the parameters are up-to- unique if and only if . In particular, when the critical field is given by
When , the spin system is called a soft-constraint model. If , then is up-to- unique for all . If the uniqueness region is more complicated which we now describe. Let
so that for every we have , and for every we have . For every , we define to be the two positive roots of the quadratic equation
More specifically, and are given by
where
Notice that for all . For we let
Then, the parameters are up-to- unique if and only if belongs to the following regime
(10) |
In particular, when there are two critical thresholds such that the parameters are up-to- unique if and only if or (i.e., ), where
The following bounds on the critical fields are helpful for our proofs later.
Lemma 35.
-
1.
If , then for every integer such that we have
-
2.
If and , then for every integer such that we have
where .
The proof of 35 is postponed to Section E.3.
E.2 Proofs of boundedness
In this section we complete the proofs of 10 and 25 by establishing Boundedness and General Boundedness in the corresponding range of parameters.
Let be an integer. Let be reals such that , , and . Recall that the potential function is defined by
(1) |
It is surprising to find out that , as the potential is exactly the one from [LLY13] as indicated by 17. This seems not to be a coincidence, and it provides some intuition why the potential from [LLY13] works. More importantly, the fact that is helpful in our proof of Boundedness and General Boundedness. Recall that for and we let to be the range of log marginal ratios of a vertex with children. Then for every and where , we have
(11) |
The following lemma gives upper bounds on , from which and Eq. 11 we deduce Boundedness and General Boundedness immediately. The brackets in the lemma indicate which lemma the bound is applied to.
Lemma 36.
Let be an integer. Let be reals such that , , and . Assume that the parameters are up-to- unique with gap . Then for all integers such that , and all reals where , the following holds:
- H.
- S.
The following lemma, whose proof can be found in Section E.3, is helpful.
Lemma 37.
For every we have
We present here the proof of 36.
Proof of 36.
We use notations and results from Section E.1.
H. Hard-constraint models: and .
H.1. .
H.2. .
Let and . Then we get
where the last inequality follows from the AM–GM inequality by
Since for , we have
If , then we deduce from 35 and that
It follows that
If , then it is easy to see that
S. Soft-constraint models: and .
S.1. .
For every we deduce from 37 that
S.2. and .
In this case, we have either or where are the two critical fields. Consider first . For every we deduce from 35 and that
where . Hence,
S.3. and .
Let , , , and . We first consider some trivial cases. If then it is easy to see that
If and , then we deduce from 37 that
Hence, in the following we may assume that and .
Since the parameters are up-to- unique, we have where the regime is given by Eq. 10. Observe that
where the last interval is nonempty only when . This means that is contained in at least one of the three intervals. We establish the bound by considering these three cases separately.
Case 1: . By the Cauchy-Schwarz inequality, we have
(12) |
Therefore, we get
Since for and , we deduce from 35 that
where . It follows that
E.3 Proofs of technical lemmas
Proof of 35.
1. For every we have
where the last inequality follows from that for all integer .
2. For every we have
Observe that the function is monotone increasing in when , and thus we deduce that
Therefore,
where the last inequality follows from that for all integer .
The second part can be proved similarly. For every we have
and hence,
We then conclude that
where the last inequality again follows from that for all integer . ∎
Proof of 37.
We deduce from the AM–GM inequality that
Appendix F Proofs for ferromagnetic cases
F.1 Proof of 26
Proof of 26.
Throughout, we use the “trivial potential” function . Note that then, is a constant function. Now, we prove Contraction and Boundedness. We split into the three cases.
-
1.
We first prove the Contraction part. By 37, for all we have
Now let us prove the Boundedness condition. From the above inequality we have
for .
-
2.
For the Contraction part, since , we have
Since we assumed , it follows that we have the upper bound
Now, we prove the Boundedness condition. Note that since , it follows that . A simple calculation reveals that and so by 37, we have
-
3.
For the Contraction part, since , we have
Since we assumed , it follows that we have the upper bound
which is again is upper bounded by as we calculated in case 2 above.
Now, we prove the Boundedness condition. Note that since , it follows that . A simple calculation reveals that and so by 37, we have
F.2 Proof of 27
In this subsection, we use results from [GL18] to prove 27. Their potential function is implicitly defined by its derivative for the marginal ratios as
for a constant depending only on (see [GL18] for a precise definition). In our context, the corresponding potential for the log ratios is
and is bounded by constants depending on for .
One of the main technical results in [GL18] is showing that the tree recursion is contracting with the potential function , and the derivative is bounded in the sense that there exist positive constants depending only on such that for all . [GL18] refer to such a function as a universal potential function.
In our context, we get that is an -potential function which satisfies 4, but with a constant that depends on . Indeed, worst case, we have
More precisely, we have the following result from [GL18], stated in terms of the log marginal ratios.
Theorem 38.
Assume are nonnegative real numbers satisfying , , and . Then the function is an -potential function for a constant depending on , and a constant depending on .
Combined with 5, this gives mixing with a constant depending only on . We note this is weaker than the correlation decay result in [GL18], since there, does not depend on , and hence is efficient for arbitrary graphs.
Appendix G Slightly faster mixing
In this section, we slightly optimize our mixing time results for certain antiferromagnetic 2-spin systems by more carefully taking into account the tradeoff between the (nontrivial) spectral independence bound we prove based on contraction, and the (trivial) spectral independence bound we obtained in Section A.2 for handling constant-sized graphs.
Proposition 39.
Suppose a distribution on subsets of is -spectrally independent for , for some and . Then the Glauber dynamics for sampling from has spectral gap at least
Proof.
Suppose we have already conditioned on -fraction of elements to be “in/out. The resulting distribution is both -spectrally independent and -spectrally independent. The exact threshold for which the bound is better than is given by
We note such a only makes sense when , or equivalently, . Now, we apply the -spectral independence bound for all conditional distributions based on fixing at most -fraction of vertices. We apply the -spectral independence otherwise. We obtain a final spectral gap lower bound of
Observe that
We also have
Putting these together, we obtain the desired lower bound. ∎
With this result, we can apply it to the antiferromagnetic models with and , since looking in the proof of 28, we have such systems are -spectrally independent roughly with .
Corollary 40 (Soft Constraints).
Fix integers , . Let be nonnegative real numbers satisfying and . Assume further that is up-to- unique with gap . Then for every -vertex graph with maximum degree at most , the Glauber dynamics for sampling from the antiferromagnetic 2-spin system with parameters mixes in steps.
Corollary 41 (Hard Constraints).
Fix an integer , fix , and let be up-to- unique with gap . Then for every -vertex graph with maximum degree at most , the Glauber dynamics for sampling from the antiferromagnetic 2-spin system with parameters -mixes in steps.