MCMC
This demo is based upon Figure 12.1 from John Miller’s book A Crude Look at the Whole.
Monte Carlo algorithms are often used to explore probability distributions. Particularly, the Metropolis-Hastings algorithm is an extremely widely used technique for sampling from distributions. In this story, there are a few frog characters to familiarize ourselves with.
First up, explorer frog:
- Red
- Doesn’t care about flies, wanders to any lilypad.
Next, we have exploiter frog (also known as greedy frog):
- Blue
- Wants flies, now.
Finally, our most complicated frog will be sampler frog:
- Green
- Wants flies, most of the time (!)
In the Metropolis-Hastings algorithm, in order to sample from a distribution proportional to \(P(x)\), a proposed move from a “state” \(x\) to some new state \(x'\) will be “accepted” with probability \[P_{\text{accept}}(x \rightarrow x') = \min\left(1,\frac{P(x)}{P(x')}\right).\] (really we should be sure our proposals are symmetric, but we won’t worry about that in this demonstration).
In this analogy, the states \(x\) are the different lilypads, and the probability \(P(x)\) is the number of flies at each lilypad. The frog characters then correspond to the behavior of this Monte Carlo algorithm at different values of \(\beta\). Below, you can tinker with these parameters to explore how the distribution of frogs is related to the distribution of flies depending on the \(\beta\) parameter.