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

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?

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.

• Yes, MCMC is used when direct sampling from $P_{target}()$ is difficult, but I'm having a hard time to figure out that, since we have to evaluate $P_{target}(x)$ for those generated samples, so we've already known this $P_{target}()$ right? If not how could we evaluate it ? – avocado Dec 13 '13 at 11:20
• Which confuses me further is that, if we know $P_{target}()$, then how could it be difficult to sample directly from it? Could your plz elaborate on why and when direct sampling is hard? – avocado Dec 13 '13 at 11:22
• @loganecolss, edited answer to give some examples and point to a source. – Zhubarb Dec 13 '13 at 11:38

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.

• Yes, the need can also arise due to intractable integration problems like in Bayesian inference and learning (e.g. using a non-conjugate prior) – Zhubarb Dec 13 '13 at 11:33
• @Zhubarb. To my view, intractable integration enforce us to work with the joint densities in place of the analytically marginalized it and thus to increase the dimension of the problem, digging a bit further into the curse of dim. – peuhp Dec 13 '13 at 11:44
• I just read this wiki page. I think your answer is addressing the problem that, when the dimensions of parameter space grow, the number of sample points will grow even faster, which makes grid approx infeasible, right? – avocado Dec 14 '13 at 1:33
• @loganecolss Exactly – peuhp Dec 14 '13 at 8:00
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.