Renewals for exponentially increasing lifetimes, with an application to digital search trees
We show that the number of renewals up to time exhibits distributional fluctuations as 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.