Hammersley–Clifford theorem
Encyclopedia
The Hammersley–Clifford theorem is a result in probability theory
, mathematical statistics
and statistical mechanics
, that gives necessary and sufficient conditions under which a positive probability distribution
can be represented as a Markov network
(also known as a Markov random field). It states that a probability distribution that has a positive mass
or density
satisfies one of the Markov properties with respect to an undirected graph G if and only if it is a Gibbs random field, 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 and Frank Spitzer
in the context of statistical mechanics
. The theorem is named after John Hammersley
and Peter Clifford who proved the equivalence in an unpublished paper in 1971. Simpler proofs using the inclusion-exclusion principle
were given independently by Geoffrey Grimmett
, Preston and Sherman in 1973, with a further proof by Julian Besag
in 1974.
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, mathematical statistics
Mathematical statistics
Mathematical statistics is the study of statistics from a mathematical standpoint, using probability theory as well as other branches of mathematics such as linear algebra and analysis...
and statistical mechanics
Statistical mechanics
Statistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...
, that gives necessary and sufficient conditions under which a positive probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
can be represented as a Markov network
Markov network
A Markov random field, Markov network or undirected graphical model is a set of variables having a Markov property described by an undirected graph. A Markov random field is similar to a Bayesian network in its representation of dependencies...
(also known as a Markov random field). It states that a probability distribution that has a positive mass
Probability mass function
In probability theory and statistics, a probability mass function is a function that gives the probability that a discrete random variable is exactly equal to some value...
or density
Probability density function
In probability theory, a probability density function , or density of a continuous random variable is a function that describes the relative likelihood for this random variable to occur at a given point. The probability for the random variable to fall within a particular region is given by the...
satisfies one of the Markov properties with respect to an undirected graph G if and only if it is a Gibbs random field, that is, its density can be factorized over the cliques (or complete subgraphs
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
) of the graph.
The relationship between Markov and Gibbs random fields was initiated by Roland Dobrushin and Frank Spitzer
Frank Spitzer
Frank Ludvig Spitzer was an Austrian-born American mathematician who made fundamental contributions to probability theory, including the theory of random walks, fluctuation theory, percolation theory, the Wiener sausage, and especially the theory of interacting particle systems...
in the context of statistical mechanics
Statistical mechanics
Statistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...
. The theorem is named after John Hammersley
John Hammersley
John Michael Hammersley was a British mathematician best known for his foundational work in the theory of self-avoiding walks and percolation theory. He was born in Helensburgh in Dunbartonshire, and educated at Sedbergh School. He started reading mathematics at Emmanuel College, Cambridge but was...
and Peter Clifford who proved the equivalence in an unpublished paper in 1971. Simpler proofs using the inclusion-exclusion principle
Inclusion-exclusion principle
In combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...
were given independently by Geoffrey Grimmett
Geoffrey Grimmett
Geoffrey Richard Grimmett is a mathematician working in probability theory. He is the Professor of Mathematical Statistics in the Statistical Laboratory, University of Cambridge....
, Preston and Sherman in 1973, with a further proof by Julian Besag
Julian Besag
Julian Ernst Besag FRS was a British statistician known chiefly for his work in spatial statistics , and Bayesian inference .- Biography:Besag was born in Loughborough and was educated at Loughborough Grammar School...
in 1974.