Poisson approximations for functionals of random trees

✍ Scribed by Robert P. Dobrow; Robert T. Smythe

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 543 KB
• Volume: 9
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199608/09)9:1/2<79::aid-rsa5>3.0.co;2-8

✦ Synopsis

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.