22nd March 2004 — Fill's algorithm
Iain will present Fill's algorithm for exact sampling using Markov Chains. This is an alternative to coupling from the past based on rejection sampling. One feature is that, in some sense, it removes user impatience bias.
The recommended reading depends on who you are. If you do not understand exact sampling by coupling from the past (CFTP), then please make sure you do so. Otherwise you won't understand comparisons to it. CFTP is covered in David's book and in numerous papers listed on the Web Site for Perfectly Random Sampling with Markov Chains.
I am currently reading: Fill's original paper, if you know about CFTP please read this too. I may draw material from some of the papers extending the technique.