Limiting distributions for additive functionals on Catalan trees

Details Limiting distributions for additive functionals on Catalan trees Limiting distributions for additive functionals on Catalan trees

2003-06-13

arxiv.org/abs/math/0306226v2

Theoret. Comput. Sci. 326 (2004) 69-102

Mathematics

Probability

30 pages, 4 figures. Version 2 adds background information on singularity analysis and streamlines the presentation

Scientific paper

10.1016/j.tcs.2004.05.010

Additive tree functionals represent the cost of many divide-and-conquer algorithms. We derive the limiting distribution of the additive functionals induced by toll functions of the form (a) n^\alpha when \alpha > 0 and (b) log n (the so-called shape functional) on uniformly distributed binary search trees, sometimes called Catalan trees. The Gaussian law obtained in the latter case complements the central limit theorem for the shape functional under the random permutation model. Our results give rise to an apparently new family of distributions containing the Airy distribution (\alpha = 1) and the normal distribution [case (b), and case (a) as $\alpha \downarrow 0$]. The main theoretical tools employed are recent results relating asymptotics of the generating functions of sequences to those of their Hadamard product, and the method of moments.

Affiliated with

Also associated with

No associations

Rating

Limiting distributions for additive functionals on Catalan trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Limiting distributions for additive functionals on Catalan trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Limiting distributions for additive functionals on Catalan trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26823