To get the next sample, we first need to calculate a candidate sample, and then choose whether to take it or not. This is the initial sample and hopefully is a location where y is greater than 0. You start with an x value and calculate y which is just f(x). The metropolis algorithm is pretty simple. It’s worth noting that the Metropolis algorithm is a simpler special case of the Metropolis-Hastings algorithm, and these are just two of many Markov Chain Monte Carlo algorithms. Maybe when the first die was a larger number, it made it be more probable for the other die to be a larger number too.Īs weird as that is, if you can describe the relationship as a z=f(x,y) function, this can generate (x,y) random numbers from that distribution for you. It sounds weird but this situation is like if you rolled two dice, the value that one die came up as affected the probability of the other die. In higher dimensions such as z=f(x,y), the z is the probability of a 2d random number (x,y) being chosen. The Metropolis algorithm also works in any dimension: you can use it with functions like z=f(x,y) or t = f(x,y,z,w,s). If there is a black box you can give an x to get a y, the Metropolis algorithm can generate random numbers from the distribution hidden in that black box. It never actually has to KNOW what function describes the probability distribution. You can sample from a distribution defined from any function, and you don’t have to throw out any samples while doing it.Īnother interesting thing about the Metropolis algorithm is that it can work blindly. In these ways, the Metropolis algorithm is the best of both worlds. Inverting the CDF doesn’t throw out any samples, but it’s limited in the type of distributions it can do: It can be mathematically complex, or impossible, to find the inverted CDF for a given function analytically. Rejection sampling does this as well, but you have to throw away an unknown number of bad samples before getting each good sample. The Metropolis algorithm lets you generate random numbers that follow a distribution given by any function y=f(x), where y is the probability of choosing x.

If you want an intro or review to either Markov Chains or Monte Carlo, these two posts can help you out. This post also talks about using it for numerical integration. This post will show how to do it using a Markov Chain Monte Carlo method called “The Metropolis Algorithm”. In previous posts I showed how to generate random numbers from a specific distributing by using two techniques: There is ~400 lines of standalone C++ code that implements the main ideas in this post.

Old random number generator algorithm