290 Monte Carlo
sampling of the state space. It has been argued that the detailed balance condition is
a sufficient but not strictly necessary condition to ensure proper sampling of the state
space (Manousiouthakis and Deam, 1999). In the present discussion, however, we will
assume that eqn. (7.3.23) is satisfied by the processR(x|y).
The sampling technique to be discussed in this section, which was proposed by
Metropoliset al.in 1953, which we refer to as the M(RT)^2 algorithm (M(RT)^2 stands
in for the last names of the five authors), belongs to a class of Monte Carlo schemes
known asrejection methods. The M(RT)^2 method starts with a rule for generating
trial or proposed moves from y to x, denotedT(x|y). The normalization condition on
T(x|y) is ∫
dxT(x|y) = 1. (7.3.24)Once a trial move is generated, a decision is made either to accept the move, in which
case the system is advanced to x, or to reject it, in which case it is returned to y by
setting x = y. LetA(x|y) be the probability that the move is accepted. Then, the
transition probabilityR(x|y) can be expressed as
R(x|y) =A(x|y)T(x|y). (7.3.25)When eqn. (7.3.25) is substituted into eqn. (7.3.23), we find
A(x|y)T(x|y)f(y) =A(y|x)T(y|x)f(x), (7.3.26)so that the acceptance probabilities are related by
A(x|y) =T(y|x)f(x)
T(x|y)f(y)A(y|x) =r(x|y)A(y|x). (7.3.27)The implication of eqn. (7.3.27) is an interesting one. SupposeA(x|y) = 1 so that the
move from y to x is favorable. In this case, we expect that the reverse move from x to
y is less favorable so thatA(y|x)<1, implying thatr(x|y)>1. On the other hand, if
A(x|y)<1 so that the move x to y is not entirely favorable, then we expectA(y|x) = 1
so thatr(x|y)<1. Combining these facts, we see that the acceptance probability is
given conveniently by
A(x|y) = min[1,r(x|y)], (7.3.28)
where function min[a,b] chooses the smaller ofaandb.
Given the ideas developed above, the M(RT)^2 algorithm can now be stated suc-
cinctly. At thekth step of a Markov chain, the trial distributionT(xk+1|xk) is used to
generate a proposed move from xkto xk+1. Using xkand xk+1, we compute the ratio
r(xk+1|xk) =T(xk|xk+1)f(xk+1)
T(xk+1|xk)f(xk). (7.3.29)
Next, the decision must be made whether this trial move is to be accepted or rejected.
Ifr(xk+1|xk)≥1, then the move is accepted with probability 1 according to eqn.
(7.3.28). If, however,r(xk+1|xk)<1, then a random numberξ∈[0,1] is generated. If
r(xk+1|xk)> ξ, the move is accepted, and the value of xk+1is retained. Otherwise, if