Sampling 2890 0.5 1
x0
0.2
0.4
0.6
0.8
1
f
(x),
h(x)(^05) ́ 105 1 ́ 106
MC Steps
0
0.2
0.4
0.6
0.8
1
Estimator(^05) ́ 105 1 ́ 106
MC Steps
0
0.2
0.4
0.6
0.8
1
Estimator
(a) (b) (c)Fig. 7.1(a) The integrand exp(−x) (solid line) and two possible importance functions
1 −x(dotted line) and 1− 0. 64 x(dashed line). (b) Instantaneous value of the estimator
φ(x) = exp(−x) for a Monte Carlo calculation withf(x) = 1 on the intervalx∈(0,1). (c)
Instantaneous value of the estimatorφ(x) = exp(−x)/h(x) when the importance function
h(x) = (1−ax)/(1−a/2) is used witha= 0.64 to improve sampling.
full interval. The dashed line in Fig. 7.1(a) shows this linear function fora= 0.64,
which, although a poorer representation of exp(−x) nearx= 0 than the Taylor series,
is still a better representation of exp(−x) overall for the full interval. The general
normalization ofh(x) ish(x) = (1−ax)/(1−a/2). After 10^6 Monte Carlo sampling
steps witha= 0.64, we obtain the approximate answerI ≈ 0. 63212 ± 0 .0000234,
which is nearly a full order of magnitude better in the variance than simple uniform
sampling. The lesson from this example is that importance functions must be chosen
carefully. Unless the importance function is a good representationof the integrand,
the sampling efficiency can actually degrade over simple uniform sampling.
7.3.3 The M(RT)^2 algorithm: Acceptance and rejection
In the application of eqn. (7.2.3) to any Monte Carlo calculation, the vectors x 1 ,...,xM
can be generated independently and randomly. However, better convergence can often
be achieved if the vectors are generated sequentially x 1 →x 2 →···→xMwith a rule
that specifies how to generate xi+1given xi. Such a sequence of vectors, in which xi+1
is generated based only knowledge of xiis called aMarkov chain. Markov chains are
the core of many Monte Carlo algorithms.
LetR(x|y) be a probability distribution function for obtaining a vector x froma
given vector y. If x and y are accessible microstates of a physical system, thenR(x|y)
is the probability for moving to a state x given that the system is currently in the state
y. Thus,R(x|y) potentially constitutes a rule for generating a Markov chain. However,
in order forR(x|y) to be valid as such a rule, it must satisfy the condition ofdetailed
balance, which states that
R(x|y)f(y) =R(y|x)f(x). (7.3.23)Here,R(x|y)f(y) is thea prioriprobability of a move from y to x, which is simply
the probabilityR(x|y) for the move from y to x times the probabilityf(y) that the
system is at y when the move is initiated. The detailed balance conditionensures
that the Markov process is microscopically reversible and hence guarantees unbiased