eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2010-01-01
Vol. 12 no. 2
10.46298/dmtcs.498
498
journal article
Asymptotic variance of random symmetric digital search trees
Hsien-Kuei Hwang
Michael Fuchs
Vytas Zacharovas
Dedicated to the 60th birthday of Philippe Flajolet
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 (logn)(2)-variance for certain notions of total path-length is also clarified.
https://dmtcs.episciences.org/498/pdf
Digital search trees
Poisson generating functions
Poissonization
Laplace transform
Mellin transform
saddle-point method
Colless index
weighted path-length
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]