28
$\begingroup$

I have it on supreme authority1 that Gibbs Sampling is a special case of the Metropolis-Hastings algorithm for Markov Chain Monte Carlo sampling. The MH algorithm always gives a transition probability with the detailed balance property; I expect Gibbs should too. So where in the following simple case have I gone wrong?

For target distribution $\pi(x, y)$ on two discrete (for simplicity) variables, the full conditional distributions are: $$ \begin{align} q_1 (x;y) & =\frac{\pi (x,y)}{\sum_z \pi (z,y)} \\ q_2 (y;x) & =\frac{\pi (x,y)}{\sum_z \pi (x,z)} \end{align} $$

As I understand Gibbs Sampling, the transition probability can be written: $$ Prob\{(y_1, y_2) \to (x_1, x_2)\} = q_1(x_1; y_2) q_2(x_2; x_1) $$

The question is, does $$ \pi(y_1,y_2) Prob\{(y_1, y_2) \to (x_1, x_2)\} \overset{?}{=} \pi(x_1,x_2) Prob\{(x_1, x_2) \to (y_1, y_2)\}, $$ but the closest I can get is $$ \begin{align} \pi(y_1,y_2) Prob\{(y_1, y_2) & \to (x_1, x_2)\} \\ & = \pi(y_1, y_2) q_2(x_2; x_1) q_1(x_1; y_2) \\ & = \frac{\pi(x_1, x_2)}{\sum_z \pi(x_1,z)}\frac{\pi(x_1, y_2)}{\sum_z \pi(z, y_2)}\pi (y_1, y_2) \\ & = \pi(x_1, x_2) q_2(y_2; x_1) q_1(y_1; y_2) \end{align} $$ That's subtly different, and does not imply detailed balance. Thanks for any thoughts!

$\endgroup$

1 Answer 1

24
$\begingroup$

You tried to show detailed balance for the Markov chain that is obtained by considering one transition of the Markov chain to be the 'Gibbs sweep' where you sample each component in turn from its conditional distribution. For this chain, detailed balance is not satisfied. The point is rather that each sampling of a particular component from its conditional distribution is a transition that satisfies detailed balance. It would be more accurate to say that Gibbs sampling is a special case of a slightly generalized Metropolis-Hastings, where you alternate between multiple different proposals. More details follow.

The sweeps do not satisfy detailed balance

I construct a counterexample. Consider two Bernoulli variables ($X_1,X_2$), with probabilities as shown in the following table: \begin{equation} \begin{array}{ccc} & X_2 = 0 & X_2 = 1 \\ X_1 = 0 & \frac{1}{3} & \frac{1}{3} \\ X_1 = 1 & 0 & \frac{1}{3} \end{array} \end{equation} Assume the Gibbs sweep is ordered so that $X_1$ is sampled first. Moving from state $(0,0)$ to state $(1,1)$ in one move is impossible, since it would require going from $(0,0)$ to $(1,0)$. However, moving from $(1,1)$ to $(0,0)$ has positive probability, namely $\frac{1}{4}$. Hence we conclude that detailed balance is not satisfied.

However, this chain still has a stationary distribution that is the correct one. Detailed balance is a sufficient, but not necessary, condition for converging to the target distribution.

The component-wise moves satisfy detailed balance

Consider a two-variate state where we sample the first variable from its conditional distribution. A move between $(x_1,x_2)$ and $(y_1,y_2)$ has zero probability in both directions if $x_2 \neq y_2$ and thus for these cases detailed balance clearly holds. Next, consider $x_2 = y_2$: \begin{equation} \pi(x_1,x_2) \mathrm{Prob}((x_1,x_2) \rightarrow (y_1,x_2)) = \pi(x_1,x_2)\,p(y_1 \mid X_2 = x_2) = \pi(x_1,x_2) \, \frac{\pi(y_1,x_2)}{\sum_z \pi(z,x_2)} \\ = \pi(y_1,x_2) \, \frac{\pi(x_1,x_2)}{\sum_z \pi(z,x_2)} = \pi(y_1,x_2) \,p(x_1 \mid X_2 = x_2) = \pi(y_1,x_2) \mathrm{Prob}((y_1,x_2) \rightarrow (x_1,x_2)). \end{equation}

How the component-wise moves are Metropolis-Hastings moves?

Sampling from the first component, our proposal distribution is the conditional distribution. (For all other components, we propose the current values with probability $1$). Considering a move from $(x_1, x_2)$ to $(y_1, y_2)$, the ratio of target probabilities is \begin{equation} \frac{\pi(y_1,x_2)}{\pi(x_1,x_2)}. \end{equation} But the ratio of proposal probabilities is \begin{equation} \frac{\mathrm{Prob}((y_1,x_2) \rightarrow (x_1,x_2))}{\mathrm{Prob}((x_1,x_2) \rightarrow (y_1,x_2))} = \frac{\frac{\pi(x_1,x_2)}{\sum_z \pi(z,x_2)}}{\frac{\pi(y_1,x_2)}{\sum_z \pi(z,x_2)}} = \frac{\pi(x_1,x_2)}{\pi(y_1,x_2)}. \end{equation} So, the ratio of target probabilities and the ratio of proposal probabilities are reciprocals, and thus the acceptance probability will be $1$. In this sense, each of the moves in the Gibbs sampler are special cases of Metropolis-Hastings moves. However, the overall algorithm viewed in this light is a slight generalization of the typically presented Metropolis-Hastings algorithm in that you have alternate between different proposal distributions (one for each component of the target variable).

$\endgroup$
5
  • $\begingroup$ Great answer, thanks (minor edit: y_2 -> x_2 in your third section). When calling the Gibbs sweep one step, is the existence of the stationary distribution (along with irreducibility and recurrence) a sufficient condition for convergence to the stationary distribution from any initial state? $\endgroup$
    – Ian
    Commented Oct 9, 2014 at 16:51
  • 7
    $\begingroup$ The Gibbs sampler is a composition of Metropolis-Hastings moves with acceptance probability 1. Each move is reversible but the composition is not, unless the order of the steps is random. $\endgroup$
    – Xi'an
    Commented Nov 21, 2014 at 7:24
  • $\begingroup$ Could you explain more why $Prob((x_1,x_2) \rightarrow (y_1, x_2)) = \frac{\pi(y_1, x_2)}{\sum_{z}\pi(z, x_2)}$? For me, the right equation looks like considring transitions from other states. For example, $(z_1, x_2) \rightarrow (y_1, x_2)$. I think the transition we want is just $(x_1,x_2) \rightarrow (y_1, x_2)$. $\endgroup$
    – shashack
    Commented Jul 15, 2021 at 2:15
  • $\begingroup$ @Xi'an is there a proof that shows the random Gibbs-sampler is reversible? $\endgroup$
    – xabush
    Commented Jul 26, 2023 at 11:54
  • $\begingroup$ @xabush: yes, by detailed balance $\endgroup$
    – Xi'an
    Commented Jul 26, 2023 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.