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

点击翻译按钮获取中文摘要

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.