Where do the full conditionals come from in Gibbs sampling?

MCMC algorithms like Metropolis-Hastings and Gibbs sampling are ways of sampling from the joint posterior distributions.

I think I understand and can implement metropolis-hasting pretty easily--you simply choose starting points somehow, and 'walk the parameter space' randomly, guided by the posterior density and proposal density. Gibbs sampling seems very similar but more efficient since it updates only one parameter at a time, while holding the others constant, effectively walking the space in an orthogonal fashion.

In order to do this, you need the full conditional of each parameter in analytical from*. But where do these full conditionals come from? $$P(x_1 | x_2,\ \ldots,\ x_n) = \frac{P(x_1,\ \ldots,\ x_n)}{P(x_2,\ \ldots,\ x_n)}$$ To get the denominator you need to marginalize the joint over $x_1$. That seems like a whole lot of work to do analytically if there are many parameters, and might not be tractable if the joint distribution isn't very 'nice'. I realize that if you use conjugacy throughout the model, the full conditionals may be easy, but there's got to be a better way for more general situations.

All the examples of Gibbs sampling I've seen online use toy examples (like sampling from a multivariate normal, where the conditionals are just normals themselves), and seem to dodge this issue.

* Or do you need the full conditionals in analytical form at all? How do programs like winBUGS do it?

-
Gibbs sampling is usually less efficient than Metropolis-Hastings because it goes one dimension at a time... –  Xi'an Jan 12 '12 at 20:24

Yes, you are right, the conditional distribution needs to be found analytically, but I think there are lots of examples where the full conditional distribution is easy to find, and has a far simpler form than the joint distribution.

The intuition for this is as follows, in most "realistic" joint distributions $P(X_1,\dots,X_n)$, most of the $X_i$'s are generally conditionally independent of most of the other random variables. That is to say, some of the variables have local interactions, say $X_i$ depends on $X_{i-1}$ and $X_{i+1}$, but doesn't interact with everything, hence the conditional distributions should simplify significantly as $Pr(X_i|X_1, \dots, X_i) = Pr(X_i|X_{i-1}, X_{i+1})$

-
To add to this answer, you need not marginalize the other variables as originally stated in the question. All you need to do is to 're-organize' $Pr(X_i|X_{i-1},X_{i+1})$ such that you recognize the result as a known pdf and you are done. As long as you are able to re-organize the above everything else (i.e., all other constants, the integral in the denominator etc) will equal the appropriate constant for the pdf to integrate to 1. –  user28 Nov 4 '10 at 9:15
They don't need to be found analytically. All full conditionals are proportional to the joint distribution, for instance. And that's all that's needed for Metropolis-Hastings. –  Tristan Nov 5 '10 at 2:05
@Tristan of course. I am, however, talking about gibbs sampling. –  gabgoh Nov 5 '10 at 6:22
They don't need to be found analytically for Gibbs Sampling. You just need to be able to sample, somehow, from the conditional; whether you can write down how to do this in a pretty analytic statement is not relevant. –  guest Mar 2 '12 at 17:47
The unnormalized full conditionals are often available. For instance, in your example $P(x_1 | x_2,...,x_n) \propto P(x_1,...,x_n)$, which you have. You don't need to do any integrals analytically. In most applications, a lot more will likely cancel too.