Summarized from lecture notes: Prof. J. L. Beck
Initiation
Standard MCS cannot sample directly from the posterior PDF given by Bayes’ Theorem:
because we cannot analytically evaluate the normalizing integral in the denominator, even if we could, it is still difficult to sample from an arbitrary multi-dimensional PDF.
In order to deal with it, Metropolis-Hasting algorithm is used and generates samples from a Markov chain whose stationary PDF is an target PDF, even an unnormalized one such as the PDF we posted above. However, these samples are not independent, thus reduces the efficiency. i.e. it increases the number of samples needed to get the same c.o.v. compared with MCS.
Metropolis Algorithm
Consider continuous stochastic variables [math]$\theta_k \in \Re^d$[/math], [math]$\forall$ k \geq 0$[/math]
Markov charin is defined by the PDF for its initial state, [math]p_{0}(\theta_0)[/math], and its transition PDF, i.e. the conditional PDF [math]p_{k|k-1}(\theta_k|\theta_k-a) , $\forall$ k \geq 1[/math]
Defn.
A homogeneous Markov chain has a transitional PDF that is independent of the step, i.e. [math]p_{k|k-1}(\theta|\xi)=p_{1|0}(\theta|\xi) $\triangleq$ p(\theta|\xi)[/math]
Defn.
[math]p_{s}(\theta)[/math]is a stationary PDF for a homogeneous Markov chain if: [math]p_{s}(\theta)=\int_{\Theta} p(\theta|\xi)p_{s}(\xi)d\xi ,\quad$\forall$\theta \in \Theta[/math]