Metropolis Algorithm

In this lesson, we will learn about the Metropolis Algorithm, and its implementation.

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

Get hands-on with 1000+ tech skills courses.