Studies in Perfect Simulation and Combinatorial Probability

完美模拟和组合概率研究

• 批准号: 0104167
• 负责人: James Fill
• 金额: $ 21.9万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2004-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0104167&HistoricalAwards=false
• 关键词: Studies; Perfect; Simulation; Combinatorial; Probability

One focus of the research is perfect simulation. Markov chain Monte Carlo (MCMC) approximate sampling methods have become extremely popular for Bayesian inference problems and for problems in other areas, such as spatial statistics, statistical physics, and computer science as a way of sampling approximately from a complicated probability distribution. For some problems, it is now possible to use more sophisticated MCMC techniques to sample perfectly (that is, without error) from the distribution of interest. The investigator and his colleagues work on creating, improving, analyzing, and applying efficient perfect simulation algorithms; these algorithms include the Fill-Machida-Murdoch-Rosenthal algorithm and the new Randomness Recycler technique pioneered by the investigator and his colleague Mark Huber. The second focus concerns probability and combinatorial structures, especially trees. The investigator and his colleagues study such problems as characterizing the "shape" of random multiway search trees (via fundamental research in the area of analytic combinatorics known as singularity analysis); generalizing the analyses of the height of a random incomplete digital search tree, of the move-to-front rule for self- organizing lists, and of recursive trees; and extending the so-called generalized smoothing transformation to distributions on the entire real line.One focus of the investigator's research is perfect simulation from probability distributions. Standard "Markov chain Monte Carlo" (MCMC) methods for approximate simulation from complicated probability distributions have proved extremely useful for problems in statistics (including image analysis), physics (including models for magnetism and for phase changes), and computer science as a way of sampling approximately from a complicated probability distribution. But there are problems with the MCMC approach -- most notably that for many problems it is unknown for how long the simulations must be run in order to come close to the distribution of interest. For some problems, it is now possible to use more sophisticated MCMC techniques to sample perfectly (that is, without error) from the distribution of interest. The investigator and his colleagues work on creating, improving, analyzing, and applying efficient perfect simulation algorithms, including two different algorithms pioneered by the investigator. The second focus concerns interplays between probability and combinatorial structures, especially trees, which are fundamental structures for the storage of computer data. This second focus of research has applications to the modeling of epidemics, family trees of ancient manuscripts, and pyramid schemes and to the election of multiple leaders in a multiprocessor computer network.

研究的重点之一就是完美模拟。马尔可夫链蒙特卡罗(MCMC)近似抽样方法作为一种从复杂概率分布中近似抽样的方法，在贝叶斯推理问题和其他领域的问题(如空间统计学、统计物理和计算机科学)中已变得非常流行。对于一些问题，现在可以使用更复杂的MCMC技术从兴趣分布中完美地(即，没有错误地)抽样。这位研究人员和他的同事致力于创建、改进、分析和应用高效的完美模拟算法；这些算法包括填充-马奇达-默多克-罗森塔尔算法和由研究人员和他的同事马克·胡贝尔开创的新的随机性循环技术。第二个关注点是概率和组合结构，尤其是树。研究人员和他的同事们研究了如下问题：刻画随机多路搜索树的“形状”(通过称为奇点分析的解析组合学领域的基础研究)；推广随机不完全数字搜索树的高度分析、自组织列表的前移规则和递归树的分析；以及将所谓的广义平滑变换扩展到整个实数行上的分布。研究人员的研究重点之一是从概率分布进行完美模拟。对于统计(包括图像分析)、物理(包括磁性模型和相变模型)和计算机科学中的复杂概率分布的近似模拟，标准的马尔可夫链蒙特卡罗(MCMC)方法被证明是非常有用的。但MCMC方法也有问题--最明显的是，对于许多问题，为了接近兴趣分布，模拟必须运行多长时间是未知的。对于一些问题，现在可以使用更复杂的MCMC技术从兴趣分布中完美地(即，没有错误地)抽样。研究人员和他的同事致力于创建、改进、分析和应用高效的完美模拟算法，包括由研究人员首创的两种不同的算法。第二个焦点涉及概率和组合结构之间的相互作用，特别是树，这是存储计算机数据的基本结构。这第二个研究重点应用于流行病的建模、古代手稿的家谱和传销计划，以及在多处理器计算机网络中选举多个领导人。