An analytic approach to the asymptotic variance of trie statistics and related structures This paper is dedicated to the memory of Philippe Flajolet, who pioneered the asymptotic study of binomial splitting processes

Michael Fuchs*, Hsien Kuei Hwang, Vytas Zacharovas

*Corresponding author for this work

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

We develop analytic tools for the asymptotics of general trie statistics, which are particularly advantageous for clarifying the asymptotic variance. Many concrete examples are discussed for which new Fourier expansions are given. The tools are also useful for other splitting processes with an underlying binomial distribution. We specially highlight Philippe Flajolet's contribution in the analysis of these random structures.

Original languageEnglish
Pages (from-to)1-36
Number of pages36
JournalTheoretical Computer Science
Volume527
DOIs
StatePublished - 27 Mar 2014

Keywords

  • Binomial splitting process
  • Contention resolution algorithms
  • Digital trees
  • Mellin transform
  • Periodic fluctuations
  • Variance

Fingerprint Dive into the research topics of 'An analytic approach to the asymptotic variance of trie statistics and related structures This paper is dedicated to the memory of Philippe Flajolet, who pioneered the asymptotic study of binomial splitting processes'. Together they form a unique fingerprint.

Cite this