Exact Markov Chain Monte Carlo

Markov Chain Monte Carlo methods are well known as a way to approximately generate random variables from a probability density function even when its overall normalisation constant is unknown. One of my favourite applications is the Metropolis Light Transport algorithm used in graphics. But it also has applications ranging from nuclear physics to finance. Unfortunately it has some drawbacks. The underlying theorems tell you that in the limit if you carry out enough trials you are drawing from the correct distribution, but it doesn't tell you how many trials you need in practice and neither does it give a good way to tell if you're getting close.

On the other hand, the Propp-Wilson algorithm is a variation that can converge to the correct distribution in a finite number of steps and, more importantly, it tells you when it has converged. It's quite curious the way it uses a notion of coupling from minus infinity which is quite distinct from convergence at infinity.





A nice bit of research you can do with this algorithm is play with Aztec Diamonds, coverings of the diamond with 2 by 1 dominoes. Notice how towards the corners you have little or no choice in how you place your dominoes but as you move away from the corners you gain more freedom. The Propp-Wilson algorithm allows you to sample uniformly from the space of all coverings and you can clearly see that the patterns are typically 'frozen' outside of a circle known as the arctic circle.

The Propp-Wilson algorithm can also be used to sample from the Ising Model exactly.

One problem with the Propp-Wilson algorithm is that it takes time to converge. It's tempting for a researcher, who's getting bored for waiting for convergence, to restart the program hoping to get a faster converging sequence. But this introduces bias because the distribution of samples at the end of short chains is different from the distribution of samples from unbounded chains. Fill's algorithm deals with that. I've never before heard of an algorithm that factors in user impatience!

I learnt about this stuff from Olle Haggstrom's book Finite Markov Chains and Algorithmic Applications.