Currently, I am going through Chapter 12.3 of Probabilistic Graphical Models - Principles and Techniques which talks about MCMC sampling methods. In Chapter, it states the following theorem:

If $\mathcal{T}$ is regular and it satisfies the detailed balance equation relative to $\pi$, then $\pi$ is the unique stationary distribution of $\mathcal{T}$.

Now suppose that a regular MC does satisfy the detailed balance equation relative to $p(\mathbf{x})$. Therefore, according to the theorem, it has the unique stationary distribution $p(\mathbf{x})$. My question is, how to prove that the Gibbs sampling will converge to that stationary distribution? I am pretty sure that updating each element of $\mathbf{x}$ is vital, but I don't know why it is related to convergence. For example, if I only update $x_1,x_2$, it is obvious that I won't converge to $p(\mathbf{x})$.

Hints and references are highly appreciated!

Thanks again for all comments. Let me give an more detailed example here, the traditional Gibbs Sampling works as follows for $(x_1,x_2,\cdots,x_n)$ (assume that the MC is regular):

  • Init $(x_1,x_2,\cdots,x_n)$
  • For each sweep
    • For $i=1,2,\cdots,n$
      • Sample $x_i$ from $p(x_i|x_{-i})$

Now, I have a wrong algorithm, name it as the stupid algorithm:

  • Init $(x_1,x_2,\cdots,x_n)$
  • For each sweep
    • Sample $x_1$ from $p(x_1|x_{-1})$
    • Sample $x_2$ from $p(x_2|x_{-2})$

However, the stupid algorithm still has the same detailed balance equation relative to $p(\mathbf{x})$ as the Gibbs Sampling. What makes the difference between this stupid algorithm and the Gibbs Sampling? From intuition, it is because the stupid algorithm is not able to update any elements other than $x_1,x_2$ (but I am not so sure about this).

OK, if I understand one comment correctly, one sweep of Gibbs may not satisfy detailed balance while one component-wise move does. Therefore I cannot prove the correctness of Gibbs from detailed balance relationship ... (I hope that I am correct this time).

  • 1
    $\begingroup$ Maybe you can take a look at the discussion in stats.stackexchange.com/questions/118442/… $\endgroup$
    – Peter Pang
    Mar 14 at 16:50
  • 2
    $\begingroup$ Provided the Markov chain is irreducible (which is guaranteed by regularity) and aperiodic (which is guaranteed by a skeleton version of the chain), the existence of the stationary distribution implies ergodicity and hence convergence for almost every starting value. $\endgroup$
    – Xi'an
    Mar 14 at 17:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.