Dependence between path-length and size in random digital trees

DOI10.1017/JPR.2017.56MaRDI QIDQ4684912zbMATH OpenOpenAlexFDO

Authors Michael Fuchs, Hsien-Kuei Hwang

Publication date 26 September 2018

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.02397

zbMATH Keywords

asymptotic normalitycontraction methodcovariancede-Poissonizationintegral transformPearson's correlation coefficientPoissonizationrandom triestotal path length

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Data structures (68P05)

Abstract: 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.

Recommendations

• Dependence between external path-length and size in random tries
• scientific article; zbMATH DE number 3961005
• On The variance of the extremal path length in a symmetric digital trie
• A note on the asymptotic behavior of the depth of tries
• scientific article; zbMATH DE number 1512698

Cites work

• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• A survey of multivariate aspects of the contraction method
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Analytic variations on bucket selection and sorting
• Analytical depoissonization and its applications
• Asymptotic variance of random symmetric digital search trees
• Dependence and phase changes in random m-ary search trees
• Digital Search Trees Revisited
• Dynamical sources in information theory: A general analysis of trie structures
• Generating random permutations by coin tossing: classical algorithms, new analysis, and modern implementation
• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 46747 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Mellin transforms and asymptotics: Harmonic sums
• New results on the size of tries
• On some applications of formulae of Ramanujan in the analysis of algorithms
• On the variance of a class of inductive valuations of data structures for digital search
• On The variance of the extremal path length in a symmetric digital trie
• The multivariate normal distribution
• The Ubiquitous Digital Tree
• The Wiener index of random digital trees
• Universal asymptotics for random tries and PATRICIA trees
• Universal Limit Laws for Depths in Random Trees

Cited in

(2)

• Imbalance in random digital trees
• Dependence between external path-length and size in random tries

This page was built for publication: Dependence between path-length and size in random digital trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684912)