The Metropolis-Hastings Algorithm By Example
Consider flipping a fair coin 100 times. The probability space has size 2^100,
which is on the order of 10^69. Yet we can easily sample from this space:
each event occurs with equal probability 0.5^100, and all we have to do is
conduct 100 independent Bernoulli experiments with p=0.5.
If the coin isn't fair, not all events occur with equal probability. Yet it's
still easy to sample from this space: we conduct 100 independent Bernoulli
experiments with 0 <= p <= 1.
Now suppose the coin flips aren't independent -- they have some peer pressure.
This system is called a one-dimensional Ising model and it's non-trivial to
sample from this space.
I will describe how the Metropolis-Hastings algorithm allows us to conduct
experiments using such a model.
John Kerl
Graduate Probability Seminar
February 14, 2008