Hammersley–Clifford theorem

Remarks

That 2 implies 1 is direct. Let $S$ separate $A$ from $B$, and enlarge $A$ and $B$ so that $A \cup B \cup S = V$ while $S$ still separates them. No clique meets both $A$ and $B$, so each clique lies in $A \cup S$ or in $B \cup S$. So $p$ is a function of $(x_A, x_S)$ times a function of $(x_B, x_S)$, which gives $X_A \perp X_B \mid X_S$. For 1 implies 2, one writes $\log p$ as a sum of terms indexed by the subsets of $V$, by Möbius inversion. The pairwise Markov property then shows that the terms of the non-cliques vanish. This second step needs positivity, since it takes logarithms and divides by $p$. The direction 2 implies 1 holds without positivity, but the direction 1 implies 2 can fail. There are Markov random fields with zero probabilities on a cycle of four vertices that do not factorise over the cliques.

Example: for the Ising model on $G$, $p(x) \propto \exp\bigl(\beta \sum_{\set{u, v} \in E} x_u x_v + h \sum_v x_v\bigr)$ with $x_v \in \set{-1, 1}$. This is a product of positive factors on edges and vertices, which are cliques, so the Ising model is a Markov random field.

Going deeper

For a student

The theorem is why Markov random fields are written as Gibbs distributions $p(x) \propto \exp(-\sum_C V_C(x_C))$ with clique potentials $V_C$. Conversely, any such energy defines a Markov random field, and in Gibbs sampling the update of $x_v$ then depends only on the neighbours of $v$. The same statement holds for positive densities with respect to a product measure, for example for Gaussian graphical models. There the missing edges of the graph are the zero entries of the inverse covariance matrix. For directed graphs, the analogous factorisation is the definition of a Bayesian network.