Probability and Algorithms

概率与算法

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

The PI's research includes the use of fixed-point methods,the method of moments, and complex-analytic singularity analysis tostudy additive functionals on random trees, which arise in theanalysis of divide-and-conquer algorithms. It seeks to explain,using continuum random trees and Brownian excursion or otherwise, aninvariance of distributions observed across various random-treesmodels. A refined analysis, under the so-called random permutationmodel, of the periodic asymptotic distributional behavior ofadditive functionals for trees with large branching factor alsoextends to urn models and multi-type branching processes.Additionally, the research encompasses digital analyses andimprovements of algorithms for searching and sorting, such as thewidely-used Quicksort; use of a perfect simulation algorithmpioneered by the PI to estimate mixing times of Markov chainsstatistically; and the novel application of Mellin transforms to thestudy of small deviations (small-ball probabilities) for Gaussianrandom fields.The research to be performed lies at the interface of probabilityand computer science. It involves the design and application ofefficient algorithms for computer simulation from complicatedprobability distributions; the probabilistic analysis of algorithmsand data structures arising in connection with such basic andimportant algorithms as Quicksort, which is the standard sortingprocedure in Unix systems and which, in a computer science reviewpaper in 2000, was cited as one of the ten algorithms with thegreatest influence on the development and practice of science andengineering in the last century; and the novel application of acommon analysis-of-algorithms tool ("Mellin transforms") to an areaof probability ("small deviations", involving the estimation of thechance of certain uncommon events).

PI的研究包括使用不动点方法，矩量法和复解析奇异性分析来研究随机树上的加性泛函，这是在分治算法的分析中出现的。 它试图解释，使用连续随机树和布朗偏移或其他方式，在各种随机树模型中观察到的分布的不变性。 在所谓的随机置换模型下，对具有大分支因子的树的可加泛函的周期渐近分布行为的精细分析也扩展到了瓮模型和多类型分支过程，此外，研究还包括数字分析和搜索和排序算法的改进，如广泛使用的Quicksort;利用PI开创的完美模拟算法对马尔可夫链的混合时间进行统计估计;以及梅林变换在小偏差研究中的新应用高斯随机场的小球概率问题是概率论与计算机科学的交叉点。 它涉及从复杂的概率分布的计算机模拟的有效算法的设计和应用;对算法和数据结构的概率分析，这些算法和数据结构与快速排序等基本和重要算法有关，快速排序是Unix系统中的标准排序过程，在2000年的一篇计算机科学评论论文中，被誉为上个世纪对科学和工程发展和实践影响最大的十大算法之一;以及将常用的算法分析工具（“梅林变换”）应用于概率领域（“小偏差”，涉及对某些不寻常事件发生概率的估计）的新应用。