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.

Agency
National Science Foundation (NSF)
Institute
Division of Mathematical Sciences (DMS)
Type
Standard Grant (Standard)
Application #
9626597
Program Officer
Dean M Evasius
Project Start
Project End
Budget Start
1996-09-01
Budget End
1999-08-31
Support Year
Fiscal Year
1996
Total Cost
$56,000
Indirect Cost
Name
Truman State University
Department
Type
DUNS #
City
Kirksville
State
MO
Country
United States
Zip Code
63501