The Hammersley–Clifford theorem is a result in
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
,
mathematical statistics
Mathematical statistics is the application of probability theory, a branch of mathematics, to statistics, as opposed to techniques for collecting statistical data. Specific mathematical techniques which are used for this include mathematical an ...
and
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
that gives necessary and sufficient conditions under which a strictly positive
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
(of events in a
probability space
In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models t ...
) can be represented as events generated by a
Markov network
In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to ...
(also known as a
Markov random field
In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to b ...
). It is the fundamental theorem of random fields. It states that a probability distribution that has a strictly positive
mass
Mass is an intrinsic property of a body. It was traditionally believed to be related to the quantity of matter in a physical body, until the discovery of the atom and particle physics. It was found that different atoms and different elementar ...
or
density
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematical ...
satisfies one of the
Markov properties with respect to an undirected graph ''G'' if and only if it is a
Gibbs random field In mathematics, the Gibbs measure, named after Josiah Willard Gibbs, is a probability measure frequently seen in many problems of probability theory and statistical mechanics. It is a generalization of the canonical ensemble to infinite systems. ...
, that is, its density can be factorized over the cliques (or
complete subgraphs) of the graph.
The relationship between Markov and Gibbs random fields was initiated by
Roland Dobrushin
Roland Lvovich Dobrushin (russian: Рола́нд Льво́вич Добру́шин) (July 20, 1929 – November 12, 1995) was a mathematician who made important contributions to probability theory, mathematical physics, and information theory. ...
and
Frank Spitzer
Frank Ludvig Spitzer (July 24, 1926 – February 1, 1992) was an Austrian-born American mathematician who made fundamental contributions to probability theory, including the theory of random walks, fluctuation theory, percolation theory, the W ...
in the context of
statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...
. The theorem is named after
John Hammersley
John Michael Hammersley, (21 March 1920 – 2 May 2004) was a British mathematician best known for his foundational work in the theory of self-avoiding walks and percolation theory.
Early life and education
Hammersley was born in Helensburgh i ...
and
Peter Clifford, who proved the equivalence in an unpublished paper in 1971.
Simpler proofs using the
inclusion–exclusion principle
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
: , A \cup ...
were given independently by
Geoffrey Grimmett
Geoffrey Richard Grimmett (born 20 December 1950) is a mathematician known for his work on the mathematics of random systems arising in probability theory and statistical mechanics, especially percolation theory and the contact process. He is ...
, Preston and Sherman in 1973, with a further proof by
Julian Besag
Julian Ernst Besag FRS (26 March 1945 – 6 August 2010) was a British statistician known chiefly for his work in spatial statistics (including its applications to epidemiology, image analysis and agricultural science), and Bayesian inferenc ...
in 1974.
Proof outline
![A_simple_Markov_network](https://upload.wikimedia.org/wikipedia/commons/7/7b/A_simple_Markov_network.png)
It is a trivial matter to show that a Gibbs random field satisfies every
Markov property
In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It is named after the Russian mathematician Andrey Markov. The term strong Markov property is similar to the Markov propert ...
. As an example of this fact, see the following:
In the image to the right, a Gibbs random field over the provided graph has the form
. If variables
and
are fixed, then the global Markov property requires that:
(see
conditional independence
In probability theory, conditional independence describes situations wherein an observation is irrelevant or redundant when evaluating the certainty of a hypothesis. Conditional independence is usually formulated in terms of conditional probabil ...
), since
forms a barrier between
and
.
With
and
constant,
where
and
. This implies that
.
To establish that every positive probability distribution that satisfies the local Markov property is also a Gibbs random field, the following lemma, which provides a means for combining different factorizations, needs to be proved:
![Merging_two_factorizations_of_a_positive_mass_function](https://upload.wikimedia.org/wikipedia/commons/f/f7/Merging_two_factorizations_of_a_positive_mass_function.png)
Lemma 1
Let
denote the set of all random variables under consideration, and let
and
denote arbitrary sets of variables. (Here, given an arbitrary set of variables
,
will also denote an arbitrary assignment to the variables from
.)
If
for functions
and
, then there exist functions
and
such that
In other words,
provides a template for further factorization of
.
In order to use
as a template to further factorize
, all variables outside of
need to be fixed. To this end, let
be an arbitrary fixed assignment to the variables from
(the variables not in
). For an arbitrary set of variables
, let