Home
|
Course Outline
|
Lectures
|
Homework
|
Files
Lecture 9: February 5
Importance Sampling
The theory and example given in §11.7 shows how the use of a
positive definite "weight function" p(x) can be used
to dramatically improve the efficiency of a Monte Carlo quadrature.
This technique is even more important for multi-dimensional integrals.
If you imagine filling the multi-dimensional integration volume with
small elements (hypercubes) of given size, the number of elements
required increases exponentially with the number of dimensions d.
For example, if the integration volume is a unit hypercube, and each
volume element is a hypercube of side 0.1, then the number of elements
is 10d. For d = 100 this is more than the total
number of hydrogen atoms in the universe!
Trying to sample the whole integration volume uniformly is doomed to
failure: it is essential to locate regions where the integrand is
large and concentrate the sampling points in these "important" regions!
So it is very important to understand the concept of importance sampling.
Metropolis Monte Carlo Algorithm
This is nicely explained in §11.8. Try to find a proof that the
"detailed balance" condition leads to the desired probability distribution
in a statistical physics textbook. The easiest way to demonstrate this is
to consider an "ensemble" of many independent Metropolis walkers.
Detailed balance guarantees that the distribution of walkers tends
towards the probability distribution p(x). This is analogous
to the proof of thermal equilibrium in statistical physics, and therefore
a Metropolis walker is said to "thermalize" after it takes some number of
"thermalization steps". While these proofs guarantee asymptotic
equilibration, they do not predict how long it takes the walker to
thermalize. In most cases, the approach to equilibrium turns out to be
surprisingly rapid!
Questions or comments:
phygons@acsu.buffalo.edu