Hsien-Kuei Hwang ; Michael Fuchs ; Vytas Zacharovas - Asymptotic variance of random symmetric digital search trees

dmtcs:498 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 2 - https://doi.org/10.46298/dmtcs.498
Asymptotic variance of random symmetric digital search treesArticle

Authors: Hsien-Kuei Hwang 1; Michael Fuchs 2; Vytas Zacharovas 1

  • 1 Institute of Statistical Science
  • 2 Department of Applied Mathematics [Hsinchu]

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.


Volume: Vol. 12 no. 2
Published on: January 1, 2010
Imported on: March 26, 2015
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]

Consultation statistics

This page has been seen 297 times.
This article's PDF has been downloaded 227 times.