Studies in Perfect Simulation and Combinatorial Probability

研究的一个重点是完美模拟。马尔可夫链蒙特卡罗（MCMC）近似抽样方法在贝叶斯推理问题和其他领域的问题中非常流行，例如空间统计、统计物理和计算机科学，作为一种从复杂概率分布中近似抽样的方法。对于某些问题，现在可以使用更复杂的MCMC技术从感兴趣的分布中进行完美采样（即没有误差）。研究者和他的同事们致力于创造、改进、分析和应用高效的完美模拟算法；这些算法包括Fill-Machida-Murdoch-Rosenthal算法和由研究者和他的同事Mark Huber首创的新的随机性回收技术。第二个重点是关于概率和组合结构，特别是树。研究者和他的同事们研究的问题包括描述随机多路搜索树的“形状”（通过被称为奇点分析的分析组合学领域的基础研究）；推广了随机不完全数字搜索树的高度分析、自组织列表的前移规则和递归树的高度分析；将所谓的广义平滑变换推广到整个实直线上的分布。研究者研究的一个重点是概率分布的完美模拟。从复杂概率分布中进行近似模拟的标准“马尔可夫链蒙特卡罗”（MCMC）方法已被证明对统计学（包括图像分析）、物理学（包括磁性和相变模型）和计算机科学中的问题非常有用，这是一种从复杂概率分布中进行近似采样的方法。但MCMC方法也存在问题——最明显的是，对于许多问题来说，模拟必须运行多长时间才能接近兴趣分布是未知的。对于某些问题，现在可以使用更复杂的MCMC技术从感兴趣的分布中进行完美采样（即没有误差）。研究者和他的同事们致力于创造、改进、分析和应用高效的完美模拟算法，包括研究者开创的两种不同的算法。第二个重点是关于概率和组合结构之间的相互作用，特别是树，这是计算机数据存储的基本结构。第二个研究重点可以应用于流行病的建模、古代手稿的家谱、传销计划以及多处理器计算机网络中多个领导人的选举。

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.