Importance Sampling

Now that we have a better understanding as to when a system reaches equilibrium and of how it evolves from equilibrium state to equilibrium state we can start answering the important question of how we can measure average equilibrium properties of the system in a way that ensures the correctness of the result. In conventional Statistical Physics, the average of an observable is given by:

[tex]\displaystyle A\equiv\left\langle A\left(s\right)\right\rangle _{S}=\frac{1}{Z}\int_{S}\mathrm{d}sA\left(s\right)e^{-\beta H\left(s\right)}[/tex]

where:

[tex]\displaystyle Z=\int_{S}\mathrm{d}se^{-\beta H\left(s\right)}[/tex]

is the system’s partition function, [tex]\beta=\left(k_{B}T\right)^{-1}[/tex] is the inverse temperature, [tex]H\left(s\right)[/tex] is the Hamiltonian and the integration is carried out over all phase space S. However, for practical reasons, it is usually impossible to perform these integrals and we are forced to estimate their value using a finite number, n, of phase space points, [tex]\left\{ s_{1},s_{2,}\cdots,s_{n}\right\}[/tex] .

A back of the envelope calculation allows us to discretize integrals, and obtain:

[tex]\displaystyle\left\langle A\left(s\right)\right\rangle _{S}=\frac{\sum_{i=1}^{n}A\left(s_{i}\right)e^{-\beta H\left(s_{i}\right)}}{\sum_{i=1}^{n}e^{-\beta H\left(s_{i}\right)}}[/tex]

which is exact in the n\to\infty limit. Ideally, these points would be chosen and weighted using some distribution, [tex]P\left(s\right)[/tex], such that we can obtain the best possible result with the fewest number of points possible. With this approach, the last expression takes on the form:

[tex]\displaystyle\left\langle A\left(s\right)\right\rangle _{S}=\frac{\sum_{i=1}^{n}A\left(s_{i}\right)e^{-\beta H\left(s_{i}\right)}P\left(s_{i}\right)^{-1}}{\sum_{i=1}^{n}e^{-\beta H\left(s_{i}\right)}P\left(s_{i}\right)^{-1}}[/tex]

which clearly identifies, the choice of [tex]P\left(s_{i}\right)[/tex]:

[tex]\displaystyleP\left(s_{i}\right)=e^{-\beta H\left(s_{i}\right)}[/tex]

that allows us to obtain:

[tex]\displaystyle\left\langle A\left(s\right)\right\rangle _{S}=\frac{1}{n}\sum_{i=1}^{n}A\left(s_{i}\right)[/tex]

this is usually referred to in the literature as ”importance sampling”. By using this form of [tex]P\left(s_{i}\right)[/tex] in the detailed balance equation, we easily obtain:

[tex]\displaystyle\frac{\omega_{s\to s’}}{\omega_{s’\to s}}=e^{-\beta\delta H}[/tex]

where [tex]\delta H[/tex] is the change in energy between the final state s’ and the initial state s. This practical prescription on how to implement a Markov Chain process that would allow us to easily calculate the equilibrium value of physical observables using a computer was introduced in 1953 by Nicholas Metropolis et al and is probably one of the most influential algorithms of the last 100 years. It has since been used in a multitude of different applications, with several good reviews and introductory texts [binder89, creutz83, fishman96, krauth96, newman99] available.

In the next parts of these series we will focus on different implementations and applications of these general ideas.

Sphere: Related Content