Renewals for exponentially increasing lifetimes, with an application to digital search trees
The Annals of Applied Probability
2007, Vol. 17, No. 2, 676–687
DOI: 10.1214/105051606000000862
c© Institute of Mathematical Statistics, 2007
RENEWALS FOR EXPONENTIALLY INCREASING LIFETIMES,
WITH AN APPLICATION TO DIGITAL SEARCH TREES
By Florian Dennert and Rudolf Grübel
Universität Hannover
We show that the number of renewals up to time t exhibits distri-
butional fluctuations as t→∞ if the underlying lifetimes increase at
an exponential rate in a distributional sense. This provides a proba-
bilistic 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.
1. Introduction. Let (Yk)k∈N be a sequence of independent, nonnegative
random variables and let (Sn)n∈N0 ,
S0 := 0, Sn :=
Yk for all n ∈N,
be the associated sequence of partial sums. Regarding the Yk’s as successive
lifetimes and Sn as the time of the nth renewal, we interpret
Nt := sup{n ∈N0 :Sn ≤ t}
as the number of renewals up to and including time t; (Nt)t≥0 is the renewal
process. Standard renewal theory assumes that the Yk’s all have the same
distribution, in which case Nt, appropriately rescaled, is asymptotically nor-
mal as t→∞. For this result, and for renewal theory in general, we refer
the reader to Section XI in [3].
In this note we consider exponentially increasing lifetimes. We show that
in such a case the distribution of Nt does not converge and that asymp-
totic distributional fluctuations appear (Section 2). Such fluctuations occur
frequently in the analysis of algorithms. The renewal theoretic framework
Received January 2006.
AMS 2000 subject classifications. Primary 60K05; secondary 68Q25.
Key words and phrases. Asymptotic distributional behavior, limiting periodicities, re-
newal processes.
This is an electronic reprint of the original article published by the
Institute of Mathematical Statistics in The Annals of Applied Probability,
2007, Vol. 17, No. 2, 676–687. This reprint differs from the original in pagination
and typographic detail.
http://arxiv.org/abs/0704.0398v1
http://www.imstat.org/aap/
http://dx.doi.org/10.1214/105051606000000862
http://www.imstat.org
http://www.ams.org/msc/
http://www.imstat.org
http://www.imstat.org/aap/
http://dx.doi.org/10.1214/105051606000000862
2 F. DENNERT AND R. GRÜBEL
provides a probabilistic view of this phenomenon in connection with digital
search trees (Section 3). We also indicate how our approach can be used to
obtain rates of convergence (Section 4).
2. Renewals for increasing lifetimes. We assume that the lifetimes in-
crease exponentially with rate α, where α> 1 is fixed throughout the sequel,
in the sense that
α−kYk →distr Y∞ and α−kEYk →EY∞(1)
for some random variable Y∞ and as k→∞. Here “→distr” denotes conver-
gence in distribution, so that the first part of (1) means that
Ef(α−kYk) =Ef(Y∞)
for all bounded continuous functions f :R→ R. Below we will use the fact
that in order to prove Xn →distr X it is sufficient to show that Ef(Xn)→
Ef(X) holds for all bounded and uniformly continuous functions. For details
and a general treatment of convergence in distribution we refer the reader
to [1]. Of course, only the distribution µ = L(Y∞) of Y∞ matters, so we
will occasionally write α−kYk →distr µ instead. Finally, throughout this note
a condition involving moments is meant to imply that these moments are
finite.
An important role will be played by
S∞ :=
α−kY∞,k,
where (Y∞,k)k∈N0 is a sequence of independent and identically distributed
random variables with L(Y∞,0) = L(Y∞), Y∞ as in (1). From EY∞ <∞ we
obtain ES∞ = α(α − 1)−1EY∞ <∞ and therefore P (S∞ <∞) = 1; more-
over, we then also have that
−kY∞,k converges almost surely and
hence in distribution to S∞ as n→∞. We will also assume that L(Y∞) has
no atoms, that is,
P (Y∞ = y) = 0 for all y ∈R+.(2)
Finally, it is an elementary analytic fact that, for a sequence (xn)n∈N of real
numbers with limit x ∈R,
α−kxn−k =
The following lemma can be regarded as a random version of (3).
Lemma 1. If (1) and (2) are satisfied, then α−nSn →distr S∞ as n→∞,
and P (S∞ = y) = 0 for all y ∈R.
RENEWALS FOR INCREASING LIFETIMES 3
Proof. Suppose that (Uk)k∈N is a sequence of independent random
variables on some probability space (Ω,A, P ), all uniformly distributed on
the unit interval. Let Fk be the distribution function of Yk, F the distribution
function of Y∞. We use a variant of the quantile construction:
Ỹk := F
k (Uk), Ỹ∞,k := F
−1(Uk) for all k ∈N.
We then have L(Ỹ1, . . . , Ỹn) = L(Y1, . . . , Yn) for all n ∈N, which implies
L(α−nSn) =L(α−nS̃n) with S̃n :=
Using α−nS̃n =
k=0 α
−k(α−(n−k)Ỹn−k) we obtain
α−nS̃n −
α−kỸ∞,n−k
α−kE|α−(n−k)Ỹn−k − Ỹ∞,n−k|.(4)
With Y ′k := F
k (U1) and Y
∞ := F
−1(U1) we have
E|α−kỸk − Ỹ∞,k|=E|α−kY ′k − Y ′∞|.(5)
From (1) it follows that α−kY ′k →distr Y ′∞ and Eα−kY ′k → EY ′∞. Because
of Y ′k, Y
∞ ≥ 0 Theorem 5.4 in [1] applies and gives the L1-convergence of
α−kY ′k to Y
∞, that is, E|α−kY ′k − Y ′∞| → 0 as k →∞. Using this together
with (3), (4) and (5) we obtain
α−nS̃n −
α−kỸ∞,n−k
= 0.(6)
Now let f :R→R be bounded and uniformly continuous. We have
|Ef(α−nSn)−Ef(S∞)|=
Ef(α−nS̃n)−Ef
α−kỸ∞,n−k
α−kỸ∞,k
α−kỸ∞,k
f(α−nS̃n)− f
α−kỸ∞,n−k
α−kỸ∞,k
α−kỸ∞,k
For the first integral on the right-hand side we use (6), for the second an
elementary estimate shows that the difference between the arguments of f
converges to 0 in probability. In both cases we now use uniform continuity
4 F. DENNERT AND R. GRÜBEL
when the arguments of f are close to each other and boundedness otherwise.
This leads to
Ef(α−nSn) =Ef(S∞),
which gives the convergence in distribution. The statement about the atoms
of S∞ follows from (2) and the fact that S∞ is equal in distribution to
Y∞ + α
−1S∞ with Y∞ and S∞ independent. �
The above proof is based on classical weak convergence arguments. An
alternative proof can be obtained via the Wasserstein distance
dW (µ, ν) = inf{E|X − Y | :L(X) = µ,L(Y ) = ν},
its known relation to weak convergence and convergence of the first moments,
and the same variant of the quantile construction, which in this context is
known as the comonotone coupling.
We write ⌊x⌋ for the greatest integer less than or equal to x and {x} for
the fractional part of x ∈R.
Theorem 2. Suppose that (1) and (2) are satisfied and let
Qη := L(⌊− logαS∞ + η⌋), 0≤ η ≤ 1.(7)
If (tn)n∈N is a sequence of real numbers with tn →∞ and such that {logα tn}→
η for some η ∈ [0,1], then
Ntn − ⌊logα tn⌋→distr Qη as n→∞.
Proof. We use the abbreviations kn := ⌊logα tn⌋ and ηn := {logα tn}. In
particular, logα tn = kn + ηn. Further, let Z∞ := − logαS∞. By a standard
renewal theoretic argument,
P (Nt = j) = P (Sj ≤ t)−P (Sj+1 ≤ t) for all t≥ 0, j ∈N0,
hence
P (Ntn − kn = j) = P (Skn+j ≤ tn)− P (Skn+j+1 ≤ tn)
= P (− logα(α−kn−jSkn+j) + ηn ≥ j)
−P (− logα(α−kn−j−1Skn+j+1) + ηn ≥ j + 1)
→ P (⌊Z∞ + η⌋= j) as n→∞,
where in the last step Lemma 1 and three general facts about convergence
in distribution were used: First, the continuous mapping theorem, which
implies that − logα(α−mSm)→distr − logαS∞ as m→∞; secondly, the in-
terplay with convergence in probability, see Theorem 4.1 in [1], which yields
RENEWALS FOR INCREASING LIFETIMES 5
− logα(α−nSn)+ ηn →distr − logαS∞+ η as n→∞; finally, that L(S∞) and
therefore also L(− logαS∞+η) assign probability 0 to single points and that
this implies
P (− logα(α−nSn) + ηn ≥ z) = P (− logαS∞ + η ≥ z) for all z ∈R.
A structural consequence of the representation (7) is the →distr-continuity
of η 7→Qη on the open unit interval; at η = 0 this function is right continuous,
at η = 1 it is left continuous. The extreme members are translates of each
other in the sense that Q0({j}) =Q1({j + 1}) for all j ∈ Z.
The total variation distance dTV of probability measures is defined by
dTV(µ, ν) := sup
|µ(B)− ν(B)|,
for µ, ν concentrated on Z this can be written as
dTV(µ, ν) =
|µ({j})− ν({j})|.(8)
For a sequence of probability measures that are concentrated on a fixed
countable set Scheffé’s lemma implies that weak convergence is equivalent
to convergence in total variation distance, hence (7) can be rewritten as
dTV(L(Ntn − ⌊logα tn⌋),Q{log
tn}) = 0.
Because of the continuity of [0,1] ∋ η 7→Qη this in turn leads to a statement
that avoids the use of subsequences,
dTV(L(Nt − ⌊logα t⌋),Q{log
t}) = 0.(9)
In Section 4 we will investigate the rate of convergence in (9) in a particular
case.
3. An application to digital search trees. The nodes of a (rooted, di-
rected) binary tree can be represented by finite strings of 0’s and 1’s if we
interpret 0 as a move to the left and 1 as a move to the right. The length of
the string is the depth (or level) of the node it represents, the root node corre-
sponds to the empty string and has level 0. The sequence (Tn)n∈N associated
with a sequence (xn)n∈N of numbers from the unit interval by the DST (dig-
ital search tree) algorithm is obtained as follows: For T1, we put x1 into the
root node. If x1, . . . , xn have been stored into Tn then the position of xn+1 is
determined by traveling through the tree with the direction given by the bi-
nary expansion of xn+1 until an empty node has been found. This algorithm
and its properties are discussed in the standard texts of the area, for exam-
ple, [8, 10, 11]. As an example we consider the first ten numbers given in [8],
6 F. DENNERT AND R. GRÜBEL
Fig. 1. Binary tree.
Appendix A, (
2, log 2, log 3, log 10). Let xi be the
fractional part of the ith entry, 1≤ i≤ 10; the relevant first four bits of the
respective binary expansions are given by (0110,1011,0011,0010, 0100,0111,
0011,1011,0001,0100). This leads to the binary tree given in Figure 1.
Consider now the sequence (Tn)n∈N0 of random trees that the DST algo-
rithm associates with a sequence (Un)n∈N of independent random variables,
where we assume that the Un’s are uniformly distributed on the unit inter-
val and that T0 is the empty tree. Let Xn(θ) be the depth of the first free
node of Tn along the path determined by a sequence θ ∈ {0,1}N. Such a θ
defines a family of nested intervals of length 2−k, k = 1,2,3, . . . , and it is
easy to see that (Xn(θ))n∈N0 is a Markov chain with X0(θ) ≡ 0 and tran-
sition probabilities pk,k+1 = 1− pk,k = 2−k for all k ∈ N0. Conditioning on
the value of Un+1 we see that the distribution of Xn(θ) is the same as the
distribution of Zn+1, the insertion depth of Un+1. This quantity is known
as “unsuccessful search” in the literature on the analysis of algorithms. [Of
course, this distributional equality does not hold for the joint distributions:
n 7→Xn(θ) is increasing, n 7→ Zn+1 is not.] For example, the next number
in Knuth’s list is x11 = 1/ log 2, the binary expansion of the fractional part
{x11} begins with 011100 and hence x11 would be inserted at level 4 as the
right child of x6.
The Markov chain (Xn(θ))n∈N0 is of the simple birth type and can there-
fore be described by its respective holding times Y1, Y2, Y3, . . . in the states
k = 0,1,2, . . . . These are independent, and Yk has a geometric distribution
with parameter pk−1,k, that is, for all k ∈N,
P (Yk = j) = (1− 2−k+1)j−12−k+1 for all j ∈N.
Here we interpret the case k = 1 as Y1, the holding time in 0, being constant
and equal to 1. As a result of its simple stochastic dynamics, (Xn(θ))n∈N0
is equal to the renewal process N associated with the sequence (Yk)k∈N,
observed at discrete times, that is, (Xn(θ))n∈N0 = (Nn)n∈N0 . It is easy to
see that for this sequence (Yk)k∈N of lifetimes conditions (1) and (2) are
satisfied and that L(Y∞) = Exp(2), with Exp(λ) the exponential distribution
RENEWALS FOR INCREASING LIFETIMES 7
with parameter λ (and mean 1/λ). Hence Theorem 2 can be applied: If the
sequence (n(m))m∈N ⊂ N is such that n(m) →∞ and {log2 n(m)} → η as
m→∞, then
Xn(m)(θ)− ⌊log2 n(m)⌋→distr Qη.(10)
Here Qη , 0≤ η ≤ 1, is the distribution of ⌊− log2 S∞+η⌋, S∞ :=
k=0 2
−kY∞,k
and Y∞,k, k ∈N0, are independent and identically distributed with L(Y∞,1) =
Exp(2). Alternatively, we can write S∞ :=
k=1 Ỹk with Ỹk, k ∈N, again in-
dependent and L(Ỹk) = Exp(2k) for all k ∈N.
The explicit representation of the family of limit distributions on the basis
of the convolution product of the distributions Exp(2k), k ∈N, can be used
to obtain a series expansion for the distribution functions associated with
Qη , 0 ≤ η ≤ 1. For this, we start with a partial fraction expansion: For all
n ∈N and all z ∈C with |ℜ(z)|< 2,
(1− 2−kz)−1 =
an,k(1− 2−kz)−1,(11)
where an,k :=
j=1(1− 2j)−1
j=1 (1− 2−j)−1. Reading (11) as an equality
relating characteristic functions we obtain
Exp(21) ⋆Exp(22) ⋆ · · · ⋆Exp(2n) =
an,kExp(2
k).(12)
Note, however, that the right-hand side in (12) is not the usual mixture of
probability distributions as the coefficients alternate in sign. With
ak := b
(1− 2j)−1, b :=
(1− 2−j)−1,
letting n→∞ in (12) leads to L(S∞) =
k=1 akExp(2
k), so that
Qη((−∞, x]) = P (⌊− log2(S∞) + η⌋ ≤ x)
= P (S∞ > 2
η−1−x)(13)
ak exp(−2k+η−1−x) for all x ∈ Z.
This representation of the limiting distribution functions as an alternating
series has already been obtained by Louchard [9] in the context of digital
search trees and by Flajolet [4] in the context of approximate counting; see
also Section 6.4 in [10] and Section 6.3 in [8] for related results. These authors
use a completely different approach, more analytic in flavor and relying on
combinatorial identities due to Euler.
8 F. DENNERT AND R. GRÜBEL
Our main point here, however, is not a rederivation of (13) but the rep-
resentation of the family {Qη : 0≤ η < 1} in terms of one particular random
variable, which is first shifted by η and then discretized. This representation
can, for example, be used to obtain information about the tail behavior of
the limit distributions. Janson [7] notes that (13) by itself would only give
an exponential rate of decrease for the tail probabilities, he then provides an
analytic argument that improves this to a superexponential rate by show-
ing that the associated Fourier transform is an entire function. Using the
representation S∞ =
k=1 2
−kZk with Zk independent and L(Zk) = Exp(1)
together with the fact that Exp(1) has a density bounded by 1, we get
P (S∞ ≤ 2−j)≤ P (Z1 ≤ 2−j+1)P (Z2 ≤ 2−j+2) · · ·P (Zj−1 ≤ 2−1)
≤ 2−j+12−j+2 · · ·2−1
= 2−j(j−1)/2
for all j ∈ N. Because of Qη([k,∞)) ≤ P (S∞ ≤ 2−k+1) for all k ∈ N, k ≥ 2,
this leads to
Qη([x,∞)) = o(exp(−ρx2)) as x→∞, for all ρ < (log 2)/2.
The fact that a representation by discretization is possible in many situ-
ations where fluctuations were first found by calculation seems to belong to
the folklore of the subject, at least in simple instances such as the asymp-
totic distributional behavior of the maximum of a sample from a geometric
distribution. The geometric case together with some renewal theoretic tech-
niques (for identically distributed lifetimes) was used in [5] to obtain results
of the above type for von Neumann addition. In [2] a discretization represen-
tation occurs on the level of stochastic processes, leading to a probabilistic
approach to fluctuation phenomena in the context of multiplicities of the
maximum in a random sample from a discrete distribution. In a recent pa-
per, Janson [7] studies the effects of discretizing random variables and the
resulting distributional fluctuations and gives a range of interesting exam-
ples. Of course, the explanation for periodicities can be, and indeed often is,
quite different and mechanisms other than discretization may be responsible;
see, for example, [6] and the references given there.
4. Rates of convergence. The renewal theoretic approach can also be
used to obtain rates of convergence. We sketch one of the possibilities, for
a particular choice of distances, and give details for the DST situation from
Section 3. Let, for t > 0, k(t) := ⌊logα t⌋ and η(t) := {logα t}.
The Kolmogorov–Smirnov distance of two probability measures µ and ν
on the real line is defined by
dKS(µ, ν) := sup
|µ((−∞, x])− ν((−∞, x])|.
RENEWALS FOR INCREASING LIFETIMES 9
If X and Y are real random variables, then we abbreviate dKS(L(X),L(Y ))
to dKS(X,Y ); if F and G are the associated distribution functions, then
dKS(X,Y ) = ‖F − G‖∞, where the supremum norm for general bounded
functions f :R → R is given by ‖f‖∞ := supx∈R |f(x)|. The Kolmogorov–
Smirnov distance is obviously invariant under strictly monotone transfor-
mations. For example,
dKS(αX + β,αY + β) = dKS(X,Y ) for all α,β ∈R, α 6= 0,
and for X,Y > 0,
dKS(X,Y ) = dKS(logX, logY ).
With the notation as in the proof of Theorem 2,
|P (Nt − k(t) = j)−P (⌊− logα(S∞) + η(t)⌋= j)|
≤ |P (− logα(α−k(t)−jSk(t)+j) + η(t)≥ j)−P (− logα(S∞) + η(t)≥ j)|
+ |P (− logα(α−k(t)−j−1Sk(t)+j+1) + η(t)≥ j +1)
− P (− logα(S∞) + η(t)≥ j + 1)|.
With the auxiliary quantities
Zt := ⌊− logα(S∞) + η(t)⌋, φ(m) := dKS(α−mSm, S∞)
and the above properties of the Kolmogorov–Smirnov distance this leads to
|P (Nt − k(t) = j)−P (Zt = j)| ≤ φ(k(t) + j) + φ(k(t) + j +1).(14)
It is often possible to obtain an upper bound for negative j, say j ≤−k(t)/2,
directly. In such cases the above elementary renewal theoretic argument leads
to a bound for the ‖ · ‖∞-distance between the probability mass functions of
Nt − k(t) and Zt, for example; note that the latter variable has distribution
Qη(t) where Qη , 0≤ η ≤ 1, is the set of limit distributions along subsequences
that appears in Theorem 2.
The above argument covers the step from (α−mSm)m∈N to (Nt)t≥0. How-
ever, in an application the starting point will usually be the convergence of
the scaled lifetimes in (1), which means that we also need an analogue for
Lemma 1 that gives rates of convergence.
We carry this out in the specific context of digital search trees. The fol-
lowing general bounds will turn out to be useful: If X has density fX and if
P (|Y | ≤ c) = 1, then
dKS(X,X + Y )≤ c‖fX‖∞.(15)
Indeed: For all z ∈R, P (X ≤ z− c)≤ P (X+Y ≤ z)≤ P (X ≤ z+ c), so that
|P (X + Y ≤ z)−P (X ≤ z)|
≤max{P (X ≤ z + c)−P (X ≤ z), P (X ≤ z)−P (X ≤ z − c)},
10 F. DENNERT AND R. GRÜBEL
and, of course, P (X ∈ (a, b]) ≤ (b − a)‖fX‖∞. This bound can easily be
generalized to
dKS(X,X + Y )≤ c‖fX‖∞ +P (|Y |> c) for all c > 0,(16)
where we still assume that X has density fX , but Y may be arbitrary.
Note that X and Y need not be independent in (15) and (16). If they are
independent then it is easy to show that
dKS(X,X + Y )≤ ‖fX‖∞E|Y |.(17)
In (17) boundedness of Y is not needed but the bound obviously makes sense
only if Y has finite first moment. Finally, in connection with density bounds
the interplay with convolution is of interest: We have ‖f ⋆ g‖∞ ≤ ‖f‖∞ for
all probability densities f, g. For example, if a sum of independent random
variables contains a summand with distribution Exp(λ), then the density of
the sum is bounded by λ.
Lemma 3. With (Yk)k∈N and S∞ as in Section 3,
dKS(2
−nSn, S∞) =O(n2
Proof. Let (Zk)k∈N be a sequence of independent random variables, all
exponentially distributed with parameter 1. Then S∞ is equal in distribution
k=1 2
−kZk. We recall that the kth lifetime Yk has a geometric distribu-
tion with parameter 2−k+1. On the basis of (Zk)k∈N we define a sequence
(Ỹk)k∈N by Ỹk := ⌊αkZk⌋+1 for all k ∈N, with
α1 := 0, αk := (− log(1− 2−k+1))−1 for k > 1.
It is easy to check that
(Ỹk)k∈N =distr (Yk)k∈N, 2
2k−1Zk =distr
2−kZk.
Hence, with φ(n) denoting the dKS-distance of 2
−nSn and S∞,
φ(n)≤ φ1(n) + φ2(n) + φ3(n) for all n ∈N,
with φ1, φ2, φ3 defined by
φ1(n) := dKS
Ỹk,2
φ2(n) := dKS
αkZk,2
2k−1Zk
φ3(n) := dKS
2−kZk,
2−kZk
RENEWALS FOR INCREASING LIFETIMES 11
For the random variables in φ1 we have
Vn ≤ 2−n
Ỹk ≤ Vn + n2−n with Vn := 2−n
αkZk.
It is easy to show that the densities of Vn, n ∈N, can be uniformly bounded
for all n by some finite constant C1, hence (15) implies that φ1(n)≤C1n2−n
for all n ∈N.
The elementary bounds
− 1≤−
log(1− x)
for 0< x≤
together with α1 = 0 imply supk∈N |αk − 2k−1|= 1, hence we have
αkZk − 2−n
2k−1Zk
≤ 2−n
The familiar combination of Markov’s inequality and moment generating
functions gives
Zk ≥ (1 + κ)n
=O(2−n)
if κ is chosen large enough, so that we can use (16) with c = c(n) = (1 +
κ)n2−n to obtain that φ2(n)≤C2n2−n for all n ∈N, for some finite constant
For φ3 finally we use (17): For the densities of the finite sums we again
have a finite uniform bound for all n, and
k=n+1
2−kZk
k=n+1
2−kEZk = 2
so that φ3(n) ≤ C32−n for all n ∈ N with some C3 <∞. Putting these to-
gether we arrive at
φ(n)≤Cn2−n for all n ∈N
with some finite constant C. �
In the application under consideration we obtain a rate of convergence
result with respect to the total variation distance, which is stronger than
a result for the supremum norm distance of the corresponding probability
mass functions that we mentioned in connection with (14).
Theorem 4. With (Xn(θ))n∈N and Qη as in Section 3,
dTV(L(Xn(θ)− ⌊log2 n⌋),Q{log2 n}) = o(n
−γ) for all γ < 1.
12 F. DENNERT AND R. GRÜBEL
Proof. We use the abbreviations k(n) := ⌊log2 n⌋ and η(n) := {log2 n}.
Let γ < 1 be given and choose ε > 0 such that ε < 1− γ. Lemma 3 together
with (14) gives
j≥−εk(n)
|P (Nn − k(n) = j)−Qη(n)({j})| ≤C
j≥(1−ε)k(n)
for all n ∈ N with some finite constant C. Our choice of ε implies that the
upper bound has the desired rate o(n−γ).
For the remaining part of the infinite sum in (8) we replace the absolute
difference of the probabilities by their sum, which means that it is now
enough to show that
P (Nn ≤ (1− ε)k(n)) = o(n−γ),(18)
P (− log2(S∞)≤−εk(n) + 1) = o(n−γ).(19)
Here we have used that Qη is the distribution of ⌊− log2(S∞)+ η⌋. It is easy
to show that the moment generating function for S∞ exists in a neighbor-
hood of 0, hence
P (S∞ > x) = o(e
−κx) for all x > 0(20)
with some κ > 0. Straightforward manipulations show that (20) implies (19);
indeed, the probability converges faster to 0 than any negative power of n.
Using once again the relation between the number of renewals and the partial
sums of the lifetimes we further obtain, with m(n, ε) := ⌊(1− ε)k(n)⌋,
P (Nn ≤ (1− ε)k(n)) ≤ P (Sm(n,ε) ≥ n)
= P (2−m(n,ε)Sm(n,ε) ≥ n2−m(n,ε))
≤ dKS(2−m(n,ε)Sm(n,ε), S∞) +P (S∞ ≥ n2−m(n,ε)).
For the Kolmogorov–Smirnov distance we use Lemma 3, for the tail of S∞
the desired rate follows with (20). This gives (18) and hence completes the
proof. �
REFERENCES
[1] Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York.
MR0233396
[2] Bruss, F. Th. and Grübel, R. (2003). On the multiplicity of the maximum in a
discrete random sample. Ann. Appl. Probab. 13 1252–1263. MR2023876
[3] Feller, W. (1971). An Introduction to Probability Theory and Its Applications II,
2nd ed. Wiley, New York. MR0270403
[4] Flajolet, Ph. (1985). Approximate counting: A detailed analysis. BIT 25 113–134.
MR0785808
[5] Grübel, R. and Reimers, A. (2001). On the number of iterations required by von
Neumann addition. Theor. Inform. Appl. 35 187–206. MR1862462
http://www.ams.org/mathscinet-getitem?mr=0233396
http://www.ams.org/mathscinet-getitem?mr=2023876
http://www.ams.org/mathscinet-getitem?mr=0270403
http://www.ams.org/mathscinet-getitem?mr=0785808
http://www.ams.org/mathscinet-getitem?mr=1862462
RENEWALS FOR INCREASING LIFETIMES 13
[6] Janson, S. (2004). Functional limit theorems for multitype branching processes and
generalized Pólya urns. Stochastic Process. Appl. 110 177–245. MR2040966
[7] Janson, S. (2006). Rounding of continuous random variables and oscillatory asymp-
totics. Ann. Probab. 34 1807–1826.
[8] Knuth, D. E. (1973). The Art of Computer Programming 3. Sorting and Searching.
Addison–Wesley, Reading, MA. MR0445948
[9] Louchard, G. (1987). Exact and asymptotic distributions in digital binary search
trees. Theor. Inform. Appl. 21 479–496. MR0928772
[10] Mahmoud, H. M. (1992). Evolution of Random Search Trees. Wiley, New York.
MR1140708
[11] Sedgewick, R. and Flajolet, Ph. (1996). An Introduction to the Analysis of Al-
gorithms. Addison–Wesley, Reading, MA.
Institut für Mathematische Stochastik
Universität Hannover
Postfach 60 09
D-30060 Hannover
Germany
E-mail: dennert@stochastik.uni-hannover.de
rgrubel@stochastik.uni-hannover.de
http://www.ams.org/mathscinet-getitem?mr=2040966
http://www.ams.org/mathscinet-getitem?mr=0445948
http://www.ams.org/mathscinet-getitem?mr=0928772
http://www.ams.org/mathscinet-getitem?mr=1140708
mailto:dennert@stochastik.uni-hannover.de
mailto:rgrubel@stochastik.uni-hannover.de
	Introduction
	Renewals for increasing lifetimes
	An application to digital search trees
	Rates of convergence
	References
	Author's addresses

  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.

Introduction. Let (Yk)k∈N be a sequence of independent, nonnegative
random variables and let (Sn)n∈N0 ,
S0 := 0, Sn :=
Yk for all n ∈N,
be the associated sequence of partial sums. Regarding the Yk’s as successive
lifetimes and Sn as the time of the nth renewal, we interpret
Nt := sup{n ∈N0 :Sn ≤ t}
as the number of renewals up to and including time t; (Nt)t≥0 is the renewal
process. Standard renewal theory assumes that the Yk’s all have the same
distribution, in which case Nt, appropriately rescaled, is asymptotically nor-
mal as t→∞. For this result, and for renewal theory in general, we refer
the reader to Section XI in [3].
In this note we consider exponentially increasing lifetimes. We show that
in such a case the distribution of Nt does not converge and that asymp-
totic distributional fluctuations appear (Section 2). Such fluctuations occur
frequently in the analysis of algorithms. The renewal theoretic framework
Received January 2006.
AMS 2000 subject classifications. Primary 60K05; secondary 68Q25.
Key words and phrases. Asymptotic distributional behavior, limiting periodicities, re-
newal processes.
This is an electronic reprint of the original article published by the
Institute of Mathematical Statistics in The Annals of Applied Probability,
2007, Vol. 17, No. 2, 676–687. This reprint differs from the original in pagination
and typographic detail.
http://arxiv.org/abs/0704.0398v1
http://www.imstat.org/aap/
http://dx.doi.org/10.1214/105051606000000862
http://www.imstat.org
http://www.ams.org/msc/
http://www.imstat.org
http://www.imstat.org/aap/
http://dx.doi.org/10.1214/105051606000000862
2 F. DENNERT AND R. GRÜBEL
provides a probabilistic view of this phenomenon in connection with digital
search trees (Section 3). We also indicate how our approach can be used to
obtain rates of convergence (Section 4).
2. Renewals for increasing lifetimes. We assume that the lifetimes in-
crease exponentially with rate α, where α> 1 is fixed throughout the sequel,
in the sense that
α−kYk →distr Y∞ and α−kEYk →EY∞(1)
for some random variable Y∞ and as k→∞. Here “→distr” denotes conver-
gence in distribution, so that the first part of (1) means that
Ef(α−kYk) =Ef(Y∞)
for all bounded continuous functions f :R→ R. Below we will use the fact
that in order to prove Xn →distr X it is sufficient to show that Ef(Xn)→
Ef(X) holds for all bounded and uniformly continuous functions. For details
and a general treatment of convergence in distribution we refer the reader
to [1]. Of course, only the distribution µ = L(Y∞) of Y∞ matters, so we
will occasionally write α−kYk →distr µ instead. Finally, throughout this note
a condition involving moments is meant to imply that these moments are
finite.
An important role will be played by
S∞ :=
α−kY∞,k,
where (Y∞,k)k∈N0 is a sequence of independent and identically distributed
random variables with L(Y∞,0) = L(Y∞), Y∞ as in (1). From EY∞ <∞ we
obtain ES∞ = α(α − 1)−1EY∞ <∞ and therefore P (S∞ <∞) = 1; more-
over, we then also have that
−kY∞,k converges almost surely and
hence in distribution to S∞ as n→∞. We will also assume that L(Y∞) has
no atoms, that is,
P (Y∞ = y) = 0 for all y ∈R+.(2)
Finally, it is an elementary analytic fact that, for a sequence (xn)n∈N of real
numbers with limit x ∈R,
α−kxn−k =
The following lemma can be regarded as a random version of (3).
Lemma 1. If (1) and (2) are satisfied, then α−nSn →distr S∞ as n→∞,
and P (S∞ = y) = 0 for all y ∈R.
RENEWALS FOR INCREASING LIFETIMES 3
Proof. Suppose that (Uk)k∈N is a sequence of independent random
variables on some probability space (Ω,A, P ), all uniformly distributed on
the unit interval. Let Fk be the distribution function of Yk, F the distribution
function of Y∞. We use a variant of the quantile construction:
Ỹk := F
k (Uk), Ỹ∞,k := F
−1(Uk) for all k ∈N.
We then have L(Ỹ1, . . . , Ỹn) = L(Y1, . . . , Yn) for all n ∈N, which implies
L(α−nSn) =L(α−nS̃n) with S̃n :=
Using α−nS̃n =
k=0 α
−k(α−(n−k)Ỹn−k) we obtain
α−nS̃n −
α−kỸ∞,n−k
α−kE|α−(n−k)Ỹn−k − Ỹ∞,n−k|.(4)
With Y ′k := F
k (U1) and Y
∞ := F
−1(U1) we have
E|α−kỸk − Ỹ∞,k|=E|α−kY ′k − Y ′∞|.(5)
From (1) it follows that α−kY ′k →distr Y ′∞ and Eα−kY ′k → EY ′∞. Because
of Y ′k, Y
∞ ≥ 0 Theorem 5.4 in [1] applies and gives the L1-convergence of
α−kY ′k to Y
∞, that is, E|α−kY ′k − Y ′∞| → 0 as k →∞. Using this together
with (3), (4) and (5) we obtain
α−nS̃n −
α−kỸ∞,n−k
= 0.(6)
Now let f :R→R be bounded and uniformly continuous. We have
|Ef(α−nSn)−Ef(S∞)|=
Ef(α−nS̃n)−Ef
α−kỸ∞,n−k
α−kỸ∞,k
α−kỸ∞,k
f(α−nS̃n)− f
α−kỸ∞,n−k
α−kỸ∞,k
α−kỸ∞,k
For the first integral on the right-hand side we use (6), for the second an
elementary estimate shows that the difference between the arguments of f
converges to 0 in probability. In both cases we now use uniform continuity
4 F. DENNERT AND R. GRÜBEL
when the arguments of f are close to each other and boundedness otherwise.
This leads to
Ef(α−nSn) =Ef(S∞),
which gives the convergence in distribution. The statement about the atoms
of S∞ follows from (2) and the fact that S∞ is equal in distribution to
Y∞ + α
−1S∞ with Y∞ and S∞ independent. �
The above proof is based on classical weak convergence arguments. An
alternative proof can be obtained via the Wasserstein distance
dW (µ, ν) = inf{E|X − Y | :L(X) = µ,L(Y ) = ν},
its known relation to weak convergence and convergence of the first moments,
and the same variant of the quantile construction, which in this context is
known as the comonotone coupling.
We write ⌊x⌋ for the greatest integer less than or equal to x and {x} for
the fractional part of x ∈R.
Theorem 2. Suppose that (1) and (2) are satisfied and let
Qη := L(⌊− logαS∞ + η⌋), 0≤ η ≤ 1.(7)
If (tn)n∈N is a sequence of real numbers with tn →∞ and such that {logα tn}→
η for some η ∈ [0,1], then
Ntn − ⌊logα tn⌋→distr Qη as n→∞.
Proof. We use the abbreviations kn := ⌊logα tn⌋ and ηn := {logα tn}. In
particular, logα tn = kn + ηn. Further, let Z∞ := − logαS∞. By a standard
renewal theoretic argument,
P (Nt = j) = P (Sj ≤ t)−P (Sj+1 ≤ t) for all t≥ 0, j ∈N0,
hence
P (Ntn − kn = j) = P (Skn+j ≤ tn)− P (Skn+j+1 ≤ tn)
= P (− logα(α−kn−jSkn+j) + ηn ≥ j)
−P (− logα(α−kn−j−1Skn+j+1) + ηn ≥ j + 1)
→ P (⌊Z∞ + η⌋= j) as n→∞,
where in the last step Lemma 1 and three general facts about convergence
in distribution were used: First, the continuous mapping theorem, which
implies that − logα(α−mSm)→distr − logαS∞ as m→∞; secondly, the in-
terplay with convergence in probability, see Theorem 4.1 in [1], which yields
RENEWALS FOR INCREASING LIFETIMES 5
− logα(α−nSn)+ ηn →distr − logαS∞+ η as n→∞; finally, that L(S∞) and
therefore also L(− logαS∞+η) assign probability 0 to single points and that
this implies
P (− logα(α−nSn) + ηn ≥ z) = P (− logαS∞ + η ≥ z) for all z ∈R.
A structural consequence of the representation (7) is the →distr-continuity
of η 7→Qη on the open unit interval; at η = 0 this function is right continuous,
at η = 1 it is left continuous. The extreme members are translates of each
other in the sense that Q0({j}) =Q1({j + 1}) for all j ∈ Z.
The total variation distance dTV of probability measures is defined by
dTV(µ, ν) := sup
|µ(B)− ν(B)|,
for µ, ν concentrated on Z this can be written as
dTV(µ, ν) =
|µ({j})− ν({j})|.(8)
For a sequence of probability measures that are concentrated on a fixed
countable set Scheffé’s lemma implies that weak convergence is equivalent
to convergence in total variation distance, hence (7) can be rewritten as
dTV(L(Ntn − ⌊logα tn⌋),Q{log
tn}) = 0.
Because of the continuity of [0,1] ∋ η 7→Qη this in turn leads to a statement
that avoids the use of subsequences,
dTV(L(Nt − ⌊logα t⌋),Q{log
t}) = 0.(9)
In Section 4 we will investigate the rate of convergence in (9) in a particular
case.
3. An application to digital search trees. The nodes of a (rooted, di-
rected) binary tree can be represented by finite strings of 0’s and 1’s if we
interpret 0 as a move to the left and 1 as a move to the right. The length of
the string is the depth (or level) of the node it represents, the root node corre-
sponds to the empty string and has level 0. The sequence (Tn)n∈N associated
with a sequence (xn)n∈N of numbers from the unit interval by the DST (dig-
ital search tree) algorithm is obtained as follows: For T1, we put x1 into the
root node. If x1, . . . , xn have been stored into Tn then the position of xn+1 is
determined by traveling through the tree with the direction given by the bi-
nary expansion of xn+1 until an empty node has been found. This algorithm
and its properties are discussed in the standard texts of the area, for exam-
ple, [8, 10, 11]. As an example we consider the first ten numbers given in [8],
6 F. DENNERT AND R. GRÜBEL
Fig. 1. Binary tree.
Appendix A, (
2, log 2, log 3, log 10). Let xi be the
fractional part of the ith entry, 1≤ i≤ 10; the relevant first four bits of the
respective binary expansions are given by (0110,1011,0011,0010, 0100,0111,
0011,1011,0001,0100). This leads to the binary tree given in Figure 1.
Consider now the sequence (Tn)n∈N0 of random trees that the DST algo-
rithm associates with a sequence (Un)n∈N of independent random variables,
where we assume that the Un’s are uniformly distributed on the unit inter-
val and that T0 is the empty tree. Let Xn(θ) be the depth of the first free
node of Tn along the path determined by a sequence θ ∈ {0,1}N. Such a θ
defines a family of nested intervals of length 2−k, k = 1,2,3, . . . , and it is
easy to see that (Xn(θ))n∈N0 is a Markov chain with X0(θ) ≡ 0 and tran-
sition probabilities pk,k+1 = 1− pk,k = 2−k for all k ∈ N0. Conditioning on
the value of Un+1 we see that the distribution of Xn(θ) is the same as the
distribution of Zn+1, the insertion depth of Un+1. This quantity is known
as “unsuccessful search” in the literature on the analysis of algorithms. [Of
course, this distributional equality does not hold for the joint distributions:
n 7→Xn(θ) is increasing, n 7→ Zn+1 is not.] For example, the next number
in Knuth’s list is x11 = 1/ log 2, the binary expansion of the fractional part
{x11} begins with 011100 and hence x11 would be inserted at level 4 as the
right child of x6.
The Markov chain (Xn(θ))n∈N0 is of the simple birth type and can there-
fore be described by its respective holding times Y1, Y2, Y3, . . . in the states
k = 0,1,2, . . . . These are independent, and Yk has a geometric distribution
with parameter pk−1,k, that is, for all k ∈N,
P (Yk = j) = (1− 2−k+1)j−12−k+1 for all j ∈N.
Here we interpret the case k = 1 as Y1, the holding time in 0, being constant
and equal to 1. As a result of its simple stochastic dynamics, (Xn(θ))n∈N0
is equal to the renewal process N associated with the sequence (Yk)k∈N,
observed at discrete times, that is, (Xn(θ))n∈N0 = (Nn)n∈N0 . It is easy to
see that for this sequence (Yk)k∈N of lifetimes conditions (1) and (2) are
satisfied and that L(Y∞) = Exp(2), with Exp(λ) the exponential distribution
RENEWALS FOR INCREASING LIFETIMES 7
with parameter λ (and mean 1/λ). Hence Theorem 2 can be applied: If the
sequence (n(m))m∈N ⊂ N is such that n(m) →∞ and {log2 n(m)} → η as
m→∞, then
Xn(m)(θ)− ⌊log2 n(m)⌋→distr Qη.(10)
Here Qη , 0≤ η ≤ 1, is the distribution of ⌊− log2 S∞+η⌋, S∞ :=
k=0 2
−kY∞,k
and Y∞,k, k ∈N0, are independent and identically distributed with L(Y∞,1) =
Exp(2). Alternatively, we can write S∞ :=
k=1 Ỹk with Ỹk, k ∈N, again in-
dependent and L(Ỹk) = Exp(2k) for all k ∈N.
The explicit representation of the family of limit distributions on the basis
of the convolution product of the distributions Exp(2k), k ∈N, can be used
to obtain a series expansion for the distribution functions associated with
Qη , 0 ≤ η ≤ 1. For this, we start with a partial fraction expansion: For all
n ∈N and all z ∈C with |ℜ(z)|< 2,
(1− 2−kz)−1 =
an,k(1− 2−kz)−1,(11)
where an,k :=
j=1(1− 2j)−1
j=1 (1− 2−j)−1. Reading (11) as an equality
relating characteristic functions we obtain
Exp(21) ⋆Exp(22) ⋆ · · · ⋆Exp(2n) =
an,kExp(2
k).(12)
Note, however, that the right-hand side in (12) is not the usual mixture of
probability distributions as the coefficients alternate in sign. With
ak := b
(1− 2j)−1, b :=
(1− 2−j)−1,
letting n→∞ in (12) leads to L(S∞) =
k=1 akExp(2
k), so that
Qη((−∞, x]) = P (⌊− log2(S∞) + η⌋ ≤ x)
= P (S∞ > 2
η−1−x)(13)
ak exp(−2k+η−1−x) for all x ∈ Z.
This representation of the limiting distribution functions as an alternating
series has already been obtained by Louchard [9] in the context of digital
search trees and by Flajolet [4] in the context of approximate counting; see
also Section 6.4 in [10] and Section 6.3 in [8] for related results. These authors
use a completely different approach, more analytic in flavor and relying on
combinatorial identities due to Euler.
8 F. DENNERT AND R. GRÜBEL
Our main point here, however, is not a rederivation of (13) but the rep-
resentation of the family {Qη : 0≤ η < 1} in terms of one particular random
variable, which is first shifted by η and then discretized. This representation
can, for example, be used to obtain information about the tail behavior of
the limit distributions. Janson [7] notes that (13) by itself would only give
an exponential rate of decrease for the tail probabilities, he then provides an
analytic argument that improves this to a superexponential rate by show-
ing that the associated Fourier transform is an entire function. Using the
representation S∞ =
k=1 2
−kZk with Zk independent and L(Zk) = Exp(1)
together with the fact that Exp(1) has a density bounded by 1, we get
P (S∞ ≤ 2−j)≤ P (Z1 ≤ 2−j+1)P (Z2 ≤ 2−j+2) · · ·P (Zj−1 ≤ 2−1)
≤ 2−j+12−j+2 · · ·2−1
= 2−j(j−1)/2
for all j ∈ N. Because of Qη([k,∞)) ≤ P (S∞ ≤ 2−k+1) for all k ∈ N, k ≥ 2,
this leads to
Qη([x,∞)) = o(exp(−ρx2)) as x→∞, for all ρ < (log 2)/2.
The fact that a representation by discretization is possible in many situ-
ations where fluctuations were first found by calculation seems to belong to
the folklore of the subject, at least in simple instances such as the asymp-
totic distributional behavior of the maximum of a sample from a geometric
distribution. The geometric case together with some renewal theoretic tech-
niques (for identically distributed lifetimes) was used in [5] to obtain results
of the above type for von Neumann addition. In [2] a discretization represen-
tation occurs on the level of stochastic processes, leading to a probabilistic
approach to fluctuation phenomena in the context of multiplicities of the
maximum in a random sample from a discrete distribution. In a recent pa-
per, Janson [7] studies the effects of discretizing random variables and the
resulting distributional fluctuations and gives a range of interesting exam-
ples. Of course, the explanation for periodicities can be, and indeed often is,
quite different and mechanisms other than discretization may be responsible;
see, for example, [6] and the references given there.
4. Rates of convergence. The renewal theoretic approach can also be
used to obtain rates of convergence. We sketch one of the possibilities, for
a particular choice of distances, and give details for the DST situation from
Section 3. Let, for t > 0, k(t) := ⌊logα t⌋ and η(t) := {logα t}.
The Kolmogorov–Smirnov distance of two probability measures µ and ν
on the real line is defined by
dKS(µ, ν) := sup
|µ((−∞, x])− ν((−∞, x])|.
RENEWALS FOR INCREASING LIFETIMES 9
If X and Y are real random variables, then we abbreviate dKS(L(X),L(Y ))
to dKS(X,Y ); if F and G are the associated distribution functions, then
dKS(X,Y ) = ‖F − G‖∞, where the supremum norm for general bounded
functions f :R → R is given by ‖f‖∞ := supx∈R |f(x)|. The Kolmogorov–
Smirnov distance is obviously invariant under strictly monotone transfor-
mations. For example,
dKS(αX + β,αY + β) = dKS(X,Y ) for all α,β ∈R, α 6= 0,
and for X,Y > 0,
dKS(X,Y ) = dKS(logX, logY ).
With the notation as in the proof of Theorem 2,
|P (Nt − k(t) = j)−P (⌊− logα(S∞) + η(t)⌋= j)|
≤ |P (− logα(α−k(t)−jSk(t)+j) + η(t)≥ j)−P (− logα(S∞) + η(t)≥ j)|
+ |P (− logα(α−k(t)−j−1Sk(t)+j+1) + η(t)≥ j +1)
− P (− logα(S∞) + η(t)≥ j + 1)|.
With the auxiliary quantities
Zt := ⌊− logα(S∞) + η(t)⌋, φ(m) := dKS(α−mSm, S∞)
and the above properties of the Kolmogorov–Smirnov distance this leads to
|P (Nt − k(t) = j)−P (Zt = j)| ≤ φ(k(t) + j) + φ(k(t) + j +1).(14)
It is often possible to obtain an upper bound for negative j, say j ≤−k(t)/2,
directly. In such cases the above elementary renewal theoretic argument leads
to a bound for the ‖ · ‖∞-distance between the probability mass functions of
Nt − k(t) and Zt, for example; note that the latter variable has distribution
Qη(t) where Qη , 0≤ η ≤ 1, is the set of limit distributions along subsequences
that appears in Theorem 2.
The above argument covers the step from (α−mSm)m∈N to (Nt)t≥0. How-
ever, in an application the starting point will usually be the convergence of
the scaled lifetimes in (1), which means that we also need an analogue for
Lemma 1 that gives rates of convergence.
We carry this out in the specific context of digital search trees. The fol-
lowing general bounds will turn out to be useful: If X has density fX and if
P (|Y | ≤ c) = 1, then
dKS(X,X + Y )≤ c‖fX‖∞.(15)
Indeed: For all z ∈R, P (X ≤ z− c)≤ P (X+Y ≤ z)≤ P (X ≤ z+ c), so that
|P (X + Y ≤ z)−P (X ≤ z)|
≤max{P (X ≤ z + c)−P (X ≤ z), P (X ≤ z)−P (X ≤ z − c)},
10 F. DENNERT AND R. GRÜBEL
and, of course, P (X ∈ (a, b]) ≤ (b − a)‖fX‖∞. This bound can easily be
generalized to
dKS(X,X + Y )≤ c‖fX‖∞ +P (|Y |> c) for all c > 0,(16)
where we still assume that X has density fX , but Y may be arbitrary.
Note that X and Y need not be independent in (15) and (16). If they are
independent then it is easy to show that
dKS(X,X + Y )≤ ‖fX‖∞E|Y |.(17)
In (17) boundedness of Y is not needed but the bound obviously makes sense
only if Y has finite first moment. Finally, in connection with density bounds
the interplay with convolution is of interest: We have ‖f ⋆ g‖∞ ≤ ‖f‖∞ for
all probability densities f, g. For example, if a sum of independent random
variables contains a summand with distribution Exp(λ), then the density of
the sum is bounded by λ.
Lemma 3. With (Yk)k∈N and S∞ as in Section 3,
dKS(2
−nSn, S∞) =O(n2
Proof. Let (Zk)k∈N be a sequence of independent random variables, all
exponentially distributed with parameter 1. Then S∞ is equal in distribution
k=1 2
−kZk. We recall that the kth lifetime Yk has a geometric distribu-
tion with parameter 2−k+1. On the basis of (Zk)k∈N we define a sequence
(Ỹk)k∈N by Ỹk := ⌊αkZk⌋+1 for all k ∈N, with
α1 := 0, αk := (− log(1− 2−k+1))−1 for k > 1.
It is easy to check that
(Ỹk)k∈N =distr (Yk)k∈N, 2
2k−1Zk =distr
2−kZk.
Hence, with φ(n) denoting the dKS-distance of 2
−nSn and S∞,
φ(n)≤ φ1(n) + φ2(n) + φ3(n) for all n ∈N,
with φ1, φ2, φ3 defined by
φ1(n) := dKS
Ỹk,2
φ2(n) := dKS
αkZk,2
2k−1Zk
φ3(n) := dKS
2−kZk,
2−kZk
RENEWALS FOR INCREASING LIFETIMES 11
For the random variables in φ1 we have
Vn ≤ 2−n
Ỹk ≤ Vn + n2−n with Vn := 2−n
αkZk.
It is easy to show that the densities of Vn, n ∈N, can be uniformly bounded
for all n by some finite constant C1, hence (15) implies that φ1(n)≤C1n2−n
for all n ∈N.
The elementary bounds
− 1≤−
log(1− x)
for 0< x≤
together with α1 = 0 imply supk∈N |αk − 2k−1|= 1, hence we have
αkZk − 2−n
2k−1Zk
≤ 2−n
The familiar combination of Markov’s inequality and moment generating
functions gives
Zk ≥ (1 + κ)n
=O(2−n)
if κ is chosen large enough, so that we can use (16) with c = c(n) = (1 +
κ)n2−n to obtain that φ2(n)≤C2n2−n for all n ∈N, for some finite constant
For φ3 finally we use (17): For the densities of the finite sums we again
have a finite uniform bound for all n, and
k=n+1
2−kZk
k=n+1
2−kEZk = 2
so that φ3(n) ≤ C32−n for all n ∈ N with some C3 <∞. Putting these to-
gether we arrive at
φ(n)≤Cn2−n for all n ∈N
with some finite constant C. �
In the application under consideration we obtain a rate of convergence
result with respect to the total variation distance, which is stronger than
a result for the supremum norm distance of the corresponding probability
mass functions that we mentioned in connection with (14).
Theorem 4. With (Xn(θ))n∈N and Qη as in Section 3,
dTV(L(Xn(θ)− ⌊log2 n⌋),Q{log2 n}) = o(n
−γ) for all γ < 1.
12 F. DENNERT AND R. GRÜBEL
Proof. We use the abbreviations k(n) := ⌊log2 n⌋ and η(n) := {log2 n}.
Let γ < 1 be given and choose ε > 0 such that ε < 1− γ. Lemma 3 together
with (14) gives
j≥−εk(n)
|P (Nn − k(n) = j)−Qη(n)({j})| ≤C
j≥(1−ε)k(n)
for all n ∈ N with some finite constant C. Our choice of ε implies that the
upper bound has the desired rate o(n−γ).
For the remaining part of the infinite sum in (8) we replace the absolute
difference of the probabilities by their sum, which means that it is now
enough to show that
P (Nn ≤ (1− ε)k(n)) = o(n−γ),(18)
P (− log2(S∞)≤−εk(n) + 1) = o(n−γ).(19)
Here we have used that Qη is the distribution of ⌊− log2(S∞)+ η⌋. It is easy
to show that the moment generating function for S∞ exists in a neighbor-
hood of 0, hence
P (S∞ > x) = o(e
−κx) for all x > 0(20)
with some κ > 0. Straightforward manipulations show that (20) implies (19);
indeed, the probability converges faster to 0 than any negative power of n.
Using once again the relation between the number of renewals and the partial
sums of the lifetimes we further obtain, with m(n, ε) := ⌊(1− ε)k(n)⌋,
P (Nn ≤ (1− ε)k(n)) ≤ P (Sm(n,ε) ≥ n)
= P (2−m(n,ε)Sm(n,ε) ≥ n2−m(n,ε))
≤ dKS(2−m(n,ε)Sm(n,ε), S∞) +P (S∞ ≥ n2−m(n,ε)).
For the Kolmogorov–Smirnov distance we use Lemma 3, for the tail of S∞
the desired rate follows with (20). This gives (18) and hence completes the
proof. �
REFERENCES
[1] Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York.
MR0233396
[2] Bruss, F. Th. and Grübel, R. (2003). On the multiplicity of the maximum in a
discrete random sample. Ann. Appl. Probab. 13 1252–1263. MR2023876
[3] Feller, W. (1971). An Introduction to Probability Theory and Its Applications II,
2nd ed. Wiley, New York. MR0270403
[4] Flajolet, Ph. (1985). Approximate counting: A detailed analysis. BIT 25 113–134.
MR0785808
[5] Grübel, R. and Reimers, A. (2001). On the number of iterations required by von
Neumann addition. Theor. Inform. Appl. 35 187–206. MR1862462
http://www.ams.org/mathscinet-getitem?mr=0233396
http://www.ams.org/mathscinet-getitem?mr=2023876
http://www.ams.org/mathscinet-getitem?mr=0270403
http://www.ams.org/mathscinet-getitem?mr=0785808
http://www.ams.org/mathscinet-getitem?mr=1862462
RENEWALS FOR INCREASING LIFETIMES 13
[6] Janson, S. (2004). Functional limit theorems for multitype branching processes and
generalized Pólya urns. Stochastic Process. Appl. 110 177–245. MR2040966
[7] Janson, S. (2006). Rounding of continuous random variables and oscillatory asymp-
totics. Ann. Probab. 34 1807–1826.
[8] Knuth, D. E. (1973). The Art of Computer Programming 3. Sorting and Searching.
Addison–Wesley, Reading, MA. MR0445948
[9] Louchard, G. (1987). Exact and asymptotic distributions in digital binary search
trees. Theor. Inform. Appl. 21 479–496. MR0928772
[10] Mahmoud, H. M. (1992). Evolution of Random Search Trees. Wiley, New York.
MR1140708
[11] Sedgewick, R. and Flajolet, Ph. (1996). An Introduction to the Analysis of Al-
gorithms. Addison–Wesley, Reading, MA.
Institut für Mathematische Stochastik
Universität Hannover
Postfach 60 09
D-30060 Hannover
Germany
E-mail: dennert@stochastik.uni-hannover.de
rgrubel@stochastik.uni-hannover.de
http://www.ams.org/mathscinet-getitem?mr=2040966
http://www.ams.org/mathscinet-getitem?mr=0445948
http://www.ams.org/mathscinet-getitem?mr=0928772
http://www.ams.org/mathscinet-getitem?mr=1140708
mailto:dennert@stochastik.uni-hannover.de
mailto:rgrubel@stochastik.uni-hannover.de
	Introduction
	Renewals for increasing lifetimes
	An application to digital search trees
	Rates of convergence
	References
	Author's addresses
