Premium
Poisson approximations for functionals of random trees
Author(s) -
Dobrow Robert P.,
Smythe Robert T.
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199608/09)9:1/2<79::aid-rsa5>3.0.co;2-8
Subject(s) - poisson distribution , mathematics , limit (mathematics) , simple (philosophy) , tree (set theory) , binary tree , random variable , approximations of π , random tree , discrete mathematics , combinatorics , statistics , computer science , mathematical analysis , philosophy , epistemology , motion planning , artificial intelligence , robot
We use Poisson approximation techniques for sums of indicator random variables to derive explicit error bounds and central limit theorems for several functionals of random trees. In particular, we consider (i) the number of comparisons for successful and unsuccessful search in a binary search tree and (ii) internode distances in increasing trees. The Poisson approximation setting is shown to be a natural and fairly simple framework for deriving asymptotic results. © 1996 John Wiley & Sons, Inc.