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