Correlation Decay up to Uniqueness in Spin Systems
Abstract
We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to , where can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most when the uniqueness condition is satisfied on infinite regular trees of degree up to . In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs.
Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the very recent hardness results of Sly-Sun and independently of Galanis-S̆tefankovic̆-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.
1 Introduction
Spin systems are well studied in the areas of Statistical Physics, Applied Probability and Computer Science as a general framework to capture the essence of how local interactions and constrains affect the macroscopic properties of particle systems. A system is usually described by a graph, with each vertex in one of a fixed number of states called spins, and edges specifying the neighborhood relation of the system.
Let be a graph and be the number of spin states. A configuration of the system is one of the possible assignments . Each configuration has an energy as a sum over all edges and vertices, such that the contribution of an edge is determined by a symmetric function of the spin states and , and the contribution of a vertex is determined by a function of its spin state . The weight of a configuration is , where is the temperature. We focus on the two-state spin systems. Up to normalization, a two-state spin system is fully captured by three parameters , where and determine the symmetric function for edge contribution and , also known as the external field, determines the function for vertex contribution. The Gibbs measure is a natural probability distribution over all configurations such that the probability of a configuration is , where the normalizing factor is called the partition function. The partition function encodes rich information regarding the macroscopic behavior of the spin system. However, for almost all nontrivial settings it is #P-hard to compute the precise value of partition functions.
One of the most important properties of spin systems is the correlation decay, which says that the correlation between the marginal Gibbs distributions of two vertices decays rapidly with respect to the distance between the two vertices. This property is also called weak spatial mixing [26]. Of greater algorithmic significance is the strong spatial mixing, which says that the correlations decay in the presence of arbitrary fixed spins at other vertices. For two-state spin systems, the strong spatial mixing may imply efficient approximation algorithms for the partition function. It is then an important question to characterize the systems which exhibit strong spatial mixing on arbitrary instances of graphs by the parameters of the systems.
A two-state spin system is ferromagnetic if adjacent vertices favor agreement of spins, and is anti-ferromagnetic if otherwise. For all two-state ferromagnetic spin systems, the partition functions can be efficiently approximated [12, 10]. In the anti-ferromagnetic region, the correlation decay plays a central role in the approximability of partition functions. It is believed (see [19]) that for such models the approximability of the partition function is characterized by the uniqueness of Gibbs measure on infinite regular trees, which is equivalent to the weak spatial mixing on the infinite regular trees. This condition is called the uniqueness condition.
In a seminal work [26], Weitz shows that for the hardcore model strong spatial mixing is characterized by the uniqueness condition, and in a recent work of Sinclair, Srivastava, and Thurley [21] the same characterization is proved for the anti-ferromagnetic Ising model. Both models are important special two-state anti-ferromagnetic spin systems. On the hardness side, it is proved for the hardcore model by Sly [23] and Galanis et al. [6], and very recently for the general two-state anti-ferromagnetic spin systems by Sly and Sun [24] and independently by Galanis, S̆tefankovic̆, and Vigoda [7] that violating the uniqueness condition implies the inapproximability of partition functions. Two questions remain open for our complete understanding of the correlation decay and computation in two-state spin systems: the characterizations of the strong spatial mixing and approximability of general two-state spin systems.
1.1 Our results
We characterize the two-state anti-ferromagnetic spin systems which exhibit strong spatial mixing on general degree-bounded graphs or arbitrary graphs by the uniqueness of Gibbs measure on infinite regular trees.
Theorem 1.
For any finite or , a two-state anti-ferromagnetic spin system is of strong spatial mixing on graphs of maximum degree at most if and only if the system exhibits uniqueness on infinite -regular trees for all .
Due to Weitz’s self-avoiding walk tree construction [26], the strong spatial mixing of a two-state spin system on degree-bounded graphs immediately implies an FPTAS for the partition function. Indeed, we show an even stronger notion of correlation decay introduced in a previous work [15], namely the computationally efficient correlation decay, which gives FPTAS not only for the degree-bounded graphs but also for arbitrary graphs with unbounded degrees, when the corresponding uniqueness condition is satisfied.
Theorem 2.
For any finite or , there exists an FPTAS for the partition function of the two-state anti-ferromagnetic spin system on graphs of maximum degree at most if for all the system parameters lie in the interior of the uniqueness region of infinite -regular tree.
In the above two theorems, the case represents the graphs of unbounded degree.
Due to a very recent hardness results of Sly and Sun [24] for general two-state spin systems and an independent result of Galanis, S̆tefankovic̆ and Vigoda [7] for a less general setting, violating the uniqueness condition implies inapproximability of the partition function.
Theorem 3 (Due to [24] and [7]).
For any finite or , unless there does not exist an FPRAS for the partition function of the two-state anti-ferromagnetic spin system on graphs of maximum degree at most if for some the system parameters lie in the interior of the non-uniqueness region of infinite -regular tree.
The original theorem in [24] holds for -regular graphs with fixed , which immediately implies the hardness for degree-bounded graphs or arbitrary graphs. And the hardness condition in both [24] and [7] requires the non-uniqueness on a -regular tree with . But the uniqueness on the infinite 2-regular tree (i.e. the infinite path) always holds for any two-state anti-ferromagnetic spin system, thus the condition in Theorem 3 suffices.
For graphs of maximum degree 2 or less, the partition function can be computed exactly in polynomial time. Thus Theorem 2 and Theorem 3 together with the FPRAS for two-state ferromagnetic spin system [12, 10] give an almost complete (except at the phase transition boundary) classification of the approximability of the partition function of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.
1.1.1 Regularity and monotonicity
In Statistical Physics, the correlation decay is usually studied on regular graphs or even structurally symmetric graphs (e.g. Bethe lattice). Although for hardness results considering only regular graphs will strengthen the lower bounds, from algorithmic perspective it is more general to consider spin systems on general graphs. The approximation algorithms in [26] for the hardcore model and [21] for the anti-ferromagnetic Ising model are both for general graphs with bounded maximum degrees. As discussed in [21, 24], up to translation of parameters the hardcore and Ising models together are complete for general two-state spin systems on -regular graphs with fixed . However, this does not cover the most general case, namely the general two-state spin system on general graphs, of either bounded or unbounded degree. A fundamental reason for this gap is the non-monotonicity of general spin systems.
The well studied hardcore and anti-ferromagnetic Ising models (along with all two-state spin systems with ) are both monotone spin systems, in the sense that the uniqueness on infinite -regular tree implies the uniqueness on all infinite regular trees with smaller degrees. This monotonicity does not necessarily hold in general two-state spin systems.
In [26], Weitz established the following implication in the hardcore model:
Claim (Theorem 2.3 in [26]).
Strong spatial mixing on a -regular tree implies the strong spatial mixing on all graphs of maximum degree at most .
In [26], Weitz also remarked without proof that this implication holds for all two-state spin systems (indeed this is rigorously proved for anti-ferromagnetic Ising model in [21]). With this to be true, devising approximation algorithms for two-state spin systems on degree-bounded graphs is reduced to verifying the strong spatial mixing on -regular trees. This has been accepted as a fact about the two-state spin systems and has become a building block for approximation algorithms for such systems (see Theorem 2.8 in [21] and the discussions in [22, 23]). It was also raised as a conjecture in [22] whether the claim holds for general multi-state spin systems.
As a byproduct of our analysis (see Section 5), we find that this well-believed implication between the strong spatial mixing on -regular tree and on graphs of maximum degree at most holds only for monotone spin systems (including the hardcore and anti-ferromagnetic Ising models). For general two-state spin systems the worst case for uniqueness as well as strong spatial mixing among all degree-bounded graphs is indeed a regular tree, but may no longer be the one of the highest degree. A bright side of this complication is that higher degrees may yield much faster correlation decay, making possible the FPTAS for graphs with unbounded degrees.
These new phenomena suggest that the general two-state spin systems have much richer structure than the well-studied monotone spin systems such as the hardcore and anti-ferromagnetic Ising models. The former approach via the strong spatial mixing on -regular tree which succeeds in monotone spin systems on general graphs and general spin systems on regular graphs, meets a barrier when dealing with general spin systems on general graphs. We give a unified approach to the correlation decay in general two-state spin systems, through the strong spatial mixing on arbitrary trees instead of -regular trees. This approach was initiated in our previous work [15] dealing with graphs of unbounded degrees. In this paper, we devise a unified potential-based analysis which adapts to both the irregularity of the arbitrary tree and the non-monotonicity of general two-state spin system and give tight correlation decay results for all two-state anti-ferromagnetic spin systems on degree-bounded families of graphs and family of all graphs.
1.1.2 Implications of the main results
By solving the uniqueness condition we can restate our main results in various threshold forms. Theorem 2 covers as special cases all previous algorithmic results for two-state anti-ferromagnetic spin systems on general-structure graphs as well as clears up previously uncovered cases.
In terms of interactions.
We can fix the external field and discuss the tractable region of . Since the roles of and are symmetric, we can further fix one of them and discuss the tractable range of the other. This formulation was used in [10, 15].
Our main result can be restated as follows: for any , there is a critical threshold for the uniqueness on infinite regular trees up to degree such that if there is an FPTAS for graphs of maximum degree at most ; and in particular, is an absolute constant such that if there is an FPTAS for arbitrary graphs.
This covers as special cases all algorithmic results in [10] regarding the anti-ferromagnetic systems and all results in [15], extends the tractable regions in these previous works, and considers the degree-bounded graphs as well.
In terms of external field.
Motivated by the studies of hardcore and anti-ferromagnetic Ising models, we can fix and discuss the tractable range of external field.
Due to the symmetric role of and , we may assume that . Our main results can be restated in specific settings as follows:
-
•
Hard constraints (when ): For any , is a critical threshold for the uniqueness on infinite regular trees up to degree such that if there exists an FPTAS for graphs of maximum degree at most .
For , the critical threshold equals . There is no external field satisfying uniqueness on infinite regular trees of unbounded degrees. This is consistent with the hardness result for the hardcore model without degree bound [4, 23]. One particularly interesting case is when , in which case the model is the hardcore model with fugacity , and is the critical threshold. This covers the result of [26].
For , in addition to the results for degree-bounded graphs, there exists an absolute positive constant which lower bounds for all , such that if there exists an FPTAS for arbitrary graphs.
-
•
Soft constraints (when ): If the uniqueness condition holds for any external field and there always exists an FPTAS for graphs of maximum degree at most .
Now suppose . Let be the smallest satisfying . For every integer , there exist two thresholds and for the uniqueness on the infinite -regular tree, such that if or for all integers , there is an FPTAS for graphs of maximum degree at most .
Furthermore, if , the above uniqueness condition can be simplified as that or , where and . In particular, for , the anti-ferromagnetic Ising model, we have , and the uniqueness holds when . This covers the result of anti-ferro-Ising model in [21].
For unbounded maximum degree , if , there is no satisfying the uniqueness on infinite regular trees of all degrees, which is consistent with the hardness results in [10]; and if , the uniqueness for all infinite regular trees holds when or for all , under which condition there exists an FPTAS for arbitrary graphs.
1.2 Related works
The approximation of partition functions of spin systems has been extensively studied[12, 13, 9, 3, 11, 25, 4, 5, 17]. In a seminal work [12], Jerrum and Sinclair devised a fully polynomial-time randomized approximation scheme (FPRAS) for the ferromagnetic Ising model. Later in [10], the FPRAS was extended to all two-state ferromagnetic spin systems by translating the parameters to the ferromagnetic Ising model. Also in [10], Goldberg, Jerrum, and Paterson gave an FPRAS and inapproximability results for two-state anti-ferromagnetic spin systems on arbitrary graphs. A gadget based on random regular bipartite graphs was proposed by Dyer, Frieze, and Jerrum in [4] and was also analyzed by Mossel, Weitz, and Wormald in [19] to study the inapproximability on degree-bounded graphs. It is widely believed that the transition of approximability of anti-ferromagnetic spin systems is captured by the phase transition of uniqueness on infinite trees. This was raised openly as a conjecture in [19]. The conjecture was proved by Sly in [23] for the hardcore model. This result was improved by Galanis et al. in [6] to a wide range of parameters. Very recently, Sly and Sun [24] proved the hardness of all two-state anti-ferromagnetic spin systems of non-uniqueness on infinite regular trees. A same result for anti-ferromagnetic Ising model without external field was independently proved by Galanis, S̆tefankovic̆, and Vigoda in [7].
The correlation decay technique developed independently by Weitz [26] and Bandyopadhyay and Gamarnik [1] is a powerful tool for devising deterministic fully polynomial-time approximation schemes (FPTAS) for partition functions (other important examples include [8, 2]). In [26], Weitz introduced the concept of strong spatial mixing and used it to devise FPTAS for the hardcore model up to the uniqueness threshold. The other most important two-state anti-ferromagnetic spin system, the anti-ferromagnetic Ising model, was studied recently by Sinclair, Srivastava, and Thurley in [21], where a more powerful message-decay method was introduced to analyze the strong spatial mixing and give FPTAS up to uniqueness threshold. A powerful technique was developed by Restrepo et al. in [20] which makes use of the specific structure of graphs for strong spatial mixing. A broader tractable region than the region of uniqueness is achieved on grid lattice by exploiting the structure of the graph. In a previous work [15], we gave an FPTAS for two-state anti-ferromagnetic spin systems without external field on arbitrary graphs with unbounded degrees, up to a continuous relaxation of the uniqueness threshold. The approach used in the current paper was initiated in [15], however the analysis in [15] cannot separate the uniqueness up to certain degree, thus fails in dealing with degree-bounded families of graphs.
2 Definitions and preliminaries
A two-state spin system is described by a graph . A configuration of the system is one of the possible assignments of states to vertices. We also use two colors blue and green to denote these two states. The weight of a configuration can be described as a product of contributions of individual edges and vertices. Let and . The weight of a configuration is given by
The Gibbs measure is a probability distribution over all configurations defined by . The normalization factor is called the partition function.
We can normalize the contributions of a edge and of a green vertex to be 1. So that for some , and for some . Since the roles of blue and green are symmetric, we can assume that without loss of generality. The three parameters with and completely specify a two-state spin system. A two-state spin system with is an Ising model and a two-state spin system with or symmetrically is a hardcore model.
A two-state spin system is called anti-ferromagnetic if adjacent vertices favor disagreeing spins, i.e. if . Without loss of generality, we focus on the cases that .
Definition 4.
is anti-ferromagnetic if , , , and .
By the symmetry of and and the triviality of the case , this definition is complete for all nontrivial two-state anti-ferromagnetic systems
2.1 Correlation decay
The Gibbs measure defines a marginal distribution of state for each vertex. Let denote the probability of vertex to be colored blue. Let be a configuration of . We call vertices fixed vertices, and free vertices. We use to denote the marginal probability of to be colored blue conditioning on the configuration of being fixed as .
Definition 5.
A spin system on a family of graphs is said to be of strong spatial mixing if for any graph in the family, any and ,
where is the subset on which and differ, and is the shortest distance from to any vertex in .
The weak spatial mixing can be defined by measuring the decay with respect to instead of . The spatial mixing property is also called correlation decay in Statistical Physics.
Let be a tree rooted by . Define to be the ratio between the probabilities that the root is blue and green, when imposing the condition (with the convention that when ). Suppose that has children and is the subtree rooted by the -th child. Due to the independence of subtrees, we have an easy recursion for calculating :
(1) |
Let be a graph. Similarly define that . In contrast to the case of tree, there is no easy recursion for calculating for a general graph because of the dependencies caused by cycles. In [26], a construction called the self-avoiding walk (SAW) tree was introduced which reduces the computing of marginal distribution in a general graph to that in a tree. Specifically, given a graph and a vertex . The SAW tree is a tree rooted at with a new vertex set (which effectively enumerates all paths originating from in and may include fixed leaves). Moreover, any vertex sets are mapped to respective and any configuration is mapped to a . We abuse the notation and write and if no ambiguity is caused. Given a graph , and , let be the shortest distance in from to any vertex in .
Theorem 6 (Theorem 3.1 of Weitz [26]).
Let be a graph, , a configuration on , and . Let . It holds that the maximum degree of equals the maximum degree of , , and . Moreover, any neighborhood of in can be constructed in time proportional to the size of the neighborhood.
2.2 The uniqueness condition
We consider the uniqueness of Gibbs measure on the infinite -regular trees , in which the recursion is given by due to the symmetric structure of .
Let be the positive fixed point of , that is, . It is known [14, 18] that the two-state anti-ferromagnetic spin system on undergoes a phase transition at with uniqueness when . This motivates the following definition.
Definition 7.
Let be anti-ferromagnetic. Let be the positive fixed point of function . We say that is up-to- unique, if for all integers ,
In particular, is universally unique if it is up-to- unique.
Being up-to- unique is equivalent to that the system is of weak spatial mixing on infinite regular trees up to degree . The uniqueness condition can be described in various threshold forms, which are given in Appendix A.
The uniqueness is defined by requiring that . The following lemma states that is bounded by an absolute constant as long as the uniqueness condition holds.
Lemma 8.
Let be anti-ferromagnetic. If is up-to- unique then there exists an absolute constant which depends only on , , and , such that for all .
Proof.
3 The strong spatial mixing on general graphs
In this section we prove Theorem 1. The necessity of the uniqueness condition is trivial since strong spatial mixing on general graphs implies weak spatial mixing on regular trees. It then remains to prove the following theorem.
Theorem 9.
Let be anti-ferromagnetic. For any finite or , if is up-to- unique, then the two-state spin system of parameters is of strong spatial mixing on graphs of maximum degree at most .
Our approach is to prove the strong spatial mixing on arbitrary trees of maximum degree at most , which by the self-avoiding walk tree construction implies the theorem. Note that unlike in [26] and [21], we analyze the decay on arbitrary tree instead of regular tree. This is because for general two-state anti-ferromagnetic spin systems the worst case for strong spatial mixing among all graphs of maximum degree at most may no longer be the -regular tree. We will explain this in detail in Section 5.
Given any graph of maximum degree at most , any configuration on and any , fixing an arbitrary vertex , by Theorem 6, a self-avoiding walk tree can be constructed such that the maximum degree of is bounded by , and . Recall that thus . For any and ,
This motivates the following definition.
Definition 10.
Let be a tree rooted by vertex , be a configuration on and be a vertex set. Define and as that for all which differ from only on .
It is then sufficient to prove Theorem 9 by constructing such and for and showing that .
Let be a tree rooted by , who has children , and be the subtree rooted by . It holds that
The lower and upper bounds and can be recursively constructed as follows. The base cases are: (1) , in which case and ; and (2) , i.e. is fixed to be the same color in all , in which case and (or ) if is fixed to be blue (or green). For , since is monotonically decreasing for anti-ferromagnetic ,
where and are the corresponding lower and upper bounds for , . In particular, when the empty product equals 1 by convention, thus , which is consistent with the case that is a free vertex having no children.
By the monotonicity of , it is easy to check that the and constructed above satisfy the requirement of Definition 10. Our goal is to show that decays exponentially in depth of recursion when the uniqueness holds. A straightforward approach is trying to prove that contracts at a constant rate in each recursion step. But this does not have to be true to guarantee the exponential decay. Indeed there are cases that the error does not decay in single steps but decay in a long run. To overcome this, we use a potential to amortize the contraction and show that contracts at a constant rate. We choose the potential function to be
We are analyzing the decay on an arbitrary tree with irregular degrees. In order to adapt this irregularity, the potential function cannot have as an input, but only caries the information regarding the distribution at the current vertex, yet it has to be able to provide correct compensation to the step-wise decay at any state of and for all spin systems satisfying sufficient uniqueness. A heuristic procedure which leads us to this good potential function is discussed in Appendix C.
Let be a monotone function satisfying that . We define that
and accordingly, , .
We define a function as follows:
The following lemma is obtained from applying the Mean Value Theorem. Similar routines were previously used in [15, 20]. The proof of the lemma is in Appendix B.
Lemma 11.
The followings hold for .
-
1.
(relation to ) for some .
-
2.
(absolute bound) Assuming that or the maximum degree of is bounded by a constant, if then and if for all then .
-
3.
(stepwise contraction) There exist , , such that
To prove the strong spatial mixing, we first relate to by Item 1 of Lemma 11, and then apply induction on the depth in , with Item 2 of Lemma 11 as basis and Item 3 of Lemma 11 as induction step. We then need to bound the contraction rate . Note that for , thus it holds unconditionally for all , , that
(2) | ||||
(3) |
With the uniqueness, the following much tighter contraction bound can be proved.
Lemma 12.
Let be anti-ferromagnetic. If is up-to- unique, then there exists a constant such that for any integer and any , , it holds that .
This lemma is the technical core of our analysis. It crucially relies on the choice of potential function. Before delving into the formal proof of Lemma 12, we note that Theorem 9 can be implied by this lemma.
Proof of Theorem 9.
Let for a whose maximum degree is at most . Then the maximum degree of is at most , thus the root has at most children in , and every other vertex in has less than children. We recursively construct , and for every subtree in .
Let . By repeatedly applying Item 3 of Lemma 11, without loss of generality, we have a path in with such that for , where is the number of children of and , .
Note that , and for all other . Assume that is up-to- unique. If is bounded, then by Lemma 12 there exists a constant , such that for , and due to (2); and if , then by Lemma 12, for all . In both cases we have .
Due to Item 1 of Lemma 11, for some . We then bound and . Due to Item 2 of Lemma 21, the fact that is up-to- unique implies that either is bounded or . Note that must be free or the theorem is trivial to prove, and none of ’s children is in because . Thus by Item 2 of Lemma 11, and , which implies that .
In conclusion, if is up-to- unique, there exists a constant , such that . As discussed in the beginning of this section, this proves Theorem 9.
Proof of Lemma 12.
The rest of this section is devoted to the proof of Lemma 12. Given that is up-to- unique, there exists an absolute constant such that for any and .
We define the symmetric version of :
The following lemma shows that the symmetric case dominates the maximum of by using the inequalities of Cauchy-Schwarz and arithmetic and geometric means.
Lemma 13.
Let be anti-ferromagnetic. Then for any integer and any , there exists an such that .
Proof.
Let . Then and . Express in terms of :
Due to Cauchy-Schwarz inequality,
Due to the inequality of arithmetic and geometric means,
Let . Then combining the above calculations,
Let be such that . Then and by substituting for , we have
∎
Lemma 14.
Let be anti-ferromagnetic. If is up-to- unique, then there exists a constant such that for any integer , it holds that for all .
Proof.
Fix to be any positive integer. We characterize the value of at which achieves its maximum. We denote that . Taking derivative of with respect to , we get that
where , whose derivative is
As ranges over , the function is strictly decreasing in and ranges from to , and the function is strictly increasing in and has a bounded range. Thus, the equation
(4) |
has unique solution in , denoted by . Moreover, it holds that
(5) |
The same also holds for . Thus, for any fixed , achieves its maximum when .
Let be the positive fixed point of , that is, . We then claim that if is up-to- unique, then for any integral , To see that this claim is sufficient to imply the lemma, note that after substituting , we have . And due to Lemma 8, if is up-to- unique then there exists a constant such that for all integer .
We then prove the claim. Assume that is up-to- unique and . It is then sufficient to show that is decreasing if and is increasing if .
Case 1: . Due to (5), . Note that
Due to the uniqueness, , thus . Combining with that , we have . Since the function is monotonically decreasing and is its fixed point, . Since satisfies (4), and must be simultaneously positive or negative, thus it also holds that . Then both and are positive and monotonically decreasing in . Therefore, .
Case 2: . By the same argument as above, it holds that , , and . Thus both and are negative and monotonically decreasing in , hence their product is positive and increasing in . Therefore, . ∎
Strong spatial mixing on regular trees.
As a byproduct of our analysis, we prove a strong spatial mixing theorem for regular trees. When the graphs itself is a regular tree. All vertices (except the root) has the same arity. And all s (excerpt the one of the root) that appear in the proof are the same and equal that arity. Then the condition that the uniqueness holds on all infinite regular trees of degree up to can be replaced by the uniqueness on infinite -regular tree.
Theorem 15.
For two-state anti-ferromagnetic spin systems, on any infinite -regular tree the uniqueness implies the strong spatial mixing.
The same result can be obtained by combining the same theorem for the hardcore model [26] and anti-ferromagnetic Ising model [21] and translating the parameters of general two-state anti-ferromagnetic spin systems to these models (as discussed in[24, 21]). However, unlike the hardcore and the anti-ferromagnetic Ising models, for general two-state anti-ferromagnetic spin systems Theorem 15 itself is not sufficient to imply the strong spatial mixing on graphs of maximum degree at most . This is discussed in Section 5.
4 Algorithmic implications
In this section we prove Theorem 2. That is, if an anti-ferromagnetic is up-to- unique then there exists an FPTAS for the partition function for any graph of maximum degree at most , and in particular the universal uniqueness implies an FPTAS for arbitrary graph .
It is well-known that can be computed from by the following standard procedure. Let enumerate the vertices in . For , let be the configuration fixing the first vertices as follows: for and is fixed so that . In particular, is a configuration of . It holds for the Gibbs measure of that as well as that , thus , where the weight can be computed precisely for any particular in time polynomial in . Note that equals to either or . Therefore, if can be approximated within an additive error in time polynomial in and , then the configurations can be efficiently constructed such that all are bounded away from 0, thus the product can be approximated within a factor of in time polynomial in and , which implies an FPTAS for .
Bounded degree graphs.
Let be a graph whose maximum degree is at most and be any vertex. A self-avoiding walk tree can be constructed so that . We can use the recursive procedure described in Section 3 to compute the upper and lower bounds of , with the setting that for all the vertices more than steps away from the root , the trivial bounds is used. Then the proof of Theorem 9 shows that the recursive procedure returns and such that , and for some constant assuming that is up-to- unique. Note that . Let and . Then and
(7) |
The recursive procedure runs in time since it only needs to construct the first levels of the self-avoiding walk tree. If is bounded, by setting , this gives an algorithm which approximates within an additive error in time polynomial in and , which implies an FPTAS for .
Arbitrary graphs.
Let be an arbitrary graph and be any vertex. Let . We use the method of Computationally Efficient Correlation Decay introduced in [15] to deal with the unbounded degrees. Intuitively, using this method we observe correlation decay in a refined metric instead of graph distance such that in this new metric a neighborhood of moderate size is sufficient to guarantee desirable correlation decay.
Similarly, we use the recursive procedure described in Section 3 to compute the upper and lower bounds of , but this time the termination condition relies on a new depth defined as follows.
Definition 16.
Let be a rooted tree and be a constant. For any vertex in , define the -based depth of , denoted , as such: if is the root, and if is one of the children of .
Let to be fixed. Denote by the set of all vertices with -based depth along with their children and grandchildren in . It can be verified by induction that . The recursion is applied to estimate the when the current until is no longer in in which case the trivial bounds is used.
Let be defined as in Section 3. Repeatedly applying Item 3 of Lemma 11, without loss of generality, we have a path in from the root to a with and , such that for , where is the number of children of and , . The key to overcome the explosion caused by unbounded degrees is to observe that the contraction decreases dramatically as the degree grows.
Lemma 17.
Let be anti-ferromagnetic. If satisfies the universal uniqueness, then there exist constants and such that for any integer , and any , , it holds that .
Proof.
By Lemma 17, there exist constants and such that
With the notation used in Section 3, is the complement of . Note that all ’s children are in thus none of them are in , and by Item 2 of Lemma 21 the universal uniqueness implies that . Thus by Item 2 of Lemma 11 it holds that . Therefore, .
Let , where and are the bounds returned by the recursive procedure such that . By the same analysis as in Section 3, . Then by (7), the marginal probability is approximated within an additive error of . The running time of the recursion is . By setting , we have an algorithm which approximates within an additive error of in time polynomial in and , which implies an FPTAS for for arbitrary graph .
Heterogeneous spin systems.
Our analysis in last and this sections actually holds for heterogeneous spin systems which allow that each vertex has a distinct constant external field .
Theorem 18.
For a two-state anti-ferromagnetic heterogeneous spin system with parameters , , and external field at each vertex , for any finite or , if for all the is up-to- unique then the spin system is of strong spatial mixing and has FPTAS on graphs of maximum degree at most .
5 Non-monotonicity of general two-state spin system
In this section, we prove the following theorem.
Theorem 19.
There exist two-state anti-ferromagnetic spin systems which exhibit strong spatial mixing on infinite -regular tree but does not exhibit strong spatial mixing on all graphs of maximum degree at most .
In a seminal work [26], Weitz proved that for the hardcore model the strong spatial mixing on an infinite -regular tree implies the strong spatial mixing on graphs of maximum degree at most (Theorem 2.3 in [26]). He further remarked that the same implication holds for all two-state spin systems. That is,
for any two-state spin system, strong spatial mixing on an infinite -regular tree implies the strong spatial mixing on graphs of maximum degree at most .
This claim played important roles in current understanding of correlation decay in two-state spin systems as well as devising FPTAS for such systems. An algorithmic form of this claim was cited in [21] as a theorem for all two-state spin systems (Theorem 2.8 in [21]) and was proved for the anti-ferromagnetic Ising model. It was raised as a conjecture in [22] whether this claim holds for multi-state spin systems.
Here we clarify that this claim holds only for the two-state spin systems under limited settings but does not hold for all general two-state spin systems. This disproves the conjecture in [22] and shows that the common belief that the -regular tree represents the worst case for strong spatial mixing among all graphs of maximum degree at most cannot be generalized to general two-state spin systems. We first describe a region that the claim is true.
Lemma 20.
For , the strong spatial mixing on infinite -regular tree implies the strong spatial mixing on trees of maximum degree at most .
Proof.
Given a rooted tree of maximum degree at most , for each vertex of children with , we can attach dummy children with fixed (distributions of) spin states. This is the method used in [26] and [21]: for the hardcore model the dummy children are fixed to be unoccupied and for the anti-ferromagnetic Ising model the dummy children are of uniform distributions over spin states. In both cases, the dummy children have no effect on their parent. In general, we fix the distribution to be at each dummy child satisfying
When , this system has solutions in . With the ratio at the -th child, , and for the dummy children , the ratio at the parent is given by the recursion
which is identical to the original quantity. ∎
Due to the self-avoiding walk tree construction (Theorem 6), it holds that for , strong spatial mixing on infinite -regular tree implies the strong spatial mixing and the FPTAS on graphs of maximum degree at most .
For , the spin system shows the following monotone property: the uniqueness on infinite -regular tree implies the uniqueness on all infinite regular trees of smaller degree. This can be verified by the following reasoning: due to Theorem 15, on infinite -regular tree the uniqueness implies the strong spatial mixing, which for , implies the strong spatial mixing (including the uniqueness) on all infinite regular trees of smaller degree.
There exist two-state anti-ferromagnetic spin systems which are non-monotone. We can choose anti-ferromagnetic satisfying that and , where is the upper threshold for universal uniqueness given in Item 8 of Lemma 21. Due to Item 3 of Lemma 21, for the uniqueness holds on -regular trees for all sufficiently large . On the other hand, due to Item 8 of Lemma 21, cannot be universally unique when , which means that there exists a finite such that the system is non-unique on -regular tree.
For such non-monotone systems, due to Theorem 15, the uniqueness implies the strong spatial mixing on -regular tree for sufficiently large , but the strong spatial mixing does not hold on a regular tree of smaller degree (because of the non-uniqueness on the smaller tree). Therefore the implication between the strong spatial mixing on -regular tree and on graphs of maximum degree at most does not hold for general two-state spin systems.
Acknowledgment.
We would like to thank Alistair Sinclair and Piyush Srivastava for the helpful comments to an early version of this paper.
Acknowledgment for the 2021 revision.
We would like to thank Xiaoyu Chen, Weiming Feng and Xinyuan Zhang for locating an error in Lemma 21 in the original (2013) version of the paper and suggesting its fix.
References
- [1] A. Bandyopadhyay and D. Gamarnik. Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Struct. Algorithms, 33:452–479, December 2008.
- [2] M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali. Simple deterministic approximation algorithms for counting matchings. In Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing, STOC ’07, pages 122–127, New York, NY, USA, 2007. ACM.
- [3] M. Dyer, M. Jerrum, and E. Vigoda. Rapidly mixing markov chains for dismantleable constraint graphs. In Proceedings of a DIMACS/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics, 2001.
- [4] M. E. Dyer, A. M. Frieze, and M. Jerrum. On counting independent sets in sparse graphs. SIAM Jounal on Computing, 31(5):1527–1541, 2002.
- [5] M. E. Dyer and C. S. Greenhill. On markov chains for independent sets. Journal of Algorithms, 35(1):17–49, 2000.
- [6] A. Galanis, Q. Ge, D. Štefankovič, E. Vigoda, and L. Yang. Improved inapproximability results for counting independent sets in the hard-core model. In The 15th International Workshop on Randomization and Computation, RANDOM ’11, 2011.
- [7] A. Galanis, D. Stefankovic, and E. Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Arxiv preprint arXiv:1203.2226, 2012.
- [8] D. Gamarnik and D. Katz. Correlation decay and deterministic fptas for counting list-colorings of a graph. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’07, pages 1245–1254, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics.
- [9] L. A. Goldberg and M. Jerrum. A polynomial-time algorithm for estimating the partition function of the ferromagnetic ising model on a regular matroid. In L. Aceto, M. Henzinger, and J. Sgall, editors, Proceedings of the 38th International Colloquium on Automata, Languages and Programming, volume 6755 of ICALP ’11, pages 521–532. Springer, 2011.
- [10] L. A. Goldberg, M. Jerrum, and M. Paterson. The computational complexity of two-state spin systems. Random Struct. Algorithms, 23(2):133–154, 2003.
- [11] M. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms, 7(2):157–166, 1995.
- [12] M. Jerrum and A. Sinclair. Polynomial-time approximation algorithms for the ising model. SIAM Journal on Computing, 22(5):1087–1116, 1993.
- [13] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51:671–697, July 2004.
- [14] F. Kelly. Stochastic models of computer communication systems. Journal of the Royal Statistical Society. Series B (Methodological), 47(3):379–395, 1985.
- [15] L. Li, P. Lu, and Y. Yin. Approximate counting via correlation decay in spin systems. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, pages 922–940, Kyoto, Japan, 2012. SIAM.
- [16] L. Li, P. Lu, and Y. Yin. Correlation Decay up to Uniqueness in Spin Systems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, pages 67-84, New Orleans, Louisiana, USA, 2013. SIAM.
- [17] M. Luby and E. Vigoda. Approximately counting up to four (extended abstract). In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, STOC ’97, pages 682–687, New York, NY, USA, 1997. ACM.
- [18] F. Martinelli, A. Sinclair, and D. Weitz. Fast mixing for independent sets, colorings, and other models on trees. Random Struct. Algorithms, 31(2):134–172, 2007.
- [19] E. Mossel, D. Weitz, and N. Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143:401–439, 2009.
- [20] R. Restrepo, J. Shin, P. Tetali, E. Vigoda, and L. Yang. Improved mixing condition on the grid for counting and sampling independent sets. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’11, 2011.
- [21] A. Sinclair, P. Srivastava, and M. Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 941–953. SIAM, 2012.
- [22] A. Sly. Uniqueness thresholds on trees versus graphs. The Annals of Applied Probability, 18(5):1897–1909, 2008.
- [23] A. Sly. Computational transition at the uniqueness threshold. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 287–296, Washington, DC, USA, 2010. IEEE Computer Society.
- [24] A. Sly and N. Sun. The computational hardness of counting in two-spin models on d-regular graphs. Arxiv preprint arXiv:1203.2602, 2012.
- [25] E. Vigoda. Improved bounds for sampling coloring. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, pages 51–, Washington, DC, USA, 1999. IEEE Computer Society.
- [26] D. Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, STOC ’06, pages 140–149, New York, NY, USA, 2006. ACM.
Appendix A The Uniqueness Thresholds
The following lemma translates the uniqueness condition into its various threshold forms. The lemma (except for item 2) is not used in the proofs of the main results but is used in the interpretation of the main results and comparisons to the previous results which are mostly stated in threshold forms.
Lemma 21.
Let be anti-ferromagnetic.
-
1.
is up-to-2 unique.
-
2.
If , then the uniqueness does not hold on infinite -regular tree for all sufficiently large .
-
3.
If , then the uniqueness holds on infinite -regular tree for all sufficiently large .
-
4.
For any (including ), there exists a critical threshold such that is up-to- unique if and only if . In particular, and for some finite .
-
5.
If , for any (including ), there exists a critical threshold such that is up-to- unique if and only if .
-
6.
If , then for any external field , is up-to- unique.
-
7.
If , for any (including ) that , the regime for the satisfying up-to- uniqueness is as follows.
Let . For any integer , let be the two positive roots of equation , more specifically,
Let , where , be defined for integers .
Then is up-to- unique if and only if belongs to the following regime
(8) And if furthermore , then is up-to- unique if and only if , where
In particular, when , it holds that , and thus is up-to- unique if and only if .
-
8.
can be universally unique only when . If , there exist finite positive constants and where , such that is universally unique if and is universally unique only if .
Remark (An error in the SODA’13 version).
In the earlier version of the paper, there was an error in Item 7 of Lemma 21 (which was Lemma 3.1 in the SODA’13 conference version [16]). In that version, the uniqueness regime (8) was unconditionally and wrongly simplified to the bi-interval simple form , which actually holds more restrictively when both . However, when , there exist such that the uniqueness regime (8) may become more complicated than consisting of at most two intervals. For example, when , , and , the regime for the such that is up-to- unique, consists of three intervals .
The current version corrects the error and changes the statements of Item 7 and Item 8 of Lemma 21. We further remark that the error does not affect the main result of the paper, namely the implication from the up-to- uniqueness to strong spatial mixing and FPTAS, because Lemma 21 is not used in the proofs of the main results (except for Item 2), but is only used for the interpretation of the uniqueness regime in various threshold forms and comparison with other known results.
Proof of Lemma 21.
Let and be the positive fixed point of . Then
Let be anti-ferromagnetic. That is, , , and , thus .
-
1.
It is easy to verify that for , for any positive . Therefore, when , we have , which means that is up-to-2 unique.
-
2.
For all sufficiently large , it holds that
By contradiction, suppose that . Then,
-
Case.1:
. Then . Thus,
which implies that . However, it holds that
a contradiction.
-
Case.2:
. Then . Thus,
which implies that . However, it holds that
a contradiction.
-
Case.1:
-
3.
Let . The fixed point , and
which is strictly less than 1 for all sufficiently large . Thus the uniqueness holds on infinite -regular tree for all sufficiently large .
-
4.
We first show that there exists a critical threshold such that is up-to- unique if and only if . It is sufficient to show that if an anti-ferromagnetic is up-to- unique then is up-to- unique for any and .
Recall that is the positive fixed point of . Also let denote the positive solution to .
We first show that . By contradiction, assume that . Since for anti-ferromagnetic , is monotonically decreasing, we have
a contradiction.
Since
we have
For , it also holds that
Multiplying the above two inequalities together, we have
Note that these are the absolute derivatives at the respective fixed points when the parameters are and . Therefore if is up-to- unique then is up-to- unique.
-
5.
When , , the uniqueness condition is equivalent to that (here we assume since due to Part 1 of the lemma, for the uniqueness always holds). Recall that . Then if and only if
Let . It holds that is up-to- unique if and only if .
-
6.
We note that is not monotone in . It achieves its maximum value at . Therefore, if for any , for , then is up-to- unique for any . This condition holds when for all , i.e. when .
-
7.
Let . It holds that for all . Thus, are well-defined and can be expressed as:
Recall that for .
The following monotonicity and unboundedness of is easy to verify.
Claim 22.
is monotonically increasing in and goes to infinity as grows.
Proof.
Observe that for , and , it holds that and is increasing in . Moreover,
It is easy to verify that is increasing in and unbounded as grows. Therefore, we can conclude that is increasing in and is unbounded as grows. ∎
We proceed to analyze the uniqueness regime. For , it holds that , in which case it always holds that due to Part 6 of this lemma.
Recall that . It remains to analyze the for those . For such ’s, we have , and since and are the roots of equation , it holds that if and only if or . Note that is monotonically increasing in . Thus:
which means for any , if and only if .
Therefore, is up-to- unique if and only if belongs to the regime
which is exactly the uniqueness regime (8). Recall that
where the last equation is due to the monotonicity of .
We then show that for , the uniqueness regime (8) becomes . We need the following claims, whose proofs are postponed to the end of this section.
Claim 23.
For , it always holds that
furthermore, if for all integers , then
Claim 24.
The followings hold:
-
•
if , then for all integers ;
-
•
if , there is a finite such that for all .
Now assume that . By Claim 24, for all integers . Then due to Claim 23, the uniqueness regime (8) becomes
In particular, consider , the anti-ferromagnetic Ising model. It is easy to verify that , and thus
Therefore, is monotonically decreasing, due to the monotonicity of guaranteed by Claim 22. As a result, , , and . Then is up-to- unique if and only if .
-
•
-
8.
The case of is taken cared of in Part 5 of this lemma. In such case, due to Part 5 of the lemma, is up-to- unique if and only if where . In particular, becomes 0 if and becomes a positive and finite if . Therefore, is universally unique only if , and when , is universally unique if and only if . We can let and the lemma follows.
For the case of , due to Part 7 of the lemma, for all , the tuple is up-to- unique if and only if belongs to the following regime:
When , this regime becomes , where and .
Claim 25.
The followings hold:
-
•
if , then approaches 0 as grows to infinity;
-
•
if , then is unbounded as grows to infinity.
Proof.
For integers , let , and let
(9) When , it is easy to verify that approaches 0 as grows to infinity.
Moreover, is upper bounded by . Specifically, for ,
Since is increasing in when , we have
Thus, for all ,
(10) Therefore, when , approaches 0 as grows to infinity.
On the other hand, when , for ,
which is obviously unbounded as grows. ∎
When , due to above claim, approaches 0 as grows to infinity, which means ; and by Claim 22, goes to infinity as grows to infinity, which means . Therefore, can be universally unique only when .
Now assume . By Claim 25, is unbounded as grows. Thus, achieves its minimum value at a finite . And it is obvious that is always finite and positive for any finite . Therefore, is finite and positive. Let denote this finite positive threshold.
On the other hand, by Claim 24, for , there is a finite such that for all . Let . Obviously, . And is also finite.
-
•
∎
Proof of Claim 23.
First, it is easy to verify that for , it always holds that
since for all , it always holds that
Next, we prove that the two regimes are equal if for all integers . This is proved by induction.
The equality in the claim is trivial to hold when , because in this case there is at most one integer satisfying . Then both sides of the equality becomes
This establishes the induction basis.
For the induction hypothesis, assume that the equality holds for :
(11) |
where we denote
For the induction step, we want to establish the equality when is increased by 1. Thus in addition, we assume that for the unique integer , that is
(12) |
To finish the induction, it is then sufficient to verify that
assuming the induction hypothesis (11). Therefore, it is sufficient to verify that
(13) |
Note that is the unique integer in . And due to the monotonicity of , we have . Therefore, , and thus (13) holds as long as , which is guaranteed by the assumption (12). ∎
Proof of Claim 24.
It also holds that . For all , we have . Since is monotonically increasing in when , it holds that . Meanwhile, for all , it holds that and . Therefore,
(14) |
Assume . It is also not hard to observe that is decreasing in . Indeed, if , then is monotonically decreasing in ; and we can verify the monotonicity of function for as follows:
which guarantees that is monotonically decreasing in , and hence is decreasing in for , since both and are positive and decreasing in .
Therefore, when , due to (10), the monotonicity of , and (14), for all ,
This proves that for all when .
Finally, when , by contradiction suppose that for some . We then deduce a finite upper bound on such bad . By (10), we have , where the last inequality is due to that is increasing and is decreasing; and by (14), we have . Hence implies that
(15) |
Recall that for , it always holds that . And without loss of generality, we only consider large enough , and thus since is decreasing. Therefore inequality (15) implies that
which gives us a necessary condition for , among the ’s that and . Let
It then must hold that for all . ∎
Appendix B Proof of Lemma 11 (a Mean Value Theorem approach)
-
1.
Due to the Mean Value Theorem, there exists an such that
-
2.
Suppose that each vertex has at most children. Then due to the assumption either is bounded or .
If , then , where . If , then ; and if is finite, then .
Due to the Mean Value Theorem, there exist , , such that
If for all , then due to the above argument, for free , where is the number of children of ; and trivially for fixed . Therefore, . If , then it is easy to see that is bounded by a constant, thus it holds that ; if is bounded, then is also bounded, thus clearly .
-
3.
We then analyze the stepwise contraction of . Define that and accordingly , . Then and , . We have
Apply the Mean Value Theorem. There exist and corresponding satisfying , such that
Appendix C Finding a good potential function heuristically
Perhaps the most mysterious step in our proof is the choice of the potential function . As in many cases where potential analysis is applied, there is no standard routine for searching for a suitable potential function. On the other hand, it is quite unlikely that we can just guess such a fairly complicated formula without any hints. Here we present a heuristic approach which leads us to the discovery of a good potential function. This part is not rigorous and logically unnecessary for the soundness of our result. Nevertheless, this heuristic approach is general and interesting enough and may find its applications in other scenarios, thus deserves an exposition here.
The heuristics consists of three steps:
-
1.
Find a necessary condition for the potential function, which is an equation related to the potential function at one point.
-
2.
(heuristic step) Enhance the condition by assuming that the equation holds for the whole range of the variable, which gives us a differential equation.
-
3.
Solve the differential equation and get a potential function.
We first assume that the system is at the boundary of uniqueness. This means that is the critical degree and , where and is the positive fixed point.
We have the following identities:
which together implies another identity
(16) |
The goal is to find a potential function such that for all . On the other hand, we have . So achieves its maximum when . As a differentiable function, it holds that , that is
We have the following calculation:
where we use the fact that and .
Taking the second derivative of , we have
This equation already gives an identity for . But it is too complicated. We may further simplify the above formula at the point .
So we have
(17) |
We apply the heuristics and assume that (17) simply holds for all . This gives us a differential equation
The solution of this differential equation is
which gives that
where are some constants. This gives the potential function we used in the paper.
There are also other equations which hold for the fixed point . Choosing which equation for to heuristically extend to all may affect the potential function we obtained. For example, (16) implies that
thus we can rewrite as
This gives that
We can also treat this equation as a differential equation for variable and solving it gives us
which is the potential function used in [15].