CAREER: Perfect sampling techniques for high dimensional integration

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

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.