Computational Physics

10.3 Importance sampling through Markov chains 301
Let us introduce the functionρ(X,t)which gives us the probability of occurrence
of configurationXat ‘time’, or Markov step,t(for an ergodic chain,ρ(x,t)becomes
independent oftfor larget). The change in this function from one step to another
is governed by two processes: (i) going from a configurationXat timetto some
other configurationX′att+1, leading to a decrease ofρ(X), and (ii) going from
some configurationX′at timettoXat timet+1, thus causing an increase inρ(X).
These mechanisms can be summarised in the formula

ρ(X,t+ 1 )−ρ(X,t)=−

∑

X′

T(X→X′)ρ(X,t)+

∑

X′

T(X′→X)ρ(X′,t).

(10.12)
This equation is called themaster equation. Remember that we are trying to find
the stationary distribution, which is found by requiringρ(X,t+ 1 )=ρ(X,t),so
that we have
∑

X′

T(X→X′)ρ(X,t)=

∑

X′

T(X′→X)ρ(X′,t). (10.13)

We omit thet-dependence ofρfrom now on. It is difficult to find the general
solution to this equation, but a particular solution is recognised immediately:

T(X→X′)ρ(X)=T(X′→X)ρ(X′) (10.14)

for all pairs of configurationsX,X′. This solution is called thedetailed balance
solution. Viewing the configurationsXas buckets, each containing a certain amount
ρ(X)of water, imagine that we make connections with pumps between each pair
of buckets. Water is pumped from bucketXto bucketX′with a pumping rate
T(X→X′)ρ(X). Condition (10.14) makes sure that the pumping rates between
any pair of bucketsX,X′are balanced: the flow fromXtoX′is equal to the flow
fromX′toX, so that obviously the volumesρ(X)andρ(X′)do not change. As this
holds for any pair of buckets, the whole set of water volumes in the buckets will
remain stationary.
Let us now reformulate the detailed balance solution to make it suitable for
practical purposes. We write the transtion probability in the form

T(X→X′)=ωXX′AXX′, (10.15)

where the matrixωωωis symmetric:ωXX′=ωX′X. Furthermore, it satisfies 0≤ωXX′≤
1, and

∑

X′ωXX′=1.AXX′must lie between 0 and 1 for each pairXX

′. Substituting

this form ofTinto the detailed balance equation gives a detailed balance equation
forA:
AXX′
AX′X

=

ρ(X′)

ρ(X)

. (10.16)

In order to construct an algorithm, we useωXX′as atrial step probabilityandAXX′
as anacceptance probability. This means that the algorithm proceeds in two stages.