Asymptotic variance of random symmetric digital search trees
Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas
Abstract
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