We prove Gibbs distribution of two-state spin systems(also known as binary Markov random fields) without hard constrains on a tree exhibits strong spatial mixing(also known as strong correlation decay), under the assumption that, for arbitrary `exter
nal field, the absolute value of `inverse temperature is small, or the `external field is uniformly large or small. The first condition on `inverse temperature is tight if the distribution is restricted to ferromagnetic or antiferromagnetic Ising models. Thanks to Weitzs self-avoiding tree, we extends the result for sparse on average graphs, which generalizes part of the recent work of Mossel and Slycite{MS08}, who proved the strong spatial mixing property for ferromagnetic Ising model. Our proof yields a different approach, carefully exploiting the monotonicity of local recursion. To our best knowledge, the second condition of `external field for strong spatial mixing in this paper is first considered and stated in term of `maximum average degree and `interaction energy. As an application, we present an FPTAS for partition functions of two-state spin models without hard constrains under the above assumptions in a general family of graphs including interesting bounded degree graphs.
Counting the number of all the matchings on a bipartite graph has been transformed into calculating the permanent of a matrix obtained from the extended bipartite graph by Yan Huo, and Rasmussen presents a simple approach (RM) to approximate the perm
anent, which just yields a critical ratio O($nomega(n)$) for almost all the 0-1 matrices, provided its a simple promising practical way to compute this #P-complete problem. In this paper, the performance of this method will be shown when its applied to compute all the matchings based on that transformation. The critical ratio will be proved to be very large with a certain probability, owning an increasing factor larger than any polynomial of $n$ even in the sense for almost all the 0-1 matrices. Hence, RM fails to work well when counting all the matchings via computing the permanent of the matrix. In other words, we must carefully utilize the known methods of estimating the permanent to count all the matchings through that transformation.
