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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.103-165
Liste complète des métadonnées

Littérature citée [61 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990457
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:37:33
Dernière modification le : mercredi 24 janvier 2018 - 10:46:02
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:20:25

Fichier

1489-4997-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990457, version 1

Collections

Citation

Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas. Asymptotic variance of random symmetric digital search trees. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (2), pp.103-165. 〈hal-00990457〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

169