Node profiles of symmetric digital search trees: Concentration properties. Issue 3 (24th November 2020)

• Record Type: Journal Article
• Authors: Drmota, Michael; Fuchs, Michael; Hwang, Hsien‐Kuei; Neininger, Ralph
• Is Part Of: Random structures & algorithms. Volume 58:Issue 3(2021)
• Page Start: 430
• Page End: 467
• Publication Date: 2020-11-24
• Subjects: asymptotic transfer -- digital search tree -- double‐indexed recurrence -- Laplace transform -- level profile -- Mellin transform -- Poissonization -- two‐point concentration; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20979
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We give a detailed asymptotic analysis of the profiles of random symmetric digital search trees, which are in close connection with the performance of the search complexity of random queries in such trees. While the expected profiles have been analyzed for several decades, the analysis of the variance turns out to be very difficult and challenging, and requires the combination of several different analytic techniques, including Mellin and Laplace transforms, analytic de‐Poissonization, and Laplace convolutions. Our results imply concentration of the profiles in the range where the mean tends to infinity. Moreover, we also obtain a two‐point concentration for the distributions of the height and the saturation level.