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.

## 2 comments:

I like your site. I wish I understood it more, but I like it.

Hey, thanks atoep! Sorry it's not more comprehensible. But check out the Aztec diamond links as the basic idea behind them is relatively simple, even if the explanation is often buried in more complicated mathematics.

Post a Comment