Continuous-time digital search tree and a border aggregation model

Janson, Svante; Thacker, Debleena

Abstract

We consider the continuous-time version of the random digital search tree, and construct a coupling with a border aggregation model as studied in Thacker and Volkov (Ann. Appl. Probab. 28 (2018) 1604–1633), showing a relation between the height of the tree and the time required for aggregation. This relation carries over to the corresponding discrete-time models. As a consequence we find a very precise asymptotic result for the time to aggregation, using recent results by Drmota et al. (Random Structures Algorithms 58 (2021) 430–467) for the digital search tree.

Citation

Janson, S., & Thacker, D. (2022). Continuous-time digital search tree and a border aggregation model. Bernoulli (Andover), 28(4), 2563-2577. https://doi.org/10.3150/21-bej1429

• Journal Article Type: Article
• Online Publication Date: Aug 17, 2022
• Publication Date: 2022-11
• Deposit Date: Oct 26, 2022
• Publicly Available Date: Oct 31, 2022
• Journal: Bernoulli
• Print ISSN: 1350-7265
• Publisher: Bernoulli Society for Mathematical Statistics and Probability
• Peer Reviewed: Peer Reviewed
• Volume: 28
• Issue: 4
• Pages: 2563-2577
• DOI: https://doi.org/10.3150/21-bej1429