Chapter 51: Discrete Probability and Statistical Mechanics

When does local interaction change global sampling behavior?

Three sites form the path $a-b-c$. A site may be occupied or empty, but neighboring sites cannot both be occupied. The allowed occupied sets are exactly $\varnothing,\{a\},\{b\},\{c\},\{a,c\}$. A positive parameter $\lambda$, called the activity, gives a configuration $I$ weight $\lambda^{\lvert I\rvert}$. The partition function adds all allowed weights:

$$Z_{P_3}(\lambda)=1+3\lambda+\lambda^2.$$

Divide each weight by $Z$ to obtain a probability distribution. At $\lambda=1$ the five configurations are equally likely; at $\lambda=4$ their probabilities are $1/29,4/29,4/29,4/29,16/29$. Raising the activity favors occupation, but the exclusion rule still couples neighboring sites. Sampling each site independently is not the same distribution.

There are three related questions. Counting asks for $Z$ or its coefficients. Spatial dependence asks how fixing a distant site's state changes a local probability. Temporal mixing asks how long a specified update rule takes to approach the distribution. These are different quantities: knowing one exactly does not automatically give a sharp bound on the others.

For example, conditional on $c$ being occupied, $b$ must be empty and $a$ is occupied with probability $\lambda/(1+\lambda)$. Conditional on $c$ being empty, the remaining two-site path has three configurations, so $a$ is occupied with probability $\lambda/(1+2\lambda)$. The difference is

$$D_3(\lambda)=\frac{\lambda^2}{(1+\lambda)(1+2\lambda)}.$$

It equals $1/6$ at activity one and $16/45$ at activity four. Endpoints two edges apart are dependent even though they are not adjacent. A successful analysis will explain this dependence, normalize the weights correctly, and distinguish equilibrium calculations from the behavior of a sampler.

The finite model and these calculations are the chapter foundation. The numbered sections are optional extensions. Useful prerequisites are random combinatorial structures, entropy methods, and approximate counting. No measure-theoretic probability is needed for a finite sum; infinite-volume claims below require additional hypotheses.

51.1 Gibbs measures on finite combinatorial structures

Optional extension; not required to complete the chapter foundation.

Let $\Omega$ be a nonempty finite configuration set. Give each configuration an energy $H(\omega)$ and let $\beta\ge0$ be inverse temperature. A finite Gibbs measure is

$$\mu_\beta(\omega)=\frac{e^{-\beta H(\omega)}}{Z(\beta)},\qquad Z(\beta)=\sum_{\omega\in\Omega}e^{-\beta H(\omega)}.$$

More generally any positive weights define a normalized finite distribution. A hard constraint can be imposed by restricting $\Omega$; forbidden configurations have probability zero. A local energy is a sum of terms involving nearby variables. Local terms do not imply global independence: neighboring terms share variables.

Solved example. For independent sets, use weights $\lambda^{\lvert I\rvert}=e^{\theta\lvert I\rvert}$ with $\theta=\log\lambda$. On our three-site path at activity one, the center is occupied only in $\{b\}$, so its marginal is $1/5$. An endpoint belongs to its singleton and the doubleton, so its marginal is $2/5$. The expected number of occupied sites is $2/5+1/5+2/5=1$. This checks the same expectation by summing site marginals rather than configuration sizes.

An observable $F$ has expectation $\mathbb E_\mu F=\sum_\omega\mu(\omega)F(\omega)$. Direct differentiation of the finite sum gives $\partial_\theta\log Z=\mathbb E\lvert I\rvert$ and $\partial_\theta^2\log Z=\operatorname{Var}(\lvert I\rvert)$. At activity one, the second moment is $(3+4)/5=7/5$, hence variance $2/5$. These identities connect a counting function to equilibrium fluctuations.

A finite positive partition function is smooth for real finite parameters. A thermodynamic phase transition concerns a limit over growing systems or an infinite-volume measure; a steep finite curve alone is not such a theorem. If a hard-constraint set is empty, its hard partition function is zero and normalization is undefined. That case must be detected rather than interpreted as a probability measure.

Exercise. At activity two, find the center marginal and expected occupied size on $P_3$. Hint: first compute $Z=1+6+4$. Solution: the center marginal is $2/11$; the mean is $(3\cdot2+2\cdot4)/11=14/11$. The weights are positive and sum to eleven, so normalization is well defined.

Primary hard-core treatment: Weitz's Counting Independent Sets up to the Tree Threshold. The identities in this section follow directly from finite sums. Omitted prerequisites: constructing infinite-volume Gibbs states and proving their existence or uniqueness.

51.2 Independence polynomials and partition functions

Optional extension; not required to complete the chapter foundation.

For a graph $G$, its independence polynomial is $Z_G(\lambda)=\sum_{I\text{ independent}}\lambda^{\lvert I\rvert}$. The coefficient of $\lambda^k$ counts independent sets of size $k$. At activity one it counts all independent sets; at activity zero it equals one because only the empty set contributes. The probability measure uses positive activity, but the polynomial itself is also an algebraic object.

Deletion recurrence and proof. For a vertex $v$, let $N[v]$ be $v$ together with all its neighbors. Split independent sets into those excluding $v$ and those including it. The first class is counted by $Z_{G-v}$. In the second class, all vertices of $N[v]$ are unavailable, and including $v$ contributes a factor $\lambda$. Therefore

$$Z_G(\lambda)=Z_{G-v}(\lambda)+\lambda Z_{G-N[v]}(\lambda).$$

Disjoint graphs multiply partition functions: choose an independent set in each component, and multiply its weights. The empty graph has partition function one. These facts give exact recursive algorithms; repeated subproblems or graph structure determine whether the computation is efficient.

For the path on $n$ vertices write $Z_n=Z_{P_n}(\lambda)$. Deleting an endpoint gives $Z_0=1$, $Z_1=1+\lambda$, and $Z_n=Z_{n-1}+\lambda Z_{n-2}$. This needs $O(n)$ arithmetic operations and constant working storage for a numerical evaluation. Bit complexity is different: at activity one the integer answer has $O(n)$ bits, so arithmetic is not constant cost in a bit model.

Exercise. Find the independence polynomial of a four-cycle. Hint: its only size-two independent sets are the two opposite pairs. Solution: $1+4\lambda+2\lambda^2$. A four-vertex path instead has $1+4\lambda+3\lambda^2$, so equal vertex counts do not determine $Z$.

These finite recurrences also underlie algorithmic hard-core counting; Weitz develops a much broader approximation method. Here the path recurrence is an exact elementary computation.

51.3 Hard-core and Ising models on graphs

Optional extension; not required to complete the chapter foundation.

The hard-core model assigns each vertex a bit $\eta_v\in\{0,1\}$, forbids adjacent ones, and weights a valid configuration by $\lambda^{\sum_v\eta_v}$. Its interaction is an exclusion rule. In an Ising model, spins $\sigma_v\in\{-1,+1\}$ are all allowed and have weights

$$w(\sigma)=\exp\left(\beta\sum_{uv\in E}\sigma_u\sigma_v+h\sum_v\sigma_v\right).$$

Here the coupling constant has been absorbed into $\beta$ and the field is the dimensionless parameter $h$. Positive $\beta$ favors equal adjacent spins; negative $\beta$ favors opposite spins. Stating the sign and field convention avoids confusing ferromagnetic and antiferromagnetic regimes.

Solved example. On $a-b-c$ with $h=0$, let $S=\sigma_a\sigma_b+\sigma_b\sigma_c$. Two configurations have $S=2$, four have $S=0$, and two have $S=-2$. Consequently

$$Z_{\mathrm{Ising}}=2e^{2\beta}+4+2e^{-2\beta}=8\cosh^2\beta.$$

At $\beta=\log2$, these weights are $4,1,1/4$. Multiply every weight by four to use integer weights $16,4,1$ and total fifty; common scaling leaves probabilities unchanged. Each all-equal configuration has probability $16/50$, each one-disagreement configuration $4/50$, and each alternating configuration $1/50$.

Read the SVG as a complete enumeration on the same two-edge path. Bits identify occupied hard-core sites; signs identify Ising spins. Every displayed row has exactly the two edges $ab$ and $bc$. The integer Ising weights use the stated scaling, not the unscaled partition function.

For the zero-field Ising path, choose $\sigma_a$ uniformly, then choose the two edge products independently with weights $e^\beta$ for agreement and $e^{-\beta}$ for disagreement. This is a bijective parametrization of all eight spin configurations. Each edge product has mean $\tanh\beta$, so $\mathbb E(\sigma_a\sigma_c)=(\tanh\beta)^2$. At $\beta=\log2$, it equals $9/25$. Global spin-flip symmetry gives each single-spin mean zero, so this correlation is also the covariance.

Exercise. At $\beta=0$ and $h=0$, how many Ising configurations are there and what is the endpoint correlation? Hint: all weights are one. Solution: eight configurations and correlation zero. This differs from the hard-core uniform measure, which supports only five bit configurations.

Primary dynamical Ising source: Glauber's Time-Dependent Statistics of the Ising Model. Scope: our partition sum and correlation are proved by finite enumeration and edge variables. Infinite-lattice critical temperatures are not inferred from this path.

51.4 Correlation decay and uniqueness thresholds

Optional extension; not required to complete the chapter foundation.

Correlation decay means that changing far-away boundary conditions has a diminishing effect on a local marginal. It must be stated uniformly over the boundary assignments under consideration. A single small covariance is not enough to prove such uniform control. Weak spatial mixing measures distance to the whole fixed boundary; strong spatial mixing measures distance to the boundary sites whose assigned values differ, even when other nearby sites are fixed identically.

On a rooted hard-core tree, define an occupation ratio $R_v$ as the total weight with $v$ occupied divided by the total weight with $v$ empty, within its descendant subtree. An empty parent leaves each child free; an occupied parent forces every child empty. This factorization proves

$$R_v=\lambda\prod_{u\text{ child of }v}\frac1{1+R_u},\qquad \Pr(v\text{ occupied})=\frac{R_v}{1+R_v}.$$

Solved path example and decay proof. A path has one child per nonterminal message, so $f(x)=\lambda/(1+x)$. For $x\ge0$,

$$f(f(x))=\frac{\lambda(1+x)}{1+x+\lambda},\qquad \left|(f\circ f)'(x)\right|\le\left(\frac{\lambda}{1+\lambda}\right)^2\lt1.$$

Thus two-step updates contract the difference between any two nonnegative incoming messages. A pinned boundary may initially correspond to ratio zero or infinity; after one update both resulting messages lie in $[0,\lambda]$. Every pair of further updates contracts by the displayed factor. Since $x/(1+x)$ has derivative at most one, the occupation-probability difference also decays. This proves exponential endpoint boundary decay on paths for every fixed finite $\lambda\gt0$. The constants can worsen as activity increases.

At activity one, fixing the far endpoint of $P_3,P_4,P_6,P_8$ to occupied versus empty changes the first endpoint marginal by $1/6,1/15,1/104,1/714$ respectively. These are exact finite conditional calculations; the contraction proves decay beyond those four instances.

For the infinite regular tree of degree $\Delta\ge3$, each nonroot vertex has $d=\Delta-1$ children. A symmetric message obeys $R=\lambda/(1+R)^d$. The derivative magnitude at this fixed point is $dR/(1+R)$; setting it to one gives $R=1/(d-1)$ and

$$\lambda_c(\Delta)=\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^\Delta}.$$

For degree three this is four. The established hard-core tree theorem gives uniqueness for $\lambda\le\lambda_c$ and nonuniqueness for $\lambda\gt\lambda_c$; strict inequality below the threshold gives exponential boundary decay. A primary statement appears in Weitz's paper. Proof scope: the derivative calculation motivates the threshold; proving the full infinite-tree uniqueness theorem, including equality, requires the boundary-recursion analysis omitted here. The threshold is for that tree, not every graph of that degree, and its degree-three value is not a critical activity for paths.

Exercise. Why does the simple one-step path derivative fail to prove decay at activity four? Hint: inspect $|f'(0)|$. Solution: it equals four, exceeding one; the two-step derivative is bounded by $(4/5)^2$, which is below one. Failure of one proof criterion is not failure of correlation decay.

51.5 Glauber dynamics and mixing thresholds

Optional extension; not required to complete the chapter foundation.

Hard-core Glauber dynamics repeatedly chooses a uniform vertex and resamples its occupancy conditional on all other sites. It sets a blocked vertex empty, and an unblocked one occupied with probability $\lambda/(1+\lambda)$. Its state space is the independent sets. For every finite positive activity it is irreducible: remove occupied sites to reach the empty set, then add a target independent set. Self-transitions occur with positive probability, so it is aperiodic.

Detailed-balance proof. If $J=I\cup\{v\}$ is valid, then $P(I,J)=\lambda/[n(1+\lambda)]$ and $P(J,I)=1/[n(1+\lambda)]$. Multiplying by $\mu(I)=\lambda^{\lvert I\rvert}/Z$ and $\mu(J)=\lambda^{\lvert I\rvert+1}/Z$ gives equal flows. Other distinct states have no direct transition unless they differ at one site. This proves reversibility and stationarity of the desired Gibbs measure.

Solved example. At activity one, order the path states as $\varnothing,\{a\},\{b\},\{c\},\{a,c\}$. The complete transition matrix is

$$P=\begin{pmatrix} 1/2&1/6&1/6&1/6&0\\ 1/6&2/3&0&0&1/6\\ 1/6&0&5/6&0&0\\ 1/6&0&0&2/3&1/6\\ 0&1/6&0&1/6&2/3 \end{pmatrix}.$$

Every row sums to one, and symmetry confirms uniform stationarity. Notice that $\{b\}$ has self-transition probability $5/6$: selecting either endpoint forces it empty and leaves the configuration unchanged. An update can be legal yet do nothing.

For probability distributions $\nu,\mu$, total variation is $\|\nu-\mu\|_{\mathrm{TV}}=\tfrac12\sum_I|\nu(I)-\mu(I)|$. Define $t_{\mathrm{mix}}(\varepsilon)$ as the least $t$ with $\max_I\|P^t(I,\cdot)-\mu\|_{\mathrm{TV}}\le\varepsilon$. Time here counts single-site updates, not complete sweeps through the graph. Numerical matrix powers give $t_{\mathrm{mix}}(1/4)=8$ for this five-state chain; the investigation labels such finite numerical results separately from general bounds.

A complete conservative coupling bound works when $\alpha=\Delta\lambda/(1+\lambda)\lt1$. Couple two chains by using the same selected vertex and uniform random number. If they differ at $D$ sites, an update removes the selected site's old disagreement; the probability of a new disagreement is at most $\lambda/(1+\lambda)$ times the number of disagreeing neighbors. Summing over the selected vertex gives

$$\mathbb E(D_{t+1}\mid X_t,Y_t)\le\left(1-\frac{1-\alpha}{n}\right)D_t.$$

Start one chain from an arbitrary state and the other in stationarity. Initially $D_0\le n$, and the coupling inequality bounds total variation by $\Pr(X_t\ne Y_t)\le\mathbb E D_t$. Hence

$$t_{\mathrm{mix}}(\varepsilon)\le\left\lceil\frac{n}{1-\alpha}\log\frac n\varepsilon\right\rceil.$$

For paths and activity $1/2$, take $\Delta=2$, giving $\alpha=2/3$. At activity one this particular criterion does not contract. It does not prove slow mixing there, nor does it give the sharp model-dependent threshold. Glauber supplies the classical dynamics background; the finite hard-core bound above is derived explicitly.

Exercise. Can stationarity alone justify taking one sample after one update from the empty state? Hint: compare the support after one step with the full support. Solution: no. The doubleton $\{a,c\}$ cannot be reached in one update, although its stationary probability is $1/5$ at activity one.

51.6 Random-cluster models

Optional extension; not required to complete the chapter foundation.

The random-cluster model puts a probability measure on edge subsets $A\subseteq E$. With $0\lt p\lt1$, cluster weight $q\gt0$, and $k(A)$ the number of connected components of the spanning graph $(V,A)$, including isolated vertices, its weight is

$$w(A)=p^{\lvert A\rvert}(1-p)^{\lvert E\rvert-\lvert A\rvert}q^{k(A)},\qquad Z_{\mathrm{RC}}=\sum_{A\subseteq E}w(A).$$

When $q=1$, this is independent bond percolation and $Z_{\mathrm{RC}}=1$. For other $q$, the component factor can couple edges, so it must not be omitted. The normalized probability is $w(A)/Z_{\mathrm{RC}}$.

Solved example. On $a-b-c$ at $p=1/2,q=2$, the empty edge set has three components and weight two; each one-edge set has two components and weight one; the two-edge set has one component and weight $1/2$. The total is $9/2$, so the four probabilities are $4/9,2/9,2/9,1/9$. Each edge is open with probability $1/3$, not $p=1/2$.

In fact, on any forest $k(A)=|V|-|A|$, so the weight factors over edges and the open edges are independent with adjusted probability $p/[p+q(1-p)]$. This explains our path example. On graphs with cycles, the component count does not obey that identity for every subset, and independence can fail.

For any graph, condition on all edges except an edge $uv$. If $u,v$ are already connected, opening it does not reduce $k$, and its conditional open probability is $p$. If they are disconnected, opening it merges two components, and its conditional open probability is $p/[p+q(1-p)]$. Comparing these two cases exposes the source of dependence.

The zero-field ferromagnetic Ising model has the exact expansion $Z_{\mathrm{Ising}}=e^{\beta|E|}Z_{\mathrm{RC}}(1-e^{-2\beta},2)$. Proof: write each edge factor as $e^\beta[(1-p)+p\mathbf1\{\sigma_u=\sigma_v\}]$, expand the product, and sum spins. Every connected component of the chosen edge set can independently take either spin, contributing $2^{k(A)}$. On $P_3$ with $\beta=\log2$, $p=3/4$ and $Z_{\mathrm{RC}}=25/8$, giving $4\cdot25/8=25/2$, as in Section 51.3.

Primary source: Fortuin and Kasteleyn, On the Random-Cluster Model90045-6). Scope: finite normalization and the zero-field expansion are proved here; infinite-volume percolation thresholds and cluster algorithms are omitted.

Exercise. Why count isolated vertices in $k(A)$? Hint: use the empty edge set. Solution: each isolated vertex still chooses its Ising spin independently, so an empty set of edges contributes $2^{|V|}$ spin assignments. Ignoring these components would break the expansion.

51.7 Phase transitions in random constraint systems

Optional extension; not required to complete the chapter foundation.

A constraint satisfaction problem has variables, allowed values, and restrictions on combinations of values. Its hard partition function counts satisfying assignments. A softened model gives a configuration with $U$ violated constraints weight $e^{-\beta U}$; at finite $\beta$ all assignments have positive weight, and as $\beta\to\infty$ only zero-violation assignments contribute to the limiting unnormalized sum. If none exists, the hard count is zero.

For random $k$-SAT on $n$ Boolean variables, take $m$ independent clauses. Each clause chooses $k$ distinct variables uniformly and independent fair literal signs. A fixed assignment violates a clause with probability $2^{-k}$, so its probability of satisfying all clauses is $(1-2^{-k})^m$. Linearity of expectation gives

$$\mathbb E Z_{\mathrm{SAT}}=2^n(1-2^{-k})^m.$$

Markov's inequality implies $\Pr(Z_{\mathrm{SAT}}\ge1)\le\mathbb E Z_{\mathrm{SAT}}$. Therefore a fixed density above $\log2/[-\log(1-2^{-k})]$ makes this upper bound exponentially small as $n$ grows. This is a sufficient unsatisfiability bound, not an equality for the actual threshold. Dependencies among assignments prevent the first moment from proving satisfiability merely because the expectation is large.

Solved finite example. With two variables $x,y$, choose each clause independently from $x\vee y$, $x\vee\neg y$, $\neg x\vee y$, $\neg x\vee\neg y$. Each clause excludes a different one of the four assignments. After four draws, unsatisfiability occurs exactly if all four clause types appear. There are $4!=24$ such ordered draws among $4^4=256$, so its probability is $3/32$. Meanwhile the expected satisfying count is $4(3/4)^4=81/64$. An expectation exceeding one plainly does not force every formula to be satisfiable.

In a growing random ensemble, satisfiability, changes in the geometry of the solution set, and algorithmic success can have distinct transitions. A finite histogram cannot establish their limiting locations. The established theorem of Ding, Sly, and Sun determines the random $k$-SAT satisfiability threshold for all sufficiently large fixed $k$. That stated range matters; it is not a theorem for every small $k$. Omitted prerequisites: the solution-cluster analysis, moment optimization, and rigorous treatment of the statistical-physics prediction. No latest small-$k$ threshold or open-status claim is needed for our finite example.

Exercise. What is the unsatisfiability probability after three draws in the two-variable model? Hint: each clause excludes only one assignment. Solution: zero, because at most three of four assignments can be excluded. Repeated clauses remove no additional assignments.

51.8 Local algorithms and limitations

Optional extension; not required to complete the chapter foundation.

A local algorithm uses information within a specified graph radius around a vertex, often together with independent random labels. Its output may aim to construct a feasible object, maximize its size, approximate a marginal, or sample a target distribution. These are different objectives. Validity of the output does not establish the target law or optimality.

Solved example: independent bits. On $P_3$, occupy each vertex independently with probability $p$. Invalidity occurs if both $a,b$ or both $b,c$ are occupied. Inclusion-exclusion gives probability $1-2p^2+p^3$ of a valid independent set. At $p=1/2$, acceptance is $5/8$. Conditioning on acceptance gives the uniform measure on the five valid sets, since the eight bit configurations initially had equal probabilities. But the validity check and rejection step are global, and long paths have acceptance $Z_n(1)/2^n$, exponentially small in $n$. A simple local proposal can lead to an inefficient exact sampler.

A radius-one feasible construction assigns independent continuous random priorities and selects every vertex whose priority is smaller than all its neighbors'. Adjacent vertices cannot both be selected because each would need a lower priority than the other. On $P_3$, each endpoint is selected with probability $1/2$ and the center with probability $1/3$, giving expected size $4/3$. The uniform hard-core mean is one. Furthermore this rule never outputs the empty set, whereas the target measure assigns it probability $1/5$. Thus it is a valid construction but not an exact Gibbs sampler. It need not produce a maximal independent set either: on a four-vertex path with priorities increasing along the path, only the first vertex is selected, and the last vertex can still be added.

These rules have $O(|V|+|E|)$ sequential work given priorities and adjacency lists; their communication radius differs from their total work. A repeated global algorithm with many local updates is not necessarily a bounded-radius algorithm. Conversely, approximate single-site marginals do not automatically specify a jointly feasible sampling law.

An established limitation for a specific model is Rahman and Virág's result on local independent-set algorithms: for factor-of-iid independent sets on the high-degree regular tree, the maximum density is asymptotically at most $(\log d)/d$. Scope: this is a theorem for that algorithmic class and asymptotic setting, not a universal barrier for all distributed, adaptive, or learned methods. Its full overlap analysis is omitted. No sharp limit for our three-vertex example is inferred from that research theorem.

Exercise. Can the priority rule on $P_3$ select both endpoints? Hint: compare each with the center. Solution: yes, whenever the center has the largest of the three priorities. That event has probability $1/3$; the uniform hard-core probability of the endpoint pair is $1/5$. Even a particular feasible output can have the wrong probability.

51.9 Spatial mixing and deterministic approximate counting

Optional extension; not required to complete the chapter foundation.

A deterministic approximation scheme for $Z$ produces a controlled multiplicative estimate without sampling. Spatial mixing can make this possible: if distant conditions matter very little, truncate a suitable recursion at bounded depth and control the resulting marginal error. The truncated object must correctly represent the original graph. A naive tree that simply ignores cycle constraints can be wrong.

Order the vertices as $v_1,\ldots,v_n$, and let $G_i$ be the graph remaining after $v_1,\ldots,v_{i-1}$ are deleted. Let $p_i$ be the occupation probability of $v_i$ in the hard-core measure on $G_i$. Since excluding a vertex leaves the measure on the graph with that vertex deleted,

$$1-p_i=\frac{Z_{G_{i+1}}}{Z_{G_i}},\qquad Z_G=\prod_{i=1}^n(1-p_i)^{-1}.$$

The product telescopes because $Z_{G_{n+1}}=1$. It also equals the reciprocal probability that all vertices are empty under successive conditional exclusions. Reusing all unconditional marginals from the original graph would not telescope.

Solved example. Delete endpoints successively on $P_3$ at activity one. The occupation probabilities are $2/5,1/3,1/2$. Therefore $Z=(1-2/5)^{-1}(1-1/3)^{-1}(1-1/2)^{-1}=5$. The center's original marginal $1/5$ does not replace the second factor: after deleting the first endpoint, its graph has changed.

Here is explicit error accounting. For any hard-core marginal, $p_i\le\lambda/(1+\lambda)$ because conditioning on neighbors either forces zero or permits that Bernoulli probability. Put $a=1/(1+\lambda)$. Suppose deterministic estimates satisfy $|\widehat p_i-p_i|\le\delta\le a/2$, and define the product using those estimates. The derivative of $-\log(1-x)$ on the interval between estimate and truth is at most $2/a$. Hence

$$|\log\widehat Z-\log Z|\le\frac{2n\delta}{a}.$$

Taking $\delta\le a\log(1+\varepsilon)/(2n)$ gives $Z/(1+\varepsilon)\le\widehat Z\le(1+\varepsilon)Z$, for $0\lt\varepsilon\le1$. The error must shrink with $n$; a fixed per-site error does not ensure a fixed multiplicative error for the full product.

For bounded-degree graphs and fixed activity strictly below the regular-tree threshold, Weitz proves a deterministic fully polynomial approximation scheme using a self-avoiding-walk tree with boundary prescriptions. Proof sketch: the representation preserves the root marginal; exponential decay permits depth $O(\log(n/\varepsilon))$; bounded branching makes the truncated computation polynomial. Omitted prerequisites: the exact cycle-closing boundary rule and uniform decay theorem. The constants depend on degree and distance from the threshold. Our path recurrence is exact at every positive activity and needs none of that representation.

Exercise. With activity one and $n=3$, choose a sufficient marginal error for multiplicative factor $1.1$. Hint: $a=1/2$ and $\varepsilon=0.1$. Solution: $\delta\le\log(1.1)/12$, approximately $0.00794$. This is a conservative sufficient precision, not a necessary one.

51.10 Statistical-mechanical approaches to combinatorial enumeration

Optional extension; not required to complete the chapter foundation.

A partition function is a generating function with a probabilistic interpretation. Coefficients count objects of a fixed size; positive activities reweight their sizes; derivatives describe typical size and fluctuations. This connects enumerative combinatorics, probability, and optimization without requiring a physical system behind every model.

Solved coefficient example. On $P_n$, an independent $k$-set has ordered positions $1\le i_1\lt\cdots\lt i_k\le n$ with consecutive gaps at least two. Set $j_t=i_t-(t-1)$. These are exactly the ordinary $k$-subsets of $\{1,\ldots,n-k+1\}$, and the transformation is reversible. Thus

$$Z_n(\lambda)=\sum_{k=0}^{\lfloor(n+1)/2\rfloor}\binom{n-k+1}{k}\lambda^k.$$

For $n=4$, the coefficients are $1,4,3$, agreeing with the deletion recurrence. At activity one, $Z_n=F_{n+2}$ for Fibonacci numbers $F_0=0,F_1=1$: both sides have the same recurrence and bases. This is exact enumeration, not an approximation obtained from Monte Carlo samples.

To study growth, solve $r^2=r+\lambda$. Its roots are $r_\pm=(1\pm\sqrt{1+4\lambda})/2$, and the recurrence solution is

$$Z_n(\lambda)=\frac{r_+^{n+2}-r_-^{n+2}}{r_+-r_-}.$$

Check the bases $Z_0=1$, $Z_1=1+\lambda$ directly. Since $|r_-|\lt r_+$ for positive finite activity, the limiting normalized log partition function is $\lim_{n\to\infty}n^{-1}\log Z_n=\log r_+$. It is analytic for $\lambda\gt0$. Thus this path family has no singularity of this pressure at a finite positive activity, despite stronger short-range dependence and slower observed updates at larger activity.

On a finite graph, as $\lambda\to\infty$ the measure concentrates on maximum independent sets: lower-degree polynomial terms become negligible after division by the leading term. This limiting fact does not supply an efficient maximum-independent-set algorithm for arbitrary graphs. Similarly, entropy is $H(\mu)=\log Z-\mathbb E|I|\log\lambda$; at activity one on $P_3$ it is $\log5$. A small entropy or a dominant term does not alone certify a fast sampler.

Broader work also studies statistical-mechanical approximations such as the Bethe approximation; a primary algorithmic analysis is Chandrasekaran, Chertkov, Gamarnik, Shah, and Shin. Scope: the formulas above are exact path calculations. No uncontrolled Bethe approximation is used to replace them, and approximation guarantees require their own model hypotheses.

Exercise. How many size-two independent sets does $P_6$ have? Hint: use the coefficient formula. Solution: $\binom52=10$. There are four size-three sets, so $Z_6(1)=1+6+10+4=21$, matching the recurrence.

Compare correlation decay, mixing, and counting on the same graph family

Use the same hard-core distribution on paths throughout. Weighted counting determines normalization and equilibrium observables; conditional marginals measure spatial influence; a fully specified transition matrix measures temporal convergence. The finite computations can be compared without conflating their units or claiming a phase transition from a small sample of sizes.

An application is probabilistic scheduling with pairwise conflicts: vertices are jobs or transmitters, edges prohibit simultaneous activity, and activity weights express preferences for occupied sites. Computing $Z$ normalizes the idealized schedule distribution; a Glauber update constructs a sampler for it; mixing controls how far a finite run can be from the intended distribution. Actual fairness or throughput objectives require additional modeling. A feasible local construction alone does not establish those equilibrium probabilities.