Dependence between path-length and size in random digital trees

We study the size and the external path length of random tries and show that they are asymptotically independent in the asymmetric case but strongly dependent with small periodic fluctuations in the symmetric case. Such an unexpected behavior is in sharp contrast to the previously known results on random tries that the size is totally positively correlated to the internal path length and that both tend to the same normal limit law. These two dependence examples provide concrete instances of bivariate normal distributions (as limit laws) whose correlation is $0$, $1$ and periodically oscillating. Moreover, the same type of behaviors is also clarified for other classes of digital trees such as bucket digital trees and Patricia tries.

• Publication year

  2017

• Venue

  Journal of Applied Probability

• Publication date

  2017-01-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/jpr.2017.56arXiv 1701.02397
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Generating Random Permutations by Coin Tossing

  2017cited by this paper
• Dependence between External Path-Length and Size in Random Tries

  2016cited by this paper
• The Wiener Index of Random Digital Trees

  2015influential reference
• Dependence and phase changes in random m‐ary search trees

  2015cited by this paper
• A General Central Limit Theorem for Shape Parameters of $m$-ary Tries and PATRICIA Tries

  2014cited by this paper
• An analytic approach to the asymptotic variance of trie statistics and related structures

  2013influential reference
• Asymptotic variance of random symmetric digital search trees

  2009cited by this paper
• The Ubiquitous Digital Tree

  2006cited by this paper
• A survey of multivariate aspects of the contraction method

  2006influential reference
• Universal Asymptotics for Random Tries and PATRICIA Trees

  2005cited by this paper
• A general limit theorem for recursive algorithms and combinatorial structures

  2004cited by this paper
• Average case analysis-based protocols to initialize packet radio networks

  2003cited by this paper
• Analytic variations on bucket selection and sorting

  2000cited by this paper
• Dynamical Sources in Information Theory : A General Analysis of Trie Structures

  1999cited by this paper
• Universal Limit Laws for Depths in Random Trees

  1999cited by this paper
• Analytical Depoissonization and its Applications

  1998cited by this paper
• The Art of Computer Programming: Volume 3: Sorting and Searching

  1998cited by this paper
• Mellin Transforms and Asymptotics: Harmonic Sums

  1995cited by this paper
• On the Variance of a Class of Inductive Valuations of Data Structures for Digital Search

  1995cited by this paper
• Evolution of random search trees

  1991influential reference
• ON SOME APPLICATIONS OF FORMULAE OF RAMANUJAN IN THE ANALYSIS OF ALGORITHMS

  1991cited by this paper
• Multiple Access Protocols: Performance and Analysis

  1990cited by this paper
• Onthevarianceoftheexternalpathlengthin a Symmetric Digital Trle*

  1989cited by this paper
• New results on the size of tries

  1989influential reference
• Trie Partitioning Process: Limiting Distributions

  1986influential reference
• Digital Search Trees Revisited

  1986cited by this paper
• The Art of Computer Programming

  1968cited by this paper

• Energy-Efficient Naming in Beeping Networks

  2021cites this paper