Metropolis–Hastings algorithm

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 x^t which is a Markov chain because each state x^t depends only on the previous state x^t-1. The algorithm depends on the creation of a proposal density Q(x^t,x') which depends on the current state x^t and which can generate a new proposed sample x'. For example, the proposal density could be a Gaussian centred on the current state x^t

Q(x^t) ~ N(x^t,σ²I).

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

a = a₁ a₂ a₁ = P(x') / P(x^t a₂ = Q(x^t;x') / Q(x';x^t)