A standard method for designing randomized algorithms to approximately count the number of solutions of a problem in @math P, is by constructing a rapidly mixing Markov chain converging to the uniform distribution over this set of solutions. This construction is not always an easy task, and it is conjectured that it is not always possible. We want to investigate other possibilities for using Markov Chains in relation to counting, and whether we can relate algorithmic counting to other, non-uniform, probability distributions over the set we want to count. In this paper we present a family of probability distributions over the set of solutions of a problem in TotP, and show how they relate to counting; counting is equivalent to computing their normalizing factors. We analyse the complexity of sampling, of computing the normalizing factor, and of computing the size support of these distributions. The latter is also equivalent to counting. We also show how the above tasks relate to each other, and to other problems in complexity theory as well. In short, we prove that sampling and approximating the normalizing factor is easy. We do this by constructing a family of rapidly mixing Markov chains for which these distributions are stationary. At the same time we show that exactly computing the normalizing factor is TotP-hard. However the reduction proving the latter is not approximation preserving, which conforms with the fact that TotP-hard problems are inapproximable if NP @math RP. The problem we consider is the Size-of-Subtree, a TotP-complete problem under parsimonious reductions. Therefore the results presented here extend to any problem in TotP. TotP is the Karp-closure of self-reducible problems in @math P, having decision version in P.
@cite_30: The q-state Potts model can be defined on an arbitrary finite graph, and its partition function encodes much important information about that graph, including its chromatic polynomial, flow polynomial and reliability polynomial. The complex zeros of the Potts partition function are of interest both to statistical mechanicians and to combinatorists. I give a pedagogical introduction to all these problems, and then sketch two recent results: (a) Construction of a countable family of planar graphs whose chromatic zeros are dense in the whole complex q-plane except possibly for the disc |q−1|<1. (b) Proof of a universal upper bound on the q-plane zeros of the chromatic polynomial (or antiferromagnetic Potts-model partition function) in terms of the graph's maximum degree.
@cite_28: 
@cite_36: In this paper we consider the reconstruction problem on the tree for the hardcore model. We determine new bounds for the non-reconstruction regime on the k-regular tree showing non-reconstruction when lambda (e+o(1))ln^2(k). We discuss the relationship for finding large independent sets in sparse random graphs and to the mixing time of Markov chains for sampling independent sets on trees.
@cite_29: 
@cite_24: We make an analogy between images and statistical mechanics systems. Pixel gray levels and the presence and orientation of edges are viewed as states of atoms or molecules in a lattice-like physical system. The assignment of an energy function in the physical system determines its Gibbs distribution. Because of the Gibbs distribution, Markov random field (MRF) equivalence, this assignment also determines an MRF image model. The energy function is a more convenient and natural mechanism for embodying picture attributes than are the local characteristics of the MRF. For a range of degradation mechanisms, including blurring, nonlinear deformations, and multiplicative or additive noise, the posterior distribution is an MRF with a structure akin to the image model. By the analogy, the posterior distribution defines another (imaginary) physical system. Gradual temperature reduction in the physical system isolates low energy states ( annealing''), or what is the same thing, the most probable states under the Gibbs distribution. The analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations. The result is a highly parallel relaxation'' algorithm for MAP estimation. We establish convergence properties of the algorithm and we experiment with some simple pictures, for which good restorations are obtained at low signal-to-noise ratios.
@cite_0: This is an invited survey on the relation between the partition function of the Potts model and the Tutte polynomial. On the assumption that the Potts model is more familiar we have concentrated on the latter and its interpretations. In particular we highlight the connections with Abelian sandpiles, counting problems on random graphs, error correcting codes, and the Ehrhart polynomial of a zonotope. Where possible we use the mean field and square lattice as illustrations. We also discuss in some detail the complexity issues involved.
@cite_2: Statistical physics models with hard constraints, such as the discrete hard-core gas model (random independent sets in a graph), are inherently combinatorial and present the discrete mathematician with a relatively comfortable setting for the study of phase transition. In this paper we survey recent work (concentrating on joint work of the authors) in which hard-constraint systems are modeled by the space @math of homomorphisms from an infinite graph @math to a fixed finite constraint graph @math . These spaces become sufficiently tractable when @math is a regular tree (often called a Cayley tree or Bethe lattice) to permit characterization of the constraint graphs @math which admit multiple invariant Gibbs measures. Applications to a physics problem (multiple critical points for symmetry-breaking) and a combinatorics problem (random coloring), as well as some new combinatorial notions, will be presented.
@cite_34: A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two‐dimensional rigid‐sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four‐term virial coefficient expansion.
@cite_13: 
Some non-uniform probability measures have already been studied in other areas of computer science, where problems concern the computation of a weighted sum over the set of solutions to a combinatorial problem. E.g. computing the partition function of the hard-core model and the Potts-model from statistical physics. There are Markov chains associated to these problems, that converge to non-uniform distributions in general. E.g. Glauber dynamics, Gibbs sampling @cite_24 , Metropolis-Hastings algorithm @cite_34 @cite_28 etc. However, for the special cases where weights are in @math , the problems correspond to conventional counting problems in #P, and the associated stationary distributions are uniform, again. The literature on this areas is enormous, e.g. @cite_36 @cite_13 @cite_2 @cite_30 @cite_0 @cite_29 .