Content deleted Content added
Ramin Nakisa (talk | contribs) m Translated equations in to glorious LaTeX markup. |
m indenting equations |
||
Line 1:
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<sup>t</sup> which is a [[Markov chain]] because each state x<sup>t</sup> depends only on the previous state x<sup>t-1</sup>. The algorithm depends on the creation of a ''proposal density'' Q(x<sup>t</sup>;x') which depends on the current state x<sup>t</sup> and which can generate a new proposed sample x'. For example, the proposal density could be a Gaussian centred on the current state x<sup>t</sup>
:<math>
Q( x^t; x' ) \sim N( x'-x^t, \sigma^2 I).
</math>
Line 7:
This proposal density would generate samples centred around the current state with variance σ<sup>2</sup>I. So we draw a new proposal state from Q(x<sup>t</sup>,x') and then calculate a value
:<math>
a = a_1 a_2
</math>
Line 13:
where
:<math>
a_1 = \frac{P(x')}{P(x^t)}
</math>
Line 19:
is the likelihood ratio between the proposed sample x' and the previous sample x<sup>t</sup>, and
:<math>
a_2 = \frac{Q( x^t; x' )}{Q(x';x^t)}
</math>
Line 25:
is the ratio of the proposal density in two directions (from x<sup>t</sup> to x' and <em>vice versa</em>). This is equal to 1 if the proposal density is symmetric. Then the new state x<sup>t+1</sup> 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>
| |||