Renewals for exponentially increasing lifetimes, with an application to digital search trees

Abstract

We show that the number of renewals up to time $t$ exhibits distributional fluctuations as $t\to \infty$ if the underlying lifetimes increase at an exponential rate in a distributional sense. This provides a probabilistic explanation for the asymptotics of insertion depth in random trees generated by a bit-comparison strategy from uniform input; we also obtain a representation for the resulting family of limit laws along subsequences. Our approach can also be used to obtain rates of convergence.

Published at http://dx.doi.org/10.1214/105051606000000862 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Rounding of continuous random variables and oscillatory asymptotics

Cited by in corpus (3)

• On the silhouette of binary search trees
• Renewal theory in analysis of tries and strings
• Asymptotic variance of random symmetric digital search trees