The Gibbs sampler has its origin in digital image processing and was introduced by Geman and Geman in 1984 for the Gibbs distribution. It was only in 1990 that Gelfand and Smith discovered that the Gibbs sampler works for other distributions as well.

The general idea of the Gibbs sampler is to approximate the modes and marginal distributions of an unknown distribution p(ω), where ω = (ω₁,…,ω_n), by successively taking samples from the known conditional distributions p_i = p(ω_i|ω_j, j≠i).

The actual algorithm works as follows:

1. Set j = 0 and set initial values ω⁽⁰⁾ = (ω₁⁽⁰⁾,…,ω_n⁽⁰⁾).
2. For 1 ≤ i ≤ n obtain samples ω_i^(j) ∼ p(ω₁|ω₁^(j),…,ω_i−1^(j),ω_i+1^(j−1),…,ω_n^(j−1)) from the conditional distributions and, therefore, a new value ω^(j).
3. Increase j by 1 and continue with step 2.

Since the new values depend only on the immediately preceding ones, we clearly have a Markov process.

The Gibbs sampler was first used in digital image processing, an application we look at in sections 2 and 5.

In section 3 we will look at Markov random fields and Gibbs distributions and see how they are related to each other. The most important result in this section is that they are in fact equivalent.

We will see in section 4 that the Gibbs sampler converges to the unknown joint distribution p(ω), and we will introduce the process of annealing, that is, gradually reducing the temperature of the system to speed up convergence.

In section 6 we will generalise the results from section 4 and show that the Gibbs sampler works for other distributions as well. We will introduce two other related algorithms, the data-augmentation algorithm, which approximates the joint distribution given the conditional distributions, and the substitution sampling algorithm, which is very close related to the Gibbs sampler.

• Monte Carlo Markov Chain Methods (PDF)
• The Genetic Linkage Example (R)
• The Coal-Mining Disasters Example (R)

Literature

• J. Bernardo, J. Berger, A. Dawid and A. Smith, Bayesian Statistics 4 (Oxford University Press 1992)
• D. Gamerman, Markov Chain Monte Carlo (Chapman & Hall 1997)
• W. Kennedy and J. Gentle, Statistical Computing (Dekker 1980)
• R. Kindermann and J. Snell, Markov Random Fields and their Applications (American Mathematical Society 1980)
• P. Lee, Bayesian Statistics (Arnold 1997)
• C. Preston, Gibbs States on Countable Sets (Cambridge University Press 1974)

MMath Project, University of York, 2001