[Publications ] [Code ] [Talks ]

This page is meant to serve as a portal for my research papers and code. I work in the area of Probability, specifcally Monte Carlo methods where generation of random variates is used in the construction of algorithms. By using randomness it is often possible to construct fast, elegant algorithms for problems from a variety of areas.

Much of my work focuses on perfect sampling methods. These are methods for generating random variates from high dimensional distributions given by a density or probability mass function where the normalizing constant is very difficult to compute. Often finding the normalizing constant is a #P-complete problem. These problems arise in computer science in building approximation algorithms for #P-complete problems, in statistics in finding p-values for tests, and in Bayesian statstics where the posterior distribution is usually of this form.

Classically, Markov chain methods have been used to approximately generate samples from these distributions. The problem with the Monte Carlo Markov chain (MCMC) approach is that unless the mixing time of the Markov chain is known ahead of time, the quality of the variates created will be in doubt. The mixing time is the classic question of how many shuffles does a deck of cards need before it is close to uniform over all permutations. While the shuffling question has been answered, for many complex problems arising in practice no means of bounding the mixing time is known. Autocorrelation tests and other heurestics can show when chains have not mixed, but evidence for the positive claim that the chain has mixed is much harder to come by.

Perfect sampling methods have no need for external knowledge of a mixing time in order to generate samples. They fall into several classes. Methods such as Coupling From the Past (CFTP) and the method of Fill, Machida, Murdoch, and Rosenthal (FMMR) utilize classical Markov chains as a component of the method. Other approachs such as the Randomness Recycler (RR) uses Markov chains, but in a very different fashion from CFTP and FMMR, leading to some advantages and some disadvantages. Finally, methods such as cycle popping and Recursive Acceptance Rejection dispense with Markov chains altogether, and directly attempt to create samples.

Back to Mark's Home Page

This site supported by NSF CAREER grant DMS-05-48153.