Metropolis algorithm, what is the target distribution and how to compose it?

Question

When we do Metropolis sampling or MCMC, we need a target distribution $P_{target}(\theta)$, and a proposal distribution $P_{proposal}(\theta)$, then a value $\theta_i$ is generated via $P_{proposal}(\theta)$, we need to compute the probability whether to accept or reject this $\theta_i$ via $P_{target}(\theta)$, right?

My problem is, we should know $P_{target}(\theta)$ before we doing this Metropolis process, right? Then what is this target distribution, does it have to do with my prior belief of $\theta$? If I've already known it, why bother doing this Metropolis sampling, can't we just use grid approximation?

As I read in the book, it takes the product of the likelihood and prior of $\theta$ as the target distribution, why? Different prior belief will result into different target distribution, does it mean we don't have a fixed desired target distribution?

Answer 1

MCMC is a strategy for generating samples $x(i)$ while exploring the state space $X $using a Markov chain mechanism. These are irreducible and aperiodic Markov chains that have $P_{target}(\theta)$ as the invariant distribution.

This mechanism is constructed so that the chain spends more time in the most important regions. In particular, it is constructed so that the samples $x(i)$ mimic samples drawn from the target distribution $P_{target}(\theta)$.

The answer to your question is: MCMC is used when we cannot draw samples from $P_{target}(\theta)$ directly, but can evaluate $P_{target}(\theta)$ up to a constant of proportionality. To clarify this, let us denote $P_{target}(\theta) = P(\theta | D)$ where $D$ is the data and $P(\theta | D)$ is our posterior target distribution.

Normally, calculating the exact $P(\theta | D)$ requires:

$ P(\theta | D) = \frac{P(D|\theta) * P(\theta)}{P(D)} $

As you can see, our target distribution: $ P(\theta | D) \propto P(D|\theta) * P(\theta)$ up to a constant of proportionality. We use this product (of the likelihood and the prior) as the target distribution in a Metropolis algorithm. The acceptance criterion of the algorithm only needs the relative posterior probabilities in the target distribution and not the absolute posterior probabilities, so we could use an unnormalised prior or unnormalised posterior when generating sample values of $\theta$.

Section 2 of this paper gives examples to situations when sampling from the posterior $P_{target}(\theta)$ is tricky. 4 scenarios in short: 1) Bayesian inference and learning (see my comment to another answer on the page), 2) Statistical mechanics, 3) Optimisation, 4) Penalised likelihood model selection.

Answer 2

I guess that the missing "concept" is the one of "curse of dimensionality" (http://en.wikipedia.org/wiki/Curse_of_dimensionality) that would make your attempt to investigate your posterior by brute force griding irrelevant when the dimension of your posterior is not very small.

Answer 3

My problem is, we should know Ptarget(θ) before we doing this 
Metropolis process, right?

Yes. The whole purpose of MCMC is to sample from the (known) target distribution, because handling it with other methods is difficult. For example, the target distribution might be multi-dimensional and maybe you only need the marginal distribution of one variable, and integrating the target distribution is unfeasible or very difficult to do (specially for hierarchical models, for example, in which every unknown parameter depends on other unknown parameters and so on).

Then what is this target distribution, does it have to do with 
my prior belief of θ?

As @Zhubarb answered, by bayes theorem, if we call $p(\theta)$ your prior belief on $\theta$, then your target distribution, a.k.a. the posterior distribution, is $$p(\theta |\textrm{Data})=\frac{p(\textrm{Data}|\theta)p(\theta)}{P(\textrm{Data})}$$

So yeah, your prior belief has to do with your target distribution: in fact, it is a function of it.

If I've already known it (the target distribution), why bother doing 
this Metropolis sampling, can't we just use grid approximation?

Yeah, you could just use a grid approximation if you know the posterior. This might seem easy to do in one-dimensional problems, but in multi-dimensional problems it's a mess. For example: how would you go on choosing your grid when you have a 10-dimensional parameter vector $\theta$? Where is the maximum or minimum of the distribution? Not in all settings you'll have an easy target distribution to play with and is in these kind of settings that MCMC is very useful, because it allows you to draw samples from the target distribution.