Metropolis–Hastings algorithm: Difference between revisions

Revision as of 09:09, 24 November 2019

Revision as of 09:12, 24 November 2019

Line 95:

{{main|Monte Carlo integration}}

A common use of Metropolis–Hastings algorithm is to compute an integral. Specifically, consider a space <math>\Omega \subset \mathbb{R}</math> and a probability distribution <math>P(x)</math> over <math>\Omega</math>, <math>x \in \Omega</math>. Metropolis-HastingsMetropolis–Hastings can estimate an integral of the form of

: <math>P(E) = \int_\Omega A(x) P(x) \,dx,</math>

:<math>

P(E) = \int_\Omega A(x) P(x) dx

where <math>A(x)</math> is an arbitrary function of interest.

</math>

where A(x) is an arbitrary function of interest.

For example, consider a [[statistic]] <math>E(x)</math> and its probability distribution <math>P(E)</math>, which is a [[marginal distribution]]. Suppose that the goal is to estimate <math>P(E)</math> for <math>E</math> on the tail of <math>P(E)</math>. Formally, <math>P(E)</math> can be written as

: <math>

P(E) = \int_\Omega P(E|x) P(x) \,dx = \int_\Omega \delta\big(E - E(x)\big) P(x) \,dx = E_X\big(P(E|X)\big)

</math>

and, thus, estimating <math>P(E)</math> can be accomplished by estimating the expected value of the [[indicator function]] <math>A_E(x) \equiv \mathbf{1}_E(x)</math>, which is 1 when <math>E(x) \in [E, E + \Delta E]</math> and zero otherwise.

Because <math>E</math> is on the tail of <math>P(E)</math>, the probability to draw a state <math>x</math> with <math>E(x)</math> on the tail of <math>P(E)</math> is proportional to <math>P(E)</math>, which is small by definition. Metropolis-HastingsThe Metropolis–Hastings algorithm can be used here to sample (rare) states more likely and thus increase the number of samples used to estimate <math>P(E)</math> on the tails. This can be done e.g. by using a sampling distribution <math>\pi(x)</math> to favor those states (e.g. <math>\pi(x) \propto e^{a E}</math> with <math>a > 0</math>).

==Step-by-step instructions==