2-Spin System Quick Notes

Setting

Configuration : A configuration of graph is a map such as:

$$\begin{aligned} \sigma: V &\to 2^V\\ u&\mapsto \{+,-\} \end{aligned}$$

Partition Function: For graph , define its partition function as

$$Z_G(\beta, \gamma, \lambda) = \sum_{\sigma} \beta^{m_{++}}\gamma^{m_{--}}\lambda^{n_+}$$

where is the number of edges between two vertices pinned to , is the number of vertices pinned to , and we sum over all possible configurations.

Initially, we wonder when there exsits a polynomial time algorithm to calculate the Partition Function of a given graph, but it’s proved that this is impossible for most cases. So we wonder when there exsits a polynonial time algorithm to calculate the -approximation of the Partition Function, and such algorithm are called FPTAS.

We are also interested in the following specific cases of the 2-Spin System:

Hardcore Model: (The partition function of which is exactly the independence polynomial)

Ising Model:

Weitz algorithm

Sub-configuration：A sub-configuration defined on is a map.

We can expand the defination of partition function to situation where some points are pinned by a sub-configuation:

$$Z_G^\sigma(\beta, \gamma, \lambda) = \sum_{\tau:\tau|_\Gamma = \sigma} \beta^{m_{++}}\gamma^{m_{--}}\lambda^{n_+}$$

Specially we use to represent the partition function where the vertex is pinned to . And we define marginal possibility of as follow(marginal distribution at vertex conditioning on ):

$$P_{G,v}^{\sigma,+} = \frac{Z_{G,v}^{\sigma,+}}{Z_G}$$

The possibility explanation of this ratio is the conditional probability of Gibbs distribution over all configurations in (Not important in this article):

$$P_{G,v}^{\sigma,+} = \mathrm{Pr}_{X\sim\mu_G}[X_v=+|X_\Gamma=\sigma]$$

It’s obvious that lies in when are real(and that’s directly by the possibility explanation). One wonder how is the calculation of helpful for , and the answer is: let and we can easily calculate the partition function if all vertices are pinned to . Then we multiply the marginal possibility times (pinning one more point each time) to get the partition function we want.

Now the problem is reduced to calculation of in polynomial time. The key here is the so-called Correlation Decay Method. The main property of decay of correlation is called Strong Spatial Mixing(SSM). The SSM at rate is defined as:

$$\forall \sigma, \tau \in[q]^{\Lambda} \text { that differ on } \Delta:\left\|p_v^\sigma-p_v^\tau\right\|_{T V} \leq \delta\left(\operatorname{dist}_G(v, \Delta)\right)$$

SSM means that marginal probabilities are well approximated by the local information. But even if for a graph that exhibits SSM it’s hard to calculate its local information, so we first study the special case of trees. In this case we can find the Tree Recurrence of .

For the hardcore model case we can establish Tree Recurrence for the probability but for the general case it’s hard to do so. So we first define Occupancy ratio:

$$R_v = \frac{p_v^{\sigma,+}}{p_v^{\sigma,-}}$$

Here comes the main trick of weitz algorithm: induction from general graphs to tree cases. We use the construction called Self-Avoiding Walk(SAW) Tree.

The main result is that the marginal possibility of a graph is equal to that of its SAW Tree’s.

Barvinok algorithm

The main trick is the truncation of Taylor series. First we consider the approximation of independence polynomial (hardcore model) .