Metropolis-Hastings

Metropolis-Hastings (also known as Metropolis-Hastings-Green) is the main form of Markov chain Monte Carlo. The algorithm provides a probabilistic rejection rule to reject some proposed moves of an arbitrary irreducible Markov chain so that the resultant Markov chain has the desired stationary distribution.

Properties of the chain

• If we find a tree with a better P(D|T), we are guaranteed to add that T to the chain.
• If the new tree has a worse P(D|T), we may stay with the better tree, or switch. The chance of switching depends on the relative difference.
• Less likely to include trees with low P(D|T) in chain
• More likely to stay with a tree with high P(D|T) for many steps.
• "Climbing mountains" but allowing some chance of moving downhill as well.

See also

• Metropolis-coupled Markov chain Monte Carlo