9
$\begingroup$

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

enter image description here

$\endgroup$
  • 2
    $\begingroup$ What would happen in Metropolis-Hastings if $p(x*)/p(x)$ was always 1? $\endgroup$ – Glen_b Jul 27 '13 at 1:00
6
$\begingroup$

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 except 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!

enter image description here

$\endgroup$
  • 1
    $\begingroup$ I didn't get it how come everything cancels out. Well lets say we have to sample from the distribution $p(\theta)$ of 3 variables. So when you meant to say full conditionals in closed form expression you mean p(x1|x2,x3) p(x2|x1,x3) and p(x3|x1,x2). My question is in the case of Gibbs sampling we do know the conditional distribution obtained from the actual distribution p from which we want to sample. Is that what you mean. In the case of Metropolis algorithm we don't know p but something like c such that p(x) = c(x)/Z?? $\endgroup$ – user34790 Jul 26 '13 at 22:44
  • $\begingroup$ Suppose we start with random values for the variables x1,x2 and x3 how can we say that its stationary distribution converges the required one. What is the criteria for that? $\endgroup$ – user34790 Jul 26 '13 at 22:47
  • $\begingroup$ Suppose I have a distribution $p(\theta) = c(\theta)/Z$. I don't know Z. So how would I sample from $p(\theta)$ using Gibbs sampling $\endgroup$ – user34790 Jul 26 '13 at 23:20
  • 3
    $\begingroup$ I added a proof above of why its always one. To use Gibbs sampling you need to know what the full conditionals are. $\endgroup$ – user25658 Jul 27 '13 at 0:33
1
$\begingroup$

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

$\endgroup$

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.