ChapterZero

I’ve suddenly noticed that the ‘London Mathematical Society Student Texts’ are really quite good. As one case of particular relevance to me at this time, Olle Haggstrom’s ‘Finite Markov Chains and Algorithmic Applications’ is a superb introduction to markov chains. It is serving as a good supplement to Winkler’s more focused ‘Image Analysis, Random Fields and Markov Chain Monte Carlo Methods’. Haggstrom’s proof of the existence and uniqueness of invariant distributions is not as concise as I’d like– he uses coupling arguments instead of contraction coeffecient arguments– so I skipped it and referred to Winkler’s book for that instead. But by far that is made up for by his presentation of the Propp-Wilson algorithm for exact sampling. Winkler also covers that material, but I couldn’t understand even his motivating comments; Haggstrom does a much better job of making the ideas transparent.

Winkler bandies about the terms coupling from the past and coalescing in his introductory comments on exact sampling, but this just confuses the reader, because he/she hasn’t yet seen a concrete example of what coalescing or coupling means. I got the impression that he thought using these terms conveyed a sense of the motivation of the algorithm, but it didn’t– you can’t appeal to people’s intuitions by introducing terminology. On the other hand, Haggstrom introduces the subject without using any terminology. This is a general rule of good mathematical writing that other authors would do well to remember: introduce terminology only after the ideas have already been absorbed; generalize only after the specific is understood.

Possibly relevant posts:

• Markov Chains (6/9/2006)
• Markov Random Fields (6/26/2006)
• Stochastic Processes are fun! (9/13/2005)