Suppose that we want to generate random variables according to an
arbitrary probability density . The Metropolis algorithm produces a
``random walk'' of points whose asymptotic probability
approaches
after a large number of steps. The random walk is defined by a
``transition probability''
for one value
to another in order that the distribution of points , ,
, ... converges to . In can be shown that it is sufficient
(but not necessary) to satisfy the ``detailed balance'' condition
(97) |
It is necessary to sample a number of points of the random walk before the asymptotic probability is attained. How do we choose the ``step size'' ? If is too large, only a small fraction of changes will be accepted and the sampling will be inefficient. If is too small, a large number will be accepted, but it would take too long to sample over the whole interval of interest. Ideally, we want at least 1/3-1/2 of the trial steps to be accepted. We also want to choose such that the distribution converges to as quickly as possible. An obvious choice is to begin the random walk at the point where is maximum.