A "Monte Carlo" algorithm is a computational method that makes random decisions as it runs. Monte Carlo algorithms (dating back to the Manhattan Project) have been an invaluable tool in physics, computer science, statistics, and many other fields, and have become an indispensable part of the modern computing toolkit. Monte Carlo methods enable approximations of integrals that would otherwise remain out of reach. This project will develop and analyze new types of Monte Carlo algorithms, with the ultimate goal of better approximation for high-dimensional integrals and sums. These methods will assist in finding statistical objects such as the maximum likelihood estimator and exact p values, in performing model section using Bayesian statistics, and in building approximation algorithms for provably hard problems that arise in computer science. Many existing Monte Carlo algorithms deliver point estimates, but fail to give provably good error bounds on these estimates. Recent work of the principal investigator shows that in some instances, it is possible to build algorithms where the error only depends on the algorithm, and not on the particular problem under consideration. For example, a new method called the Paired Product Estimator gives a fast method for estimating integrals in high dimension where the error of the estimate is precisely bounded. These bounds are independent of the distribution being sampled from. The project purpose is to further develop and analyze these algorithms to improve both their theoretical and practical efficiency. These will be foundational methods, and should find use as a general tool for researchers in many different fields.
This project will develop several new methodologies in Monte Carlo simulation. The first algorithm is for estimating the mean of a Bernoulli random variable. This is an essential step in Monte Carlo algorithms for estimating exact p values in statistics and for estimating integrals using acceptance rejection. By employing a method of Huber, it is possible to create an estimate such that the relative error in the estimate is independent of the value of the mean. Computer experiments indicate the method is fast; in this part of the project, Huber will try to show that this method is provably close to the optimal in the number of samples needed to obtain such an estimate. A new protocol for sampling from Markov random fields such as the Ising model will also be developed, partially recursive acceptance rejection. By creating a tree of possible labels for a graph and then carefully pruning this (exponentially large) tree, it is possible to sample from the Ising model (at temperatures above the critical temperature) using only a polynomial (even linear) number of steps. Such models can usually be written as Gibbs distributions, and often finding the normalizing constant (called the partition function) for these distributions is computationally very difficult. One part of the project will be refining an idea called the Paired Product Estimator, that approximates the partition function in a provably fast way: now the goal is to make the method practically efficient as well.
