DEPARTMENT OF MATHEMATICS AND STATISTICS COLLOQUIM

SPEAKER:

Duncan Murdoch

Department of Statistics and Actuarial Science

University of Western Ontario

TITLE:

Perfect Sampling Algorithms: Connections

ABSTRACT:

The arrival of Propp and Wilson's (1996, Random Structures and Algorithms) coupling from the past (CFTP) algorithm caused a big stir in the Markov chain Monte Carlo community, because it did the seemingly impossible task of using a finite run of a Markov chain to obtain samples from the steady-state distribution of the chain. At around the same time Fill (1998, Annals of Applied Probability) developed quite a different algorithm that accomplished the same thing using rejection sampling.

In this talk (which is loosely based on Fill, Machida, Murdoch and Rosenthal, 2000, Random Structures and Algorithms) I will summarize both algorithms, and show how Wilson's (2000, Random Structures and Algorithms) ``read-once'' variation on CFTP is in some sense also a variation on Fill's algorithm.

About the Speaker

Duncan Murdoch is an associate professor in the Department of Statistics and Actuarial Science at the University of Western Ontario. His research interests are in the area of computationally intensive statistics including Markov Chain Monte Carlo and Perfect Sampling.

References

A pdf copy of the transparencies can be downloaded. Other references used in the talk or giving background material are :

• J. A. Fill (1998) An Interruptible Algorithm for Perfect Sampling via Markov Chains. Annals of Applied Probability, 8, 131-162
• J. A. Fill, M. Machida, D. J. Murdoch and J. S. Rosenthal (2000) Extension of Fill's Perfect Rejection Sampling Algorithm to General Chains. Random Structures and Algorithms, 17, 290-316
• J. Propp and D. B. Wilson (1996) Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics. Random Structures and Algorithms, 9, 223-252
• L. Tierney (1994) Markov Chains for Exploring Posterior Distributions. Annals of Statistics, 22, 1701-1762
• D. B. Wilson (2000) How to Couple from the Past Using a Read-Once Source of Randomness. Random Structures and Algorithms, 16, 85-113

Department of Mathematics and Statistics

Graduate Program in Statistics

This page is maintained by Angelo Canty,
Last updated on November 25, 2002