Confusion related to Gibbs sampling

Question

I came across this article where it says that in Gibbs sampling every sample is accepted. I am a bit confused. How come if every sample it accepted it converges to a stationary distribution.

In general Metropolis Algorithm we accept as min(1, p(x*)/p(x)) where x* is the sample point. I assume that x* points us to a position where the density is high so we are moving to the target distribution. Hence I suppose that it moves to the target distribution after a burn in period.

However, in Gibbs sampling we accept everything so even though it may take us to a different place, how can we say that it converges to the stationary/target distribution

Suppose we have a distribution $p(\theta) = c(\theta)/Z$. We cannot calculate Z. In metropolis algorithm we use the term $c(\theta^{new})/c(\theta^{old})$ to incorporate the distribution $c(\theta)$ plus the normalizing constant Z cancels out. So it's fine

But in Gibbs sampling where are we using the distribution $c(\theta)$

For eg in the paper http://books.nips.cc/papers/files/nips25/NIPS2012_0921.pdf its given

so we don't have the exact conditional distribution to sample from, we just have something that is directly proportional to the conditional distribution

Answer 1

When we use the Metropolis-Hastings algorithm we have to compute an acceptance ratio $$\alpha=\min(1,\frac{p(x^*)}{p(x)})$$ and let the random variable $U\sim\text{Uniform(0,1)}$ then we accept the random variable if $U<\alpha$.

However, in Gibbs sampling we always accept the random variable because we do not have to calculate the acceptance ratio (well you actually do but when you plug things in you see that everything cancels out and your acceptance ratio is $\alpha=1$ and so clearly $U$ is always less than $\alpha$ and because of that you are always accepting). However, you can also think of it intuitively where in Gibbs sampling you are sampling from the full conditionals which is a closed form expression that we can sample from directly and so there is no need to reject samples like in the Metropolis-Hastings algorithm where we do not know how to sample from (or usually don't recognize the form of) $p(x)$. Hope that helps!

Answer 2

The proof that the acceptance rate is equal to 1 as a typo i.e. in the denominator in the middle and third part the expression for q should have z_i prime, so that in the end you get P(z_i prime|z_i prime).

Alex