Assume we want to sample from the variables of Bayesian belief network, which is a Directed Acyclic Graph (DAG), where we observe some of the variables, and do not observe the others. We can usually do Gibbs sampling since the probability of a variable conditional on the others can be easily computed.

However, I am asked:

When is using Gibbs sampling to simulate from a DAG given the observed values at a subset of nodes is not appropriate? Can you see the reason?

I believe this has to be something about the convergence of Markov chain, but I can't see why. Is it because when we know some of the variables it can result in the underlying Markov chain not to be stable? We know that the limit exists when the underlying chain is aperiodic, so maybe when we fix some observed variables we have periods.

One explanation I have is: suppose a variable has many parent nodes, and no child. It will take too much time for this node to change its state since at each step we change only one variable and this will have too little effect considering that this node has a lot of parent nodes...


One particular problem you may run into is when your joint distribution is separated by regions of zero probability. Consider a bivariate distribution you are trying to sample from. Conditioning on one variable and sampling the other means you can only propose values in one dimension at a time. Consequently (as seen in the picture), your sampler will not be able to reach the other mode to sample.

a bivariate distribution with separated by regions of 0 density.

The red lines indicate the paths of your Gibbs sampler.

Below is a discrete example taken directly from Wikipedia's article on Gibbs sampling:

There are two ways that Gibbs sampling can fail. The first is when there are islands of high-probability states, with no paths between them. For example, consider a probability distribution over 2-bit vectors, where the vectors (0,0) and (1,1) each have probability ½, but the other two vectors (0,1) and (1,0) have probability zero. Gibbs sampling will become trapped in one of the two high-probability vectors, and will never reach the other one. More generally, for any distribution over high-dimensional, real-valued vectors, if two particular elements of the vector are perfectly correlated (or perfectly anti-correlated), those two elements will become stuck, and Gibbs sampling will never be able to change them.

| cite | improve this answer | |
  • $\begingroup$ This condition has however nothing to do with the DAG structure. $\endgroup$ – Xi'an Feb 11 at 10:28
  • $\begingroup$ @Xi'an thanks for pointing that out. To follow-up on this, do Markov random fields share this problem? I think MRFs do not run into this mode of failure because their conditionals take the form of a Gibbs distribution (i.e., all positive probabilities). $\endgroup$ – fool126 Feb 11 at 18:49

Your Answer

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

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