{"docId":498,"paperId":498,"url":"https:\/\/dmtcs.episciences.org\/498","doi":"10.46298\/dmtcs.498","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":89,"name":"Vol. 12 no. 2"}],"section":[],"repositoryName":"Hal","repositoryIdentifier":"hal-00990457","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00990457v1","dateSubmitted":"2015-03-26 16:20:54","dateAccepted":"2015-06-09 14:47:36","datePublished":"2010-01-01 08:00:00","titles":{"en":"Asymptotic variance of random symmetric digital search trees"},"authors":["Hwang, Hsien-Kuei","Fuchs, Michael","Zacharovas, Vytas"],"abstracts":{"0":"Dedicated to the 60th birthday of Philippe Flajolet","en":"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."},"keywords":[["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]"]}