Encyclopedia > Metropolis-Hastings Markov Chain Monte Carlo Sampling

  Article Content

Metropolis-Hastings Markov Chain Monte Carlo Sampling

This algorithm can draw samples from any probability distribution P(x), requiring only that the density can be calculated at x. The algorithm generates a set of states xt which is a Markov chain because each state xt depends only on the previous state xt-1. The algorithm depends on the creation of a proposal density Q(xt;x') which depends on the current state xt and which can generate a new proposed sample x'. For example, the proposal density could be a Gaussian centred on the current state xt

<math>
Q( x^t; x' ) \sim N( x'-x^t, \sigma^2 I). </math>

This proposal density would generate samples centred around the current state with variance σ2I. So we draw a new proposal state from Q(xt,x') and then calculate a value

<math>
a = a_1 a_2 </math>

where

<math>
a_1 = \frac{P(x')}{P(x^t)} </math>

is the likelihood ratio between the proposed sample x' and the previous sample xt, and

<math>
a_2 = \frac{Q( x^t; x' )}{Q(x';x^t)} </math>

is the ratio of the proposal density in two directions (from xt to x' and vice versa). This is equal to 1 if the proposal density is symmetric. Then the new state xt+1 is chosen with the rule

<math>
x^{t+1}=\left\{\begin{matrix} x' & \mbox{if }a > 1 \\ x'\mbox{ with probability }a, & \mbox{if }a < 1 \end{matrix}\right. </math>

The Markov chain is started from a random initial value x0 and the algorithm is run for a few thousand iterations so that this initial state is "forgotten". These samples, which are discarded, are known as burn-in. The algorithm works best if the proposal density matches the shape of the target distribution P(x), but in most cases this is unknown. If a Gaussian proposal is used the variance parameter σ2 has to be tuned during the burn-in period. This is usually done by calculating the acceptance rate, which is the fraction of proposed samples that is accepted in a window of the last N samples. This is usually set to be around 60%. If the proposal steps are too small the chain will mix slowly i.e. it will move around the space slowly and converge slowly to P(x). If the proposal steps are too large the acceptance rate will be very low because the proposals are likely to land in regions of much lower probability density so a1 will be very small.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Christiania

... name of Oslo, from 1624 to 1925. The Free State of Christiania - a partially self-governing neighborhood in the city of Copenhagen. This is a disambiguation page; that ...

 
 
 
This page was created in 38.7 ms