# Gibbs Sampler

## Problem Statement

To sample from $$p(\mathbf{x})$$ where $$\mathbf{x}$$ is a $$D$$-dimensional vector. $$p(\mathbf{x})$$ is not easy to sample from directly, but each factorized conditional distribution $$p(x_i|\mathbf{x}_{\neg i})$$, where $$\mathbf{x}_{\neg i} = (x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_D)$$, is easy to sample from.

## Gibbs Sampler

Given $$\mathbf{x}^{(t)}$$, $$\mathbf{X}^{(t+1)}$$ is generated by the following procedure: \begin{align} X_1^{(t+1)} &\sim p(x_1|x_2^{(t)}, \dots, x_D^{(t)}) \\ X_2^{(t+1)} &\sim p(x_2|x_1^{(t+1)}, x_3^{(t)}, \dots, x_D^{(t)}) \\ & \vdots \\ X_D^{(t+1)} &\sim p(x_D|x_1^{(t+1)}, \dots, x_{D-1}^{(t+1)}) \end{align}

## Irreducibility of Gibbs Sampler

The Gibbs sampler might not always be irreducible for a given state distribution $$p(\mathbf{x})$$. A counterexample is given in "Monte Carlo Statistical Methods", Example 7.1.10.1 A sufficient condition for the chain to be irreducible is the positivity condition:

Let $$(X_1, \dots, X_D) \sim p(x_1, \dots, x_D)$$, where $$p_i$$ denotes the marginal distribution of $$X_i$$. If $$p_i(x_i) > 0$$ for all $$i = 1,\dots,D$$ implies that $$p(x_1,\dots,x_D) > 0$$, then $$p$$ satisfies the positivity condition.

And we further have:

Gibbs sampler derived from $$p$$ satisfying the positivity condition is irreducible.

1. Robert, C. P., & Casella, G. (2005). Monte Carlo Statistical Methods (Springer Texts in Statistics). Secaucus, NJ, USA: Springer-Verlag New York, Inc.↩︎