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.