Mathematical Sciences: Poisson Approximation, Markov Chains, and Random Trees

数学科学：泊松近似、马尔可夫链和随机树

• 批准号: 9626597
• 负责人: Robert Dobrow
• 金额: $ 5.6万
• 依托单位: Truman State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-09-01 至 1999-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9626597&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Poisson; Approximation; Markov

9626597 Dobrow ABSTRACT Trees are fundamental data structures in computer science and have been the focus of much recent work in probability. The investigator applies modern approximation and Markov chain techniques to the study of random tree models. The work focuses on exploring the applicability of Chen-Stein techniques for Poisson approximation to obtain distributional results for functionals of random trees. The project also addresses the analysis of self-organizing random trees and the efficacy of using Markov chain Monte Carlo techniques to generate near-random search trees. The project has significance for the design and analysis of algorithms, particularly in computer science. Tree models also arise in statistics, physics, chemistry, sociology, and numerous other scientific areas. A first line of investigation into the behavior of such trees is to consider how a ``typical'' tree behaves. Thus a random model is postulated and characteristics of the ``random tree'' are studied. The methods that the investigator considers have previously been applied with success in several other areas of probability and statistics.

9626597 Dobrow抽象树是计算机科学中的基本数据结构，也是最近概率学工作的焦点。研究人员将现代逼近和马尔可夫链技术应用到随机树模型的研究中。这项工作的重点是探索Poisson近似的Chen-Stein技巧在获得随机树泛函的分布结果方面的适用性。该项目还讨论了自组织随机树的分析以及使用马尔科夫链蒙特卡罗技术生成近随机搜索树的有效性。该项目对算法的设计和分析具有重要意义，特别是在计算机科学中。树模型也出现在统计学、物理学、化学、社会学和许多其他科学领域。对这种树的行为进行调查的第一条线是考虑一棵“典型”树的行为。因此，假设了一个随机模型，并研究了“随机树”的特性。研究人员认为的方法以前已经成功地应用于概率和统计学的其他几个领域。