The Metropolis Et Al Algorithm

To perform accurate Monte Carlo Integration requires sampling the function $f(x)$ using random numbers distributed according to a positive definite weight function $w(x)$. The Metropolis Et Al algorithm was devised to generate random numbers with arbitrary positive weight function $w(x)$. This algorithm, due to Metropolis, Rosenbluth, Rosenbluth, Taller, and Taller, in 1953, has become a very important tool for any Monte Carlo technique.

Assume that $X$ is a variable in the multi-dimensional space. We are looking for a set of points ${X_i}$ in this phase space which follow a probability density $w(X)$. The sequence of points $X_0$, $X_1$, $...$ corresponds to the points visited by a guided random walker moving through this multi-dimensional space as his walk becomes longer and longer.

The algorithm can be described as follows: assume the walker is at the point $X_n$ in the sequence. The walker takes a tentative trial step to a new point $X_t$. This point can be chosen in any convenient way, for example using a uniform random choice within a multi-dimensional cube of the small size $\delta$ about $X_n$. This trial step is then accepted or rejected according to the ratio.

$$r = \frac{ w(X_t) } { w(X_n) }$$

If $r > 1$ then the step is accepted ( $X_{n + 1} = X_t$). If $r < 1$ the trial step is accepted with probability $r$. This is accomplished by comparing $r$ with the random number $n$ uniformly distributed in the interval [0,1] and accepting the step if $r > n$, ( $X_{n + 1} = X_t$). If the trial step is not accepted then it is rejected,( $X_{n + 1} = X_n$), which means that it does not participate in taking averages. Any arbitrary points $X_0$ can be used as the starting point for the random walk. All steps are generated by the algorithm as described.

It is possible to prove that this algorithm yields a distribution of random numbers, set of points in multi-dimensional space, according to the weight function $w(x)$. The proof is in one of the following subsections.

An interesting question is what to choose for the step size, $\delta$. This choice is obviously arbitrary. Taking $\delta$ too large will result in poor sampling since when near a maximum of $w(x)$ very few steps will take the walker away from the maximum. If on the other hand the steps are too small, the walker will stand litttle chance to explore the space by going far from the initial point. Neither of these two choices yields efficient sampling of the space. In practice $\delta$ is chosen so as to have roughly half of the trial steps accepted by the criteria of the algorithm.

A great danger in sampling a multi-dimensional space via a random walk is to have steps taken by the walker which are not independent from one another. This could result from poor random number generation algorithms or from the way the walk is built. If this happens then the calculation of integrals by averaging over points in a random walk will be innacurate.