Asymptotic variance of random symmetric digital search trees

Details Asymptotic variance of random symmetric digital search trees Asymptotic variance of random symmetric digital search trees

2009-12-31

arxiv.org/abs/1001.0095v2

Mathematics

Combinatorics

Scientific paper

Asymptotics of the variances of many cost measures in random digital search trees are often notoriously messy and involved to obtain. A new approach is proposed to facilitate such an analysis for several shape parameters on random symmetric digital search trees. Our approach starts from a more careful normalization at the level of Poisson generating functions, which then provides an asymptotically equivalent approximation to the variance in question. Several new ingredients are also introduced such as a combined use of the Laplace and Mellin transforms and a simple, mechanical technique for justifying the analytic de-Poissonization procedures involved. The methodology we develop can be easily adapted to many other problems with an underlying binomial distribution. In particular, the less expected and somewhat surprising $n(\log n)^2$-variance for certain notions of total path-length is also clarified.

Affiliated with

Also associated with

No associations

Rating

Asymptotic variance of random symmetric digital search 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 Asymptotic variance of random symmetric digital search trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic variance of random symmetric digital search trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104370