Probability and Algorithms

PI的研究包括使用不动点方法，矩量方法和复解析奇点分析来研究随机树上的加性泛函，这些泛函在分治算法的分析中出现。它试图用连续随机树和布朗偏移或其他方法来解释在各种随机树模型中观察到的分布的不变性。在随机置换模型下，对具有大分支因子的树的可加泛函的周期渐近分布行为进行了细致的分析，并推广到树模型和多类型分支过程。此外，该研究还包括数字分析和搜索和排序算法的改进，如广泛使用的快速排序；使用由PI首创的完美模拟算法来统计估计马尔可夫链的混合时间；以及Mellin变换在高斯随机场小偏差（小球概率）研究中的新应用。要进行的研究是在概率和计算机科学的界面上进行的。它涉及复杂概率分布的计算机模拟的高效算法的设计和应用；快速排序是Unix系统中的标准排序程序，在2000年的一篇计算机科学评论论文中，它被列为上世纪对科学和工程的发展和实践影响最大的十大算法之一；以及将常用的算法分析工具（“梅林变换”）新颖地应用于概率区域（“小偏差”，涉及对某些不常见事件的概率的估计）。

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).