Metropolis Algorithm

In the previous lesson, we implemented a technique for sampling from a non-normalized target PDF:

• Find an everywhere-larger helper PDF that we can sample from.
• Sample from it.
• Accept or reject the sample via a coin flip with the ratio of weights in the target distribution and the helper distribution.

This technique works, but it has a few drawbacks:

• It’s not at all clear how to find a suitable helper PDF without humans intervening.
• Even with a pretty tight-fitting helper, you potentially still end up rejecting a lot of samples.

The first problem is the big one. It would be great if there were a technique that didn’t require quite so much intervention from experts.

In this lesson, we’ll describe just such a technique; it is called the “Metropolis algorithm” after one of its inventors, Nicholas Metropolis.

---

Introduction to the Metropolis Algorithm