CAREER: Perfect sampling techniques for high dimensional integration

Duke University, Durham NC

Investigators

Abstract

This project will develop and analyze new computational methodologies for generating random variates from high dimensional distributions where the normalizing constant is unknown. These random variates are then used to obtain approximations for problems involving high dimensional integrations. Algorithms employing random variates are known as Monte Carlo methods. Direct methods often suffer from running times that are exponential in the dimension of the problem, whereas Monte Carlo approaches can have a polynomial or even linear running time. Applications include estimate of parameters arising from probabilistic models, approximation of exact p-values in statistics, and efficient algorithms for approximate solutions to NP complete and \#P complete problems. The new algorithms are in a class of methods known as perfect sampling algorithms. Existing perfect samplers such as Coupling From the Past have made an impact on Monte Carlo methods, but suffer from certain flaws that limit their applicability. Here new methodologies such as the Randomness Recycler and other modifications and generalizations of acceptance rejection approaches will be used to solve these problems. As part of this project, new classes will be developed and undergraduates and graduate students will have opportunities to work on problems arising in this area. Today our data collection abilities are better than at any point in history, but the time needed to analyze data can grow exponentially in the amount collected. The use of randomness in designing algorithms for analysis of data can result in enormous benefits in speed and accuracy. These techniques have been a cornerstone of computational methodology for the last fifty years. Statistics, finance, signal processing, physics, and genetics are but some of the areas that have benefited from the injection of randomness into the design of algorithms. However, existing methods are not without difficulties. A new class of algorithms called perfect sampling methods solves many of these problems in specific cases, but their applicability is limited. The goal of this project is to extend the reach of these methods by introducing new types of perfect sampling algorithms. The result will be faster, more accurate algorithms of the type used by practitioners every day in a wide variety of fields.