Gibbs Sampling for Discrete Graphical Models

From Ising interactions to a local update

In a discrete graphical model, the joint distribution can involve many variables, but the conditional distribution of one variable may depend only on its immediate neighbors. This locality is what makes single-site Gibbs sampling practical: at each step, one spin is redrawn from a two-point conditional distribution rather than from the full joint distribution. The update probability is not guessed from the graph; it follows by holding all other spins fixed and comparing the two possible joint weights.

Let \(G=(V,E)\) be a finite undirected graph, with spin \(x_i\in\{-1,+1\}\) at each vertex \(i\). For each edge \(\{i,j\}\in E\), let \(K_{ij}=K_{ji}\) be a real interaction parameter, and let \(b_i\) be a real external-field parameter at vertex \(i\). The target distribution on configurations \(x=(x_i)_{i\in V}\) is

Here \(Z\) is the normalizing constant. It is a finite sum of positive terms, so it is finite and strictly positive. In the common parametrization \(K_{ij}=\beta J_{ij}\) and \(b_i=\beta h_i\), \(\beta\) is inverse temperature, \(J_{ij}\) is the edge coupling, and \(h_i\) is the field. Positive \(K_{ij}\) favors matching spins; negative \(K_{ij}\) favors opposite spins.

Because every configuration has positive target probability, the conditional distribution given any fixed \(x_{-i}\) is well-defined. Only terms in the exponent involving \(x_i\) matter: terms involving no \(x_i\) are the same for both possible values and cancel in the conditional normalization.

Proof. Fix the values \(x_{-i}\). In the joint exponent, the terms that depend on \(x_i\) are \(x_i b_i+\sum_{j:\{i,j\}\in E}K_{ij}x_ix_j=x_iH_i(x)\). All remaining terms have a common value, say \(C\), for the two choices of \(x_i\). Thus the unnormalized weights for \(x_i=+1\) and \(x_i=-1\) are respectively \(\exp(C+H_i(x))\) and \(\exp(C-H_i(x))\). Dividing the first by their sum cancels \(\exp(C)\) and gives \(\exp(H_i)/(\exp(H_i)+\exp(-H_i))\). Multiplying numerator and denominator by \(\exp(H_i)\) gives \(1/(1+\exp(-2H_i))\). The probability for \(-1\) is the other normalized weight, equivalently \(1/(1+\exp(2H_i))\). The two probabilities are positive and sum to one, including when \(H_i=0\). \(\square\)

The formula uses the sum of the neighboring spins weighted by their interactions, not the number of neighbors alone. If \(i\) has no neighbors, the sum is empty and equals zero, so the conditional depends only on \(b_i\). With zero field and zero neighbor contribution, each spin value has probability one-half.

Exact calculations on small graphs

Enumeration is a useful verification tool for small graphs, but it scales poorly: a graph with \(|V|\) vertices has \(2^{|V|}\) configurations. The conditional formula instead requires only the neighboring spins and the incident edge parameters. The following example also checks how a single-site update relates to the full target, without needing to compute its normalizing constant.

Why the fixed-site update preserves the target

The local conditional calculation does more than produce plausible draws. A Gibbs update at any fixed vertex preserves the joint target distribution. The claim concerns one update kernel; it does not assert that a particular update schedule converges, nor does it address how update order affects sampling.

Proof. If \(x\) and \(y\) differ at any vertex other than \(i\), then \(K_i(x,y)=0\), because the update changes no other coordinate. For configurations that agree away from \(i\), \(K_i(x,y)=\pi(y_i\mid x_{-i})\). Fix \(y\). In the sum \(\sum_x\pi(x)K_i(x,y)\), only configurations \(x\) with \(x_{-i}=y_{-i}\) contribute. For each such \(x\), the conditional probability of producing \(y_i\) is \(\pi(y_i\mid y_{-i})\), independent of \(x_i\). Therefore \(\sum_x\pi(x)K_i(x,y)=\pi(y_i\mid y_{-i})\sum_{x:x_{-i}=y_{-i}}\pi(x)\). The sum on the right is the marginal probability \(\pi(X_{-i}=y_{-i})\). By the definition of conditional probability, its product with \(\pi(y_i\mid y_{-i})\) equals \(\pi(y)\). This proves the assertion for every \(y\). \(\square\)

In the Ising examples, strict positivity follows because every exponential weight is positive and the normalizer is finite. The theorem therefore applies without excluding any spin configuration. It also explains why the update must use the conditional from the target itself: replacing it with an unrelated probability need not preserve \(\pi\).

A common calculation error

Pitfall: forgetting that conditional odds compare two weights. In the path example with both endpoint spins \(+1\), the center local field is \(2\log 2\). A common wrong calculation is to set the probability of \(+1\) equal to \(\exp(H_2)=4\). That is not a probability, and it also misses the weight for the alternative spin. The correct weights are \(\exp(H_2)=4\) and \(\exp(-H_2)=1/4\); hence the conditional probability is \(4/(4+\tfrac14)=16/17\). Equivalently, the odds are \(\exp(2H_2)=16\), so the probability is \(16/(1+16)=16/17\). Both forms give the same result.

For practical calculations, first isolate all terms involving the updated spin, then evaluate the local field, and finally normalize the two weights. Keep the distinction between a configuration’s unnormalized joint weight and a conditional probability explicit. For a small graph, direct enumeration provides an independent check; for a larger graph, the same local calculation remains valid even when enumerating the joint target is infeasible.