Perfect sampling for high dimensional integration

Grant Number: CAREER: DMS-05-48153    
Funding Agency: NSF
PI: Mark Huber
Effective Dates: 2006/01-2007/12
Amount: $193,853

Description: Monte Carlo Markov chain (MCMC) methods have become an indispensable tool in a wide variety of disciplines, including biology, physics, signal processing, finance, computer science, and statistics. These methods address the problem of counting or integration over high dimensional regions, where deterministic numerical methods cease to be practical. Taking random steps over a state space using a Markov chain can be used to generate random variates from a target distribution with an unknown normalizing constant. These random variates can then be employed to estimate parameters of interest about the distribution. Unfortunately, these methods are usually only heuristics. They only become algorithms when properties of the Markov chain such as the mixing time can be determined. This proposal focuses on perfect sampling methods, which are true algorithms for obtaining random variates exactly from a desired distribution. These are a subclass of MCMC methods that are an improvement on classical methods in several ways. For the generic MCMC approach, the greatest difficulty is knowing how many steps must be taken in the Markov chain before the variates obtained have a distribution close to the target. The number of steps needed is the mixing time. The mixing time question for specific chains such as the rifle shuffle chain used to generate a uniformly random permutation for a deck of cards has been answered with theoretical tools, but in applications of interest the mixing time remains elusive and difficult to calculate or even estimate. Perfect sampling algorithms have no need to know a mixing time, and can operate on problems where analysis of the mixing time of associated Markov chains cannot be accomplished. The PI proposes to develop and apply new perfect sampling techniques to problems currently studied using classical MCMC methods. The new algorithms are to be designed with several strong properties in place (such as interruptibility) that are absent in perfect sampling methods such as Coupling From the Past..