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.