Gibbs Sampling

In M-H sampling, $X$ can be updated one component at a time, so that each iteration will take $K$ steps each for one of the $K$ components of $X$. In this case, all distributions in the expression for the acceptance probablity are for the i-th component $x_i$ of the random vector $X$ conditioned on the remaining $K-1$ components:

$$p(x_i\vert X_{-i})=\frac{p(X)}{p(X_{-i})}=\frac{p(X)}{\int p(X) dx_i}$$

where

$$X_{-i}=(x_1,\cdots,x_{i-1},x_{i+1},\cdots,x_K)^T$$

contains all the components except the i-th one. Moreover, the proposal distribution in the i-th step of the t-th iteration becomes

$$q(y_i\vert x_i^t,X_{-i}^t)$$

where $X_{-i}^t=(x_1^{t+1},\cdots,x_{i-1}^{t+1},x_{i+1}^t,\cdots,x_K^t)$ with its first $i-1$ components updated while the rest not. The probability for acceptance is

$$\alpha(x_i, y_i, X_{-i})=min(1, \frac{p(y_i\vert X_{-i})q(x_i\vert y_i,X_{-i})} {p(x_i\vert X_{-i})q(y_i\vert,x_i,X_{-i})}$$

In particular, if the proposal distribution $q(y_i\vert x_i,X_{-i})$ is chosen to be just the same as $p(x_i\vert X_{-i})$, i.e.,

$$q(y_i\vert x_i,X_{-i})=p(y_i\vert X_{-i})$$

then the second term in the expression for the acceptance probability becomes 1 and the sample generated by the proposal distribution is always accepted. This particular version of the M-H method is the Gibbs sampling, based on the assumption that the conditional distribution $p(x_i\vert X_{-i})=p(x_i\vert X_{-i}$ is simple enough to draw samples from directly, although the whole distribution $p(X)$ in $K$ dimensional space is too complex to sample. The iteration in Gibbs sampling in a $K$ dimensional space can be illustrated as this:

$$\begin{array}{c} x_1^{t+1} \sim p(x_1\vert x_2^t,\cdots,x_K) ... ...x_3\vert x_1^{t+1},x_2^{t+1},x_4^t,\cdots,x_K) \\ \end{array}$$

Gibbs sampling can be best illustrated in 2D space where the above iteration becomes alternating sampling between the horizontal direction for $x_1$ and the vertical direction for $x_2$. For example, if $p(X)$ is a 2D Gaussian, then the iteration will keep sampling the two 1D Gaussians $p(x_1\vert x_2)$ and $p(x_2\vert x_1)$ alternatively along the sequence of $x_1^t,x_2^t,x_1^{t+1},x_2^{t+1},\cdots$.