CAREER: Perfect sampling techniques for high dimensional integration

这个项目将开发和分析新的计算方法，从高维分布中产生随机变量，其中归一化常数是未知的。 这些随机变量，然后使用，以获得近似的问题，涉及高维积分。 采用随机变量的算法称为蒙特卡罗方法。 直接方法的运行时间通常是问题维度的指数，而蒙特卡罗方法可以有多项式甚至线性的运行时间。 应用包括估计概率模型中的参数，近似统计中的精确p值，以及NP完全和P完全问题近似解的有效算法。 新算法属于一类称为完美采样算法的方法。 现有的完美采样器，如Coupling From the Past，对Monte Carlo方法产生了影响，但存在某些缺陷，限制了它们的适用性。 在这里，新的方法，如随机回收和其他修改和接受拒绝方法的推广将被用来解决这些问题。 作为该项目的一部分，将开发新的课程，本科生和研究生将有机会研究这一领域出现的问题。今天，我们的数据收集能力比历史上任何时候都要好，但分析数据所需的时间可能会以指数方式增长。 在设计数据分析算法时使用随机性可以在速度和准确性方面带来巨大的好处。 这些技术在过去的五十年里一直是计算方法的基石。 统计学、金融学、信号处理、物理学和遗传学只是从算法设计中注入随机性中受益的一些领域。 然而，现有方法并非没有困难。 一种称为完美采样方法的新算法在特定情况下解决了许多这些问题，但其适用性有限。 该项目的目标是通过引入新类型的完美采样算法来扩展这些方法的范围。 其结果将是更快，更准确的算法类型的从业者每天使用的各种领域。

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.