Gibbs sampling

Under modification by User:dkulkarn

Gibbs sampling is used to sample from the stable joint distribution of two or more random variables when accurate computation of the integral or a marginal is intractable. Usually some variables in this set of random variables are the actual observables and hence there values need not be sampled in the Gibbs sampling iterations. This form of approximate inference method is generally used when doing posterior probability inference in probabilistic graphical models where computation of marginals are intractable.

Motivation

Gibbs sampling was introduced in the context of image processing by Geman and Geman[1]. The Gibbs sampler is a technique for generating random variables from a (marginal) distribution indirectly, without having to calculate the density[2]. Thus, if we are given with conditional densities $f(x_{i}|x_{(-i)})=f(x_{i}|x_{1},\cdots ,x_{i-1},x_{i+1},\cdots ,x_{K})$, we can use Gibbs sampling to calculate the marginal distributions $f(x_{i})$ or any other function of $x_{i}$.

Algorithm

1. Take some initial values $X_{k}^{(0)},k=1,2,\cdots ,K.$

2. Repeat for $t=1,2,\cdots ,$:

 For $k=1,2,\cdots ,K{\mbox{ generate }}X_{k}^{(t)}{\mbox{ from }}f(X_{k}^{(t)}|X_{1}^{(t)},\cdots ,X_{k-1}^{(t)},X_{k+1}^{(t-1)},\cdots X_{K}^{(t-1)}$

3. Continue step 2 until joint distribution of $(X_{1}^{(t)},\cdots ,X_{K}^{(t)})$ doesn't change.

References

1. Geman and Geman

2. http://biostat.jhsph.edu/~mmccall/articles/casella_1992.pdf