Skip to Main content Skip to Navigation
Journal articles

Asymptotic variance of random symmetric digital search trees

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 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [61 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:37:33 PM
Last modification on : Wednesday, January 24, 2018 - 10:46:02 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:20:25 PM


Files produced by the author(s)




Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas. Asymptotic variance of random symmetric digital search trees. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, Vol. 12 no. 2 (2), pp.103-165. ⟨10.46298/dmtcs.498⟩. ⟨hal-00990457⟩



Record views


Files downloads