Discrete Mathematics & Theoretical Computer Science, Vol 12, No 2 (2010)

Font Size:  Small  Medium  Large

Asymptotic variance of random symmetric digital search trees

Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas


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 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.

Full Text: PDF PostScript