Central limit theorems for the monkey walk with steep memory kernel
Erion-Stelios Boci Cécile Mailler






Central limit theorems for the monkey walk
 with steep memory kernel
    Erion-Stelios BociDepartment of Mathematical Sciences, University of Bath, Claverton Down, BA2 7AY Bath, UK.Email: e.boci/c.mailler@bath.ac.uk Cécile Mailler^*
    September 9, 2024
===================================================================================================================================================================



§ ABSTRACT 
The monkey walk is a stochastic process defined as the trajectory of a walker that moves on ℝ^d according to a Markovian generator, 
except at some random “relocation” times at which it jumps back to its position at a time sampled randomly in its past, according to some “memory kernel”.
The relocations make the process non-Markovian and introduce a reinforcement effect (the walker is more likely to relocate in a Borel set in which it has spent a lot of time in the past).
In this paper, we focus on “steep” memory kernels: in these cases, the time sampled in the past at each relocation time is likely to be quite recent. 
One can see this as a way to model the case when the walker quickly “forgets” its past.
We prove limit theorems for the position of the walker at large times, which confirm and generalise the estimates available in the physics literature.




§ INTRODUCTION

The “monkey walk” is a non-Markovian stochastic process that 
was first defined in the physics literature as a model for animal (monkeys, in particular) 
foraging behaviour. 
The original model of Boyer and Solis-Salas <cit.> is a random walk on ℤ^d 
that evolves like the simple symmetric random walk except at some random “relocation” 
times at which it jumps to a site it has already visited in the past, 
chosen with probability proportional to the number of past visits at that site. 
Equivalently, at relocation times, 
the walker chooses a time uniformly 
at random in its past and jumps to the site it visited at that random time.
We call the intervals between relocation times the “run-lengths”.
In the original model of <cit.>, the run-lengths are i.i.d. random variables, 
geometrically distributed with some parameter q>0.
Boyer and Solis-Salas <cit.> proved a central limit theorem 
for the position of the walker at large time; 
they showed in particular that the variance of this position 
is or order (log t)^d at large time t.
The monkey walk thus diffuses much slower than the simple symmetric random walk, 
which diffuses at speed t^d.
This is because the random relocations, which make sites that have been visited often in the past more likely to be visited again in the future, introduce a reinforcement (rich-gets-richer) effect.

Boyer, Evans and Majumdar <cit.> later 
generalised this model by adding memory, i.e. making the walker more likely to relocate 
to sites it visited more recently.
Indeed, in their model, at relocation times, the walker chooses a time in its past according to some possibly non-uniform probability distribution, 
and then jumps to the site where it was at that random time.
More precisely, the idea is that, if a relocation happens at time t>0, then
the random time chosen by the walker in its past has density μ(x)dx/(∫_0^t μ), where μ : [0,∞) → [0,∞) is a non-negative function called the memory kernel. 
(We ask that μ satisfies ∫_0^t μ>0 for all t>0.)
Boyer, Evans and Majumdar <cit.> 
showed a central limit theorem for the position of the walker at large times, 
for a large class of possible memory “kernels”.

Mailler and Uribe-Bravo <cit.> later generalised the model even further by allowing the underlying motion (the walk between relocation times) to be any Markov process (instead of the simple symmetric random walk), possibly in continuous time, and the run-lengths to be a sequence of i.i.d. random variables of any distribution (instead of the geometric distribution).
They also allowed the memory to be non-uniform as in <cit.> and proved that, for a large class of memory kernels, “if the underlying Markov process satisfies some central limit theorem, and if the run-lengths distribution have moments of high-enough order, then the associated monkey walk also satisfies a central limit theorem”.

For technical reasons, the results of <cit.>
only hold for relatively “flat” memory kernels, i.e. only if the walker 
does not forget its past too fast.
More precisely, they consider two classes of memory kernels: 

    μ_1(x) = α/x (log x)^α-1e^β (log x)^α,    (α>0, β≥ 0),

and

    μ_2(x) = γδ x^δ-1e^γ x^δ,   (γ>0, δ∈ [0,1/2]).

The aim of this paper is to prove limit theorems for steeper memory kernels, i.e. for μ = μ_2 with δ>1/2. We are able to prove precise asymptotic results for the position of the walker at large times, which, in particular, confirm the predictions of <cit.> (made in the case when the underlying Markov process is the standard Brownian motion).
In <cit.>, the proofs rely on the analysis of the “genealogical tree of the runs”. 
When the memory kernel is flat enough, this tree is close enough to a random recursive tree. 
When the memory kernel becomes steeper, the tree becomes less and less “fat”; 
in particular, as mentioned in <cit.>, 
the fact that the last common ancestor of two nodes taken uniformly, 
independently at random in the tree has constant-order height is no longer true, 
we believe, when δ≥1/2.
Because of this, we are not able to prove convergence of the occupation measure for steep memory kernels, while this could be done in <cit.> for flatter memory kernels.


The literature on the “monkey walk” extends much beyond the works of Boyer and Solis-Salas <cit.>, Boyer, Evans and Majumdar <cit.>, and Mailler and Uribe Bravo <cit.>, which we have discussed so far. 
Indeed, Boyer and Pineda <cit.> proved limiting theorems for the position of the walker at large times in the case when the underlying Markov process is a random walk with heavy-tailed increments (a case which falls under the more general, more recent framework of <cit.>).
Large deviations for the position of the walker at large times were established in the work of Boci and Mailler <cit.>.
In <cit.>, Boyer, Falcón-Cortés, Giuggioli and Majumdar exhibit an interesting localisation phenomenon when the probability to relocate is larger at the origin than at the other sites of ℤ^d.
Recently, Boyer and Majumdar <cit.> have introduced a continuous-time variant of the model in which, between relocations, the particle moves at constant speed on a one-dimensional line with a telegraphic noise (i.e. the sign of the particle's speed changes at constant rate). They get explicit formulas for the distribution of the position of the particle at all times and show large deviation results.

The case when the walker resets to a fixed position (eg. the origin) at relocation times has also been studied in the literature (see, e.g. <cit.> for a literature review on the subject), but, unsurprisingly, it leads to a drastically different behaviour.







 §.§ Mathematical definition of the model and notation
 
The monkey walk X = (X_t)_t≥ 0 is a stochastic process on ℝ^d whose distribution depends on three parameters: 


  * a semi-group P = (P_t)_t≥ 0 on ℝ^d (the distribution of the underlying Markov process);

  * a probability distribution ϕ on [0,∞) (the run-length distribution);

  * a function μ : [0,∞) → [0,∞) such that ∫_0^t μ >0 for all t>0.

The process X is defined as follows (see Figure <ref>): 
first sample (L_n)_n≥ 1 a sequence of i.i.d. random variables of distribution ϕ and let T_n = ∑_i=1^n L_i for all n≥ 0. 
Then, let (X(s))_0≤ s<T_1 be the Markov process of semi-group P started at the origin.
Then, for all n≥ 1, given (X(s))_0≤ s<T_n,


  * let R_n be a random variable on [0, T_n) whose distribution has density μ/(∫_0^T_nμ) on [0,T_n),

  * let (X(s))_T_n≤ s<T_n+1 be the Markov process of semi-group P started at X(R_n).

For all n≥ 1, we call L_n the “length of the n-th run” and T_n the “n-th relocation time”. 



In this paper, we assume that

    μ(x) = γδ x^δ-1e^γ x^δ

for some γ>0 and δ>1/2.


 
Note that this framework also includes the case of a discrete-time underlying process. Indeed, in that case, we make the underlying process defined on [0,∞) by making it constant on each interval [n, n+1), n≥ 0, and we round the relocation times to the integer above.




 §.§ Statement of the results

Our main result holds under the following assumptions on the underlying Markov process of semi-group P:


  (A1) There exist two functions a : [0,∞) →ℝ^d and b : [0,∞) → (0,∞), and a probability distribution ν on ℝ^d such that, for all z∈ℝ^d, if Z = (Z(t))_t≥ 0 is the Markov process of semi-group P started at z, then

    Z(t)-a(t)/b(t)⇒ν,

in distribution as t↑∞.
(We say that Z is (a, b)-ergodic, following the terminology used in <cit.>, and before that in <cit.>.)

  (A2) For all x∈ and for all functions ε : [0,∞)→ℝ satisfying ε(t) = o(√(t)) as t↑∞, the following limits exist and are finite: 
    f(x)=lim_t→∞a(t+x√(t)+ε(t))-a(t)/b(t)  and   
    g(x)=lim_t→∞b(t+x√(t)+ε(t))/b(t).


  (A2_δ) 
For all functions ε : [0,∞)→ℝ satisfying, as t↑∞, 

    ε(t) = 
    
    o(t^3/2-δ)     if δ∈ (1, 3/2)
    𝒪(1)     if δ>3/2,
 we have

    0=lim_t→∞a(t+ε(t))-a(t)/b(t)  and   
    1=lim_t→∞b(t+ε(t))/b(t).




The results of <cit.> hold under Assumptions (A1-2); 
recall that they cover the case of δ∈(0,1/2].
For δ∈ (1/2, 1], we use the same assumptions.
However, for δ>1, i.e. for the steepest memory kernels, 
we need to replace Assumption (A2) by (A2_δ).


To state our main result, we introduce the following notation:
For all t≥ 0, we set

    s(t)
    = γδ t^δ/𝔼 [L]∑_k=0^⌊δ/2 - 2δ⌋(-γδ)^k𝔼[L^k+2]/(k+2)!(δ-(1-δ)k)· t^k(δ -1)    if δ∈(0, 1),
    (𝔼[L] - 1-𝔼[e^-γ L]/γ) t     if δ = 1,
     t-t^2-δ/γδ (2-δ)    if δ∈ (1, 2],
    
    t     if δ>2.

Roughly speaking, our main result says that, in distribution, X(t)≈ Z(s(t)), 
where Z is the Markov process of semi-group P started at the origin.
One can see that, as δ increases, and thus as the memory kernel becomes steeper and steeper, s(t) becomes larger and larger.


We comment on the formula for s(t) when δ∈(1/2, 1).
For δ∈ (1/2, 2/3), the sum has only one summand. Indeed, 0≤δ/(2δ -2)< 1 if and only if δ∈ (1/2, 2/3). In that case,

    s(t) = γ𝔼[L^2] /2𝔼 [L]· t^δ.

Similarly, if δ∈ [2/3, 3/4), the sum has two summands, and

    s(t) =  γ𝔼[L^2] /2𝔼 [L]· t^δ -
    (γδ)^2 𝔼[L^3]/6(2δ -1)𝔼 [L]· t^2δ -1.

More generally, for all integers i≥ 1, for all δ∈ [i/i+1, i+1/i+2),
the sum has i summands, each of them of the form “constant times a power of t”, where the power of t deacreases with the index k of the sum.
Note in particular that, for all δ∈ (1/2, 1), as t↑∞,

    s(t)∼γ𝔼[L^2] /2𝔼 [L]· t^δ.




The following three theorems are our main results:
 
Let X=(X(t))_t≥ 0 be the monkey process of semigroup P, 
run-length distribution ϕ and memory kernel 
μ(x)=γδ x^δ -1e^γ x^δ, 
where γ>0 and δ∈ (0,1).
Let L be a random variable of distribution ϕ.
We assume that (A1-2) hold and assume that 𝔼[L^p]<∞, where

    p=max{8, ⌊1/1-δ⌋ +1}.

Then, 


in distribution as t↑∞,

    X(t)-a(s(t))/b(s(t))⇒ f(Ω) + Λ g(Ω),

where (s(t))_t≥ 0 is defined as in (<ref>),
and where Ω∼𝒩(0, 2𝔼[L^3]/(3𝔼[L^2])) and Λ∼ν are two independent random variables.




































 
We have included the case δ∈ (0, 1/2] in Theorem <ref>.
This case is proved in <cit.>. In this paper, we only prove Theorem <ref> in the case δ∈(1/2, 1).
Although the general idea of the proof is the same as in <cit.>, the proof is more technical because the expansion of s(t) up to order t^δ/2 (which is the accuracy we need) has more and more terms as δ↑1.



 
Let X=(X(t))_t≥ 0 be the monkey process of semigroup P, 
run-length distribution ϕ and memory kernel 
μ(x)=γe^γ x, 
where γ>0.
Let L be a random variable of distribution ϕ.
We assume that (A1-2) hold and assume that 𝔼[L^4]<∞.
Then, in distribution when t↑∞,

    X(t)-a(s(t))/b(s(t))⇒ f(Ω) + Λ g(Ω),

where s(t) is defined as in (<ref>),
Λ∼ν and Ω are independent, 
and Ω = Ω_1 + Ω_2 + Ω_3 is the sum of three dependent Gaussian random variables whose variances and covariances are as follow:

    Var(Ω_1) 
    = 1/γ^2+𝔼[L^2-(L+e^-γ L/γ)^2],
      Var(Ω_2) 
    = Var(L- 1-e^-γ L/γ)
    = Var(L + e^-γ L/γ),


    Var(Ω_3) 
    = Var(L)𝔼[L-(1-e^-γ L)/γ]^2/𝔼[L^2],


    Cov(Ω_1, Ω_2) 
    = Var(L-1-e^-γ L/γ),
    Cov(Ω_1, Ω_3) 
    = Cov(Ω_2, Ω_3)
    = Cov(L, L+e^-γ L)𝔼[L-(1-e^-γ L)/γ]/γ𝔼[L].



 
Let X=(X(t))_t≥ 0 be the monkey process of semigroup P, 
run-length distribution ϕ and memory kernel 
μ(x)=γδ x^δ-1e^γ x^δ, 
where γ>0 and δ>1.
Let L be a random variable of distribution ϕ.
We assume that (A1) and (A2_δ) hold and assume that 𝔼[L^4]<∞.
Then, 


in distribution as t↑∞,

    X(t)-a(s(t))/b(s(t))⇒ν.




We summarise here our moment conditions on the run-length distribution, for increasing values of δ:


  * for δ<7/8, we ask that 𝔼[L^8]<∞;

  * for δ∈ [7/8, 8/9) we ask that 𝔼[L^9]<∞; etc

  * for δ≥ 1, we ask that 𝔼[L^4]<∞.

Interestingly, one can note that we ask for more and more control on the upper tail of the run-length distribution as δ↑1. We believe that this is a caveat of the expansion in the expression for s(t); if the run-lengths had heavier tails, a limiting result would hold, but there would be no “nice” formula for s(t).






 §.§ One example

Before discussing our main result further, we apply it to a simple example:
let ϕ be the standard exponential distribution and P be the semi-group of the one dimensional Brownian motion with constant drift equal to 1.
We first check Assumptions (A1-2) and (A2_δ):
If Z is the one dimensional Brownian motion with constant drift equal to 1, 
then, in distribution as t↑∞,

    Z(t)-t/√(t)⇒𝒩(0,1).

In other words, Assumption (A1) holds with a : t ↦ t, b : t↦√(t), and ν = 𝒩(0,1).
Also, for all x∈ℝ and t≥ 0,

    a(t+ x√(t) + ε(t))- a(t)/b(t)
    = x√(t) + ε(t)/√(t)→ x,

as t↑∞, as long as ε(t) = o(√(t)).
Similarly,

    b(t+ x√(t) + ε(t))/b(t) = √(t+x√(t) + ε(t)/t)→ 1.

Thus, Assumption (A2) holds with f(x) = x and g(x) = 1, for all x∈ℝ.
Finally, if ε(t) = o(√(t)), then

    a(t+ε(t))-a(t)/b(t) = ε(t)/√(t)→ 0,

and

    b(t+ε(t))/b(t) = √(t+ε(t)/t)→ 1,

as t↑∞, which implies that Assumption (A2_δ) also holds in this case.

Also note that, if L is a standard exponential random variable, 
then 𝔼 L^k = k! <∞ for all k≥ 1.
Thus the assumptions of Theorems <ref>, <ref> and <ref> hold for all δ∈ (0, ∞).
We now look at the conclusions of these theorems for different values of δ.
For all of these, one can check that the diffusive speed of the monkey walk coincides with the variance estimates of <cit.> (made for the same model: runs of Brownian motion and exponential run-lengths – the only difference is that they consider the case with no drift, but this does not affect the variance estimates).

∙ Assume that δ∈ (0, 2/3).
In that case (see Remark <ref>),

    s(t) = γ𝔼[L^2] /2𝔼 [L]· t^δ
     =γ t^δ.

Thus, by Theorem <ref>,

    X(t) - γ t^δ/√(γ) t^δ/2⇒Ω + Λ,

where Ω∼𝒩(0, 2) (because 2𝔼[L^3]/3𝔼[L^2] = 2) and Λ∼𝒩(0, 1).
Because Ω and Λ are independent, we get

    X(t) - γ t^δ/√(γ) t^δ/2⇒𝒩(0, 3),   or equivalently,   X(t) - γ t^δ/t^δ/2⇒𝒩(0, 3γ).


∙ Assume that δ∈ (2/3, 3/4).
The only difference with the previous case is in the definition of s(t):
as discussed in Remark <ref>, in this case,

    s(t) = γ𝔼[L^2] /2𝔼 [L]· t^δ -
    (γδ)^2 𝔼[L^3]/6(2δ -1)𝔼 [L]· t^2δ -1
    = γ t^δ + (γδ)^2/2δ -1 · t^2δ -1.

Theorem <ref> thus gives

    X(t) - γ t^δ - (γδ)^2/2δ -1· t^2δ -1/t^δ/2⇒𝒩(0,3γ).

It is important to note that one cannot neglect the second order term of s(t) in the numerator above because t^2δ -1≫ t^δ/2. Indeed, 2δ -1>δ/2 as soon as δ>2/3.
This is the reason why, in the definition of s(t) for δ<1, 
we need to keep more and more terms in the sum as δ increases.

∙ Assume that δ = 1.
In that case, Theorem <ref> applies. We have

    s(t) = (𝔼[L]-1-𝔼[e^-γ L]/γ)t
    = γ/γ+1· t.

Thus,

    X(t) - γ t/(γ+1)/√(γ t/(γ+1))⇒Ω + Γ,

where Γ∼𝒩(0,1) and Ω = Ω_1+Ω_2+Ω_3 are independent, with Ω_1, Ω_2, and Ω_3 three Gaussian whose variances and covariances are given by

    Var(Ω_1) = (γ-1)^2/2γ^2(γ+1)^2,
      Var(Ω_2) = γ^2(2γ+5)/(γ+1)^2(2γ+1),
      Var(Ω_3)  = γ/γ+1,


    Cov(Ω_1, Ω_2) = γ^2(2γ+5)/(γ+1)^2(2γ+1),   and   Cov(Ω_1, Ω_3)=Cov(Ω_2, Ω_3)
    = γ^2+2γ+2/(γ+1)^3.


∙ Assume that δ>1.
In that case, Theorem <ref> applies and gives that, if δ∈ (1, 3/2], then

    X(t)-t+t^2-δ/(γδ(2-δ))/√(t)⇒𝒩(0,1),

and if δ>3/2,

    X(t)-t/√(t)⇒𝒩(0,1).

In the case when δ>3/2, the memory kernel is so steep that the monkey walk satisfies the same central limit theorem as the standard Brownian motion (with no relocations).




 §.§ Plan of the paper

After some preliminary results in Section <ref>, we prove Theorems <ref>, 
<ref> and <ref> in Sections <ref>, <ref> and <ref>, respectively. 





§ PRELIMINARIES TO THE PROOFS

As in <cit.>, our proofs rely on the fact that, for all t≥ 0, in distribution, 
X(t) = Z(S(t)), where Z is the Markov process of semi-group P started at the origin, 
and S(t) is a random variable, independent of Z.
The idea is that, as t↑∞, S(t)∼ s(t) in probability (where s(t) is as defined in (<ref>)).

To define S(t), one need to introduce the following notation: 
for all 1≤ i< j, we say that the i-th run is the parent of the j-th run if R(j)∈ [T_i-1, T_i).
This implies a genealogy on runs, and we let i≺ j denote the event that the i-th run is an ancestor of the j-th run in this genealogical tree.
For any t, we let i(t) be the integer such that X(t)∈ [T_i(t)-1, T_i(t)), 
meaning that X(t) belongs to the i(t)-th run of the process.
We also let A(t)= t-T_i(t)-1.
Finally, we set

    S(t) = A(t) + ∑_i=1^i(t)-1 F_i  1_i≺ i(t),

where, given the run-lengths (L_i)_i≥ 1, 
(F_i)_i≥ 1 is a sequence of independent random variables such that, for all i≥ 1,

    ℙ_ L(F_i≤ x) = ∫_0^x μ(T_i-1+u) du/∫_0^L_iμ(T_i-1+u) du,

where we let ℙ_ L denote ℙ( · |(L_i)_i≥ 1).
Note that, for all i≥ 1, T_i-1 + F_i is distributed as R(n) conditioned to belong to the i-th run. Interestingly, and this is crucial in our proofs, the distribution of R(n) conditionally on R(n)∈ [T_i-1, T_i) is the same for all n≥ 1.

With these definitions, we have

For all t≥ 0, in distribution,

    X(t) = Z(S(t)),

where Z is the Markov process of semi-group P started at the origin, and S(t) is defined as in (<ref>).


The intuition behind this lemma is given in Figure <ref>: the idea is that, by the Markov property of the underlying process, X(t) can be seen at the end-point of the bold purple trajectory, which is distributed as Z run for the amount of time S(t).



The plan of the proof of Theorems <ref>, <ref>, and <ref> all follow the same plan:


  * We first prove a limiting theorem for

    Φ(n):=∑_i=1^n F_i  1_i≺ n,    as n↑∞.


  * We use renewal theory to get that i(t) ≈ t/𝔼[L] and A(t) = o(u(t)) in probability for any u(t)↑∞ as t↑∞. This gives a limiting theorem for S(t).

  * We then compose the limiting theorem for S(t) with the limiting theorem for Z(t) given by Assumption (A1).

In Sections <ref>, <ref>, and <ref>, we prove Theorems <ref>, <ref>, and <ref>, respectively.
We now state a few preliminary results that will be useful in all three proofs: Lemma <ref> will be useful for Step 1., while Lemmas <ref> and <ref> will be useful in Step 2.


Conditionally on L = (L_i)_i≥ 1, ( 1_i≺ n)_1≤ i≤ n-1 is a sequence of independent Bernoulli-distributed random variables of respective parameters W_i/W̅_i,
where, for all i≥ 1,

    W_i = ∫_T_i-1^T_iμ   and   W̅_i = ∑_j=1^i W_j = ∫_0^T_iμ.



The proof of Lemma <ref>, and the intuition behind all the results in <cit.>,
is based on the fact that the genealogical tree of the runs as defined by the relationship ≺ is a “weighted (random) recursive tree” with random weights (W_i)_i≥ 1.
For more literature on weighted recursive trees, we refer the reader to, e.g., <cit.>.


In probability as t↑∞, A(t) = 𝒪(1) (i.e., for all ε>0, there exists M = M(ε) and t(ε) such that, for all t≥ t(ε), ℙ(|A(t)|≥ M)≤ε).
In particular, for any u : [0,∞)→ℝ such that u(t)↑∞ as t↑∞, A(t)/u(t) → 0 in probability as t↑∞.



This is a straightforward consequence of the fact that, by renewal theory, T_i(t)+1-T_i(t) converges in distribution to an almost surely finite random variable (see, e.g. <cit.>). The result follows, because 0≤ A(t)≤ T_i(t)+1-T_i(t) almost surely for all t≥ 0.



Almost surely as t↑∞, i(t) = t/𝔼L + 𝒪(√(tlog t)).



This is a straightforward consequence of the law of the iterated logarithm. 
First note that i(t)↑∞ almost surely as t↑∞.
Indeed, it is almost surely non-decreasing, and thus either i(t)↑∞, or i(t)↑ i(∞)<∞. In the latter case, we would get that, for all t≥ 0, t≤∑_i=1^i(∞) L_i, which is impossible. Thus, i(t)↑∞ almost surely as claimed.
Because, by assumption, 𝔼L<∞, the strong law of large numbers gives i(t)∼ t/𝔼L, almost surely as t↑∞.
Now, by assumption, Var(L)<∞, thus,

    -∞<lim inf_n↑∞∑_i=1^n L_i - n𝔼L/√(nlog n)≤lim sup_n↑∞∑_i=1^n L_i - n𝔼L/√(nlog n)<∞,

which implies

    -∞<lim inf_t↑∞∑_i=1^i(t) L_i - i(t)𝔼L/√(i(t)log i(t))≤lim sup_t↑∞∑_i=1^i(t) L_i - i(t)𝔼L/√(i(t)log i(t))<∞.

Because i(t)∼  t/𝔼L almost surely, we get

    -∞<lim inf_t↑∞∑_i=1^i(t) L_i - i(t)𝔼L/√(tlog t)≤lim sup_t↑∞∑_i=1^i(t) L_i - i(t)𝔼L/√(tlog t)<∞.

By definition,

    ∑_i=1^i(t)-1 L_i - i(t)𝔼L/√(tlog t)≤t - i(t)𝔼L/√(tlog t)
    < ∑_i=1^i(t) L_i - i(t)𝔼L/√(tlog t).

Taking limits, we thus get that, almost surely,

    -∞< lim inf_t↑∞t - i(t)𝔼L/√(tlog t)≤lim sup_t↑∞t - i(t)𝔼L/√(tlog t)<∞,

which concludes the proof.




§ PROOF OF THEOREM <REF>

In this section, we assume that δ<1.
As discussed in Section <ref>, we start by proving a limit theorem for Φ(n) = ∑_i=1^n F_i  1_i≺ n:
 
Assume that δ∈ (1/2, 1) and that the assumptions of Theorem <ref> hold.
We let L = (L_i)_i≥ 1 and F = (F_i)_i≥ 1 (as defined in (<ref>)).
Conditionally on (L,F), (L,F)-almost surely, 

    Φ(n)-σ(n)/√(γ n^δ)⇒𝒩(0,𝔼[L^3]/3𝔼[L]^1-δ),
  in distribution as n→∞, where  

    σ(n) = γδ n^δ∑_k=0^⌊δ/2 - 2δ⌋(-γδ)^k 𝔼[L^k+2]/(k+2)!(δ - k(1-δ))
    𝔼[L]^(1-δ)(k+1)·  n^-k(1-δ).




Before proving Proposition <ref> we show how to use it to prove Theorem <ref>:

We first aim at proving a limit theorem for S(t).
Recall that, by definition (see (<ref>)),

    S(t) = Φ(i(t)-1) + A(t).

By Lemma <ref>, i(t)↑∞ almost surely as t→∞. 
Thus, Proposition <ref> implies that, in distribution as t↑∞,

    Φ(i(t)-1)-σ(i(t)-1)/√(γ i(t)^δ)⇒𝒩(0,𝔼[L^3]/3𝔼[L]^1-δ).

Now, by Lemma <ref>, i(t)= t/𝔼L + 𝒪(√(tlog t)), almost surely as t↑∞. Thus,

    σ(i(t)-1) =  γδ∑_k=0^⌊δ/2 - 2δ⌋(-γδ)^k 𝔼[L^k+2]/(k+2)!(δ - k(1-δ))
    𝔼[L]^(1-δ)(k+1)·  i(t)^-k(1-δ)+δ,

For all 0≤ k≤⌊δ/2 - 2δ⌋,
i(t)^-k(1-δ)+δ 
   = (t/𝔼L + 𝒪(√(tlogt)))^-k(1-δ)+δ
= (t/𝔼L)^-k(1-δ)+δ ( 1+ 𝒪(√(logt/t)))

   = (t/𝔼L)^-k(1-δ)+δ + 𝒪(t^-k(1-δ)+δ-1/2√(logt))
= (t/𝔼L)^-k(1-δ)+δ  + o(t^δ/2),
where, in the last equality, we have used the fact that, for all k≥ 0, 
-k(1-δ)+δ-1/2≤δ-1/2<δ/2.
Using this in (<ref>) gives

    σ(i(t)-1)  = γδ∑_k=0^⌊δ/2 - 2δ⌋(-γδ)^k 𝔼[L^k+2]/(k+2)!(δ - k(1-δ))
    𝔼[L]· t^-k(1-δ)+δ + o(t^δ/2)
    = s(t) + o(t^δ/2),

by definition of s(t) is this case (see (<ref>) for δ <1).
Using this and the fact that i(t)∼ t/𝔼L in (<ref>), we get

    Φ(i(t))-s(t) + o(t^δ/2)/√(γ (t/𝔼L)^δ)⇒𝒩(0,𝔼[L^3]/3𝔼[L]^1-δ),

which implies

    Φ(i(t)-1)-s(t)/t^δ/2⇒𝒩(0,γ𝔼[L^3]/3𝔼[L]).

Recall that S(t) = Φ(i(t)-1) + A(t) (see (<ref>));
using the fact that, by Lemma <ref>, A(t)/t^δ/2→ 0 in probability, we get that, in distribution as t↑∞.

    S(t)-s(t)/t^δ/2⇒𝒩(0,γ𝔼[L^3]/3𝔼[L]).


By Skorokhod's representation theorem, 
there exists a probability space on which there exist S̃(t) distributed as S(t) for all t≥ 0, and Ω̂∼𝒩(0,𝔼[L^3]/(3𝔼[L])), 
such that almost surely when t→∞,
S̃(t) 
    = s(t) + Ω̂√(γt^ δ) + o(t^δ/2) 

    = s(t)+ Ω̂√( 2 𝔼[L] / 𝔼[L^2]  s(t) ) 
+ Ω̂(√(γt^δ) - √( 2 𝔼[L] / 𝔼[L^2]  s(t) )) + o(t^δ/2) 

    = s(t) + Ω̂√( 2 𝔼[L] / 𝔼[L^2] s(t)) + o(√(s(t))).
Indeed, we have used the fact that, as t↑∞, 
s(t)∼γ𝔼[L^2]t^δ/(2𝔼 [L]) (see Remark <ref>).
By Assumption (A1), on the same probability space, 
there exists (Z̃(t))_t≥ 0 independent of (S̃(t))_t≥ 0 and a random variable Λ, independent of Ω̂ such that
Z̃(t) has the same distribution as Z(t) for all t≥ 0, Λ has distribution ν, and Z̃(t)-a(t)/b(t)→Λ almost surely as t↑∞. 
Therefore, by assumption (A2), almost surely as t→∞, 
Z̃(S̃(t))-a(s(t))/b(s(t)) 
    = b(S(t))/b(s(t)) ·Z̃(S̃(t))-a(S̃(t))/b(S̃(t)) 
+a(S̃(t))-a(s(t))/b(s(t)) 

   →f(Ω)+ Λg(Ω),
where Ω = Ω̂√(2𝔼[L]/𝔼[L^2])∼𝒩(0, 2𝔼[L^3]/(3𝔼[L^2])).
Because Z̃(S̃(t)) = Z(S(t)) = X(t) in distribution for all t≥ 0 (by Lemma <ref>), 
this concludes the proof.




The rest of the section is devoted to proving Proposition <ref>. 
The idea of the proof is as follows: we first reason conditionally on L and F and 
apply Linderberg's central limit theorem to prove that

    Φ(n)-𝔼_ L,  F[Φ(n)]/√(Var_ L,  F(Φ(n)))⇒(0,1)

in distribution as n↑∞.
This is done in Section <ref>.
To prove Proposition <ref>, we thus need to find asymptotic equivalents 
for 𝔼_ L,  F[Φ(n)] and Var_ L,  F(Φ(n)).
To do so, we apply Lemma <ref> to get that

    𝔼_ L,  F[Φ(n)]
    =∑_i=1^nF_iW_i/W̅_i  and  Var_ L,  F(Φ(n))
    =∑_i=1^nF_iW_i/W̅_i(1-W_i/W̅_i).
 
In Lemma <ref>, 
we prove that, conditionally on L, 
we can almost surely approximate 𝔼_ L,  F[Φ(n)] and Var_ L,  F(Φ(n)) by their expectations conditionally on L, i.e.,

    𝔼_ L,  F[Φ(n)]≈∑_i=1^n𝔼_ L[F_i]W_i/W̅_i   and   Var_ L,  F(Φ(n))≈∑_i=1^n𝔼_ L[F_i]W_i/W̅_i(1-W_i/W̅_i).

To estimate these expectations, we note that, by Definition of (F_i)_i≥ 1 (see (<ref>), see also (<ref>) for the definition of (W_i)_i≥ 1),

    𝔼_ L[F_i] 
    = 1/W_i∫_0^L_i xμ(T_i-1 + x)dx
    = 1/W_i∫_0^L_iγδ x(T_i-1+x)^δ-1e^γ (T_i-1+x)^δdx.

In Section <ref>, we prove preliminary technical results that will be useful in the rest.
In Section <ref> we state and prove a rigorous version of (<ref>).
Finally, in Section <ref>, we use Linderberg's theorem to prove (<ref>) and conclude the proof of Proposition <ref>.



 §.§ A preliminary lemma

In this section, we prove the following lemma: recall that, for all i≥ 1, T_i = ∑_j=1^i L_i is the time of the i-th relocation.
 
Let g:→ be a function such that 𝔼[g(L)],Var(g(L))<∞. 


  (i) For all ℓ∈(0,1) almost surely as n→∞,  

    ∑_i=1^n g(L_i)/T_i^1-ℓ
    = 𝔼[g(L)]/ℓ·𝔼[L]^1-ℓ n^ℓ + o(n^ℓ/2).


  (ii) For all ℓ>1, almost surely as n→∞,
 
    ∑_i=1^n g(L_i)/T_i^ℓ 
    = 𝒪(1).


  (iii)
Almost surely as n↑∞,

    ∑_i=1^n g(L_i)/T_i = 𝔼[g(L)]log n + 𝒪(1).




To prove this lemma, we use the following strong law of large numbers, for sums of independent but not identically-distributed random variables:

Let (Δ_i)_i≥ 1 be a sequence of independent random variables,
and let (a_i)_i≥ 1 be a sequence of real numbers such that a_n→+∞ as n↑∞.
Assume that there exists α∈[1,2] such that

    ∑_i≥ 1𝔼[|Δ_i|^α]/a_i^α<∞.

Then, almost surely as n↑∞,

    1/a_n∑_i=1^n Δ_i → 0.



 
(i) By the law of the iterated logarithm T_i=𝔼[L] i + 𝒪(√(i log i)) almost surely as i→∞. Hence,  
∑_i=1^n g(L_i)T_i^ℓ-1 
    = ∑_i=1^n g(L_i)( 𝔼[L] i 
+ 𝒪(√(i logi)))^ℓ-1 

    = 𝔼[L]^ℓ-1 ∑_i=1^n g(L_i) i^ℓ-1 
+ 𝒪( ∑_i=1^n g(L_i) i^ℓ-3/2 √(logi) ), 
almost surely as n↑∞.
For the first sum in (<ref>), note that

    ∑_i=1^n g(L_i) i^ℓ -1 =
    ∑_i=1^n 𝔼[g(L_i)] i^ℓ -1+
    ∑_i=1^n (g(L_i)-𝔼[g(L_i)]) i^ℓ -1.

The latter sum is a sum of independent random variables to which we can apply 
Theorem <ref> with α=2 and a_i = i^ℓ/2. 
Indeed,

    ∑_i=1^∞𝔼[(g(L_i)-𝔼[g(L_i)])^2]i^2(ℓ-1)-ℓ 
    = Var(g(L)) ∑_i=1^∞1/i^ℓ-2
    <∞,

because ℓ-2<-1, by assumption on ℓ.
Thus, Theorem <ref> implies that, almost surely as n↑∞

    ∑_i=1^n (g(L_i)-𝔼[g(L_i)]) i^ℓ -1 = o(n^ℓ/2),

and thus, by (<ref>),

    ∑_i=1^n g(L_i) i^ℓ -1 =
    ∑_i=1^n 𝔼[g(L_i)] i^ℓ -1+o(n^ℓ/2)
    = 𝔼[g(L)] ∑_i=1^n i^ℓ -1 + o(n^ℓ/2).

Now note that

    (n+1)^ℓ-1/ℓ= ∫_1^n+1 x^ℓ-1dx≤∑_i=1^n i^ℓ -1≤∫_0^n x^ℓ-1dx = n^ℓ/ℓ,

which implies that, as n↑∞,

    ∑_i=1^n i^ℓ -1  = n^ℓ/ℓ +o(n^ℓ/2).

We thus get that, almost surely as n↑∞,

    ∑_i=1^n g(L_i)i^ℓ -1 = 𝔼[g(L)]/ℓ· n^ℓ + o(n^ℓ/2).
 
For the second sum in (<ref>), 
we proceed similarly: first note that, for all ε>0,

    ∑_i=1^n g(L_i) i^ℓ -3/2√(log i) =
    𝒪(∑_i=1^n g(L_i) i^ℓ -3/2+ε).

We use Theorem <ref> again, with α = 2 and a_n = n^ε.
Indeed, we have

    ∑_i≥ 1(g(L_i)-𝔼[g(L_i)]) i^2ℓ -3+2ε-2ε
    = Var(g(L)) ∑_i≥ 1 i^2ℓ -3<∞,

because 2ℓ-3<-1 by assumption on ℓ.
Theorem <ref> thus implies that

    ∑_i=1^n g(L_i) i^ℓ -3/2+ε 
    = 𝔼[g(L)] ∑_i=1^n i^ℓ - 3/2+ε + o(n^2ε).

We now choose ε such that 0<ε<min(ℓ-1/2, ℓ/4, (1-ℓ)/2).
Using the fact that

    0≤∑_i=1^n i^ℓ -3/2+ε≤∫_1^n+1 x^ℓ -3/2+εdx
    = 𝒪(n^ℓ-1/2+ε),

we get that 

    ∑_i=1^n g(L_i) i^ℓ -3/2+ε 
    = 𝒪(n^ℓ-1/2+ε) + o(n^2ε)
    = o(n^ℓ/2),

because, with our choice of ε, ℓ-1/2+ε<ℓ/2 and 2ε<ℓ/2.
We have thus proved that, almost surely as n↑∞,

    ∑_i=1^n g(L_i) i^ℓ -3/2√(log i) = o(n^ℓ/2).

Together with (<ref>) and (<ref>), this gives that, almost surely as n↑∞,

    ∑_i=1^n g(L_i)T_i^ℓ -1 
    = 𝔼[g(L)]/ℓ· n^ℓ + o(n^ℓ/2),

which concludes the proof of the first claim.

(iii) We use the strong law of large numbers,
to get that T_i∼ i𝔼[L] almost surely as i↑∞.
This implies

    ∑_i=1^n g(L_i)/T_i^ℓ 
     = 𝒪(1/𝔼[L]^ℓ∑_i=1^n g(L_i)/i^ℓ).

Now, we write

    ∑_i=1^n g(L_i)/i^ℓ
    = 𝔼[g(L)] ∑_i=1^n  1/i^ℓ + ∑_i=1^n g(L_i)-𝔼[g(L)]/i^ℓ,

and note that the second sum is a martingale whose quadratic variation satisfies

    ∑_i=1^n 𝔼[(g(L_i)-𝔼[g(L)])^2]/i^2ℓ 
    = Var(g(L)) ∑_i=1^n 1/i^2ℓ≤Var(g(L)) ∑_i=1^∞1/i^2ℓ<∞,

because ℓ>1.
Thus, this martingale converges almost surely as n↑∞, and we get

    ∑_i=1^n g(L_i)/ i^ℓ 
    = 𝔼[g(L)] ∑_i=1^n  1/i^ℓ + 𝒪(1)
    = 𝒪(1),

because ℓ>1. 
This concludes the proof of the second claim.

(iii) We proceed similarly to the proof of (i) and write that, by the law of the iterated logarithm,
∑_i=1^n g(L_i)/T_i
   = ∑_i=1^n g(L_i)/(i𝔼L + 𝒪(√(ilogi)))
= ∑_i=1^n g(L_i)/i𝔼L (1 + 𝒪(√((logi)/i)))

   = ∑_i=1^n g(L_i)/i𝔼L + 𝒪(∑_i=1^n g(L_i)√(logi)/i^3/2𝔼L).
We now use the fact that log i is negligible in front of any power or i to get that

    ∑_i=1^n g(L_i)√(log i)/i^3/2𝔼L
    = 𝒪(∑_i=1^n g(L_i)/i^5/4𝔼L)
    = 𝒪(1),

by (ii).
This implies that, almost surely as n↑∞,
∑_i=1^n g(L_i)/T_i
   = ∑_i=1^n g(L_i)/i𝔼L  + 𝒪(1)
= 𝔼[g(L)]∑_i=1^n 1/i𝔼L + ∑_i=1^n g(L_i)-𝔼[g(L)]/i𝔼L +𝒪(1)

   = 𝔼[g(L)]/𝔼L·logn + ∑_i=1^n g(L_i)-𝔼[g(L)]/i𝔼L +𝒪(1).
Now, the remaining sum is a martingale whose quadratic variation satisfies

    ∑_i=1^n 𝔼[(g(L_i)-𝔼[g(L)])^1]/i^2(𝔼L)^2
    = Var(g(L))/(𝔼L)^2∑_i=1^n 1/i^2≤Var(g(L))/(𝔼L)^2∑_i≥ 11/i^2<∞.

This implies that the remaining sum converges almost surely as n↑∞, which concludes the proof.




 §.§ Estimating the sums in (<ref>)

The aim of this section is to understand the asymptotic behaviour of ∑_i=1^n W_i𝔼_ L[F_i]/W̅_i and ∑_i=1^n W_i𝔼_ L[F^2_i]/W̅_i. We do this in two separate lemmas.


Almost surely as n→+∞,

    ∑_i=1^n W_i𝔼_ L[F_i]/W̅_i
    = σ(n) + o(n^δ/2).
 











To prove Lemma <ref>, 
we need the following consequence of Borel-Cantelli lemma:

For all δ∈ (0,1), L_i/T_i-1^1-δ→ 0 almost surely as i↑∞.



First note that, by the strong law of large numbers, 
almost surely for all i large enough,
T_i-1≥ i𝔼L/2.
We take p as in (<ref>) (recall that, in this section, we assume that δ∈(0,1)).
Fix ε>0;
by Markov inequality, for all i≥ 1,

    ℙ(L_i>ε (2i𝔼L)^1-δ)
    ≤𝔼[L^p]/ε^p(i𝔼L/2)^(1-δ)p.

By definition of p (see (<ref>)), (1-δ)p>1.
and thus, ∑_i≥ 1ℙ(L_i>ε(2i𝔼L)^1-ℓ)<∞.
By Borel-Cantelli lemma (because the (L_i)_i≥ 1 is a sequence of independent random variables), almost surely for all i large enough, L_i≤ε (2i𝔼L)^1-ℓ,
which concludes the proof (recall that T_i-1≥ i𝔼L/2 almost surely for all i enough).



By (<ref>), for all i≥ 1,
W_i𝔼_L [F_i]
   = ∫_0^L_i γδx(T_i-1+x)^δ-1 e^γ(T_i-1+x)^δdx
= L_i e^γT_i^δ
- ∫_0^L_i e^γ(T_i-1+x)^δdx,
by integration by parts.
Setting u = (T_i-1+x)^δ, we get
W_i𝔼_L [F_i]
   = L_i e^γT_i^δ
- ∫_T_i-1^δ^T^δ_i 1/δu^1/δ-1 e^γudu
= L_i e^γT_i^δ
- T_i^1-δ/δ∫_T_i-1^δ^T^δ_i e^γudu
+  1/δ∫_T_i-1^δ^T^δ_i  [T_i^1-δ -u^1/δ-1] e^γudu

   = L_i e^γT_i^δ
- T_i^1-δ/γδ(e^γT_i^δ-e^γT_i-1^δ)
+  1/δ∫_T_i-1^δ^T^δ_i  [T_i^1-δ -u^1/δ-1] e^γudu
thus,

    ∑_i=1^nW_i𝔼_ L [F_i]/W̅_i
    = T_n  
    - ∑_i=1^n T_i^1-δ/γδ(1-e^-γ (T_i^δ-T_i-1^δ)) 
    + R_n,

where we have set

    R_n = ∑_i=1^n 1/δ∫_T_i-1^δ^T^δ_i[T_i^1-δ -u^1/δ-1] e^γ udu.

We first show that, in probability as n↑∞,
R_n = o(n^δ/2). 
Indeed, we have R_n≥ 0, and
R_n    ≤∑_i=1^n (T_i^1-δ -T_i-1^1-δ)
∑_i=1^n 1/δ∫_T_i-1^δ^T^δ_i e^-γ(T_i^δ- u)du
= ∑_i=1^n T_i^1-δ(1-(1-L_i/T_i)^1-δ)
(1-e^-γ(T_i^δ-T_i-1^δ))

    =∑_i=1^n T_i^1-δ(1-(1-L_i/T_i)^1-δ)
(1-e^-γT_i^δ (1 -(1-L_i/T_i)^δ))
As i↑∞, L_i/T_i → 0 almost surely (see Lemma <ref>), 
and thus

    T_i^1-δ(1-(1-L_i/T_i)^1-δ)
    (1-e^-γ T_i^δ (1 -(1-L_i/T_i)^δ))
    ∼ (1-δ)L_iT_i^-δ(1-e^-γδ L_i T_i^δ-1)
    ∼γδ(1-δ)L^2_i/T_i,

because δ<1 and thus L_iT_i^δ -1→ 0 almost surely as i↑∞ (by Lemma <ref>).
Because, by Lemma <ref>,

    ∑_i=1^n γδ(1-δ)L^2_i/T_i = 𝒪(log n),

we get that, almost surely as n↑∞

    R_n = 𝒪(log n) = o(n^δ/2),

as needed.
We now look at the second term in (<ref>): we write

    ∑_i=1^n T_i^1-δ/γδ(1-e^-γ (T_i^δ-T_i-1^δ)) 
    = ∑_i=1^n T_i^1-δ/γδ(1-e^-γδ L_i T_i^δ-1)
    + R'_n,

where

    R'_n = ∑_i=1^n T_i^1-δ/γδ(e^-γδ L_i T_i^δ-1-e^-γ (T_i^δ-T_i-1^δ)).

First note that, for all x∈ [0,1], (1-x)^δ≤ 1-δ x. This implies

    T_i^δ-T_i-1^δ 
    = T_i^δ(1-(1-L_i/T_i)^δ)
    ≥δ L_i T_i^δ-1,

implying that R'_n≥ 0 for all n≥ 1.
We now prove that R'_n = o(n^δ/2) almost surely as n↑∞.
To do so, we use the fact that, for all x∈[0,1], (1-x)^δ≤ 1-δ x-δ(1-δ)x^2/2, and thus

    T_i^δ-T_i-1^δ≤δ L_i T_i^δ-1 + δ(1-δ)L_i^2 T_i^δ-2/2,

which, in turn, implies
R'_n
   ≤∑_i=1^n T_i^1-δ/γδe^-γδL_i T_i^δ-1(1-e^-γδ(1-δ)L_i^2 T_i^δ-2/2)
≤∑_i=1^n T_i^1-δ/γδ
(1-e^-γδ(1-δ)L_i^2 T_i^δ-2/2)

   ≤∑_i=1^n (1-δ) L_i^2/2 T_i = 𝒪(logn),
by Lemma <ref>.
In total, using the fact that R_n = o(n^δ/2) and R'_n = o(n^δ/2) in (<ref>), we get that, almost surely as n↑∞,
∑_i=1^nW_i𝔼_L [F_i]/W̅_i
   = T_n  
- ∑_i=1^n T_i^1-δ/γδ(1-e^-γδL_i T_i^δ-1) + o(n^δ/2)

   =  ∑_i=1^n T_i^1-δ/γδ(e^-γδL_i T_i^δ-1-1+γδL_i T_i^δ-1) + o(n^δ/2)

   = ∑_i=1^n T_i^1-δ/γδ∑_k≥2(-γδL_i T_i^δ-1)^k/k!+ o(n^δ/2)
= ∑_k≥2(-γδ)^k/γδk! ∑_i=1^n L_i^k/T_i^(1-δ)(k-1)+ o(n^δ/2)
Now note that, for all k≥ k_0 = ⌊3/2-δ/1-δ⌋+1, 

    ∑_i=1^n L_i^k/T_i^(1-δ)(k-1)≤∑_i=1^n L_i^k_0/T_i^(1-δ)(k_0-1)=o(n^δ/2),

almost surely as n↑∞.
Furthermore, because of the alternating signs,

    |∑_k≥ k_0(-γδ)^k/γδ k!∑_i=1^n L_i^k/T_i^(1-δ)(k-1)|
    ≤|(-γδ)^k_0/γδ k_0!∑_i=1^n L_i^k_0/T_i^(1-δ)(k_0-1)| =o(n^δ/2),

almost surely.
This gives
∑_i=1^nW_i𝔼_L [F_i]/W̅_i
   = ∑_k= 2^k_0-1(-γδ)^k/γδk! ∑_i=1^n L_i^k/T_i^(1-δ)(k-1)+ o(n^δ/2)

   = ∑_k= 2^k_0-1(-γδ)^k𝔼[L^k]/γδ𝔼[L]^(1-δ)(k-1)k! ·n^(1-δ)(k-1)+1/(1-δ)(k-1)+1+ o(n^δ/2),
which concludes the proof, by definition of σ(n) (see (<ref>)).



 
Almost surely as n→∞,

    ∑_i=1^n 𝔼_L[F_i^2] W_i/W̅_i 
    = γ𝔼[L^3]/3𝔼[L]^1-δ· n^δ +o(n^δ).




By (<ref>), for all i≥ 1,
W_i𝔼_L [F_i^2]
   = ∫_0^L_i γδx^2(T_i-1+x)^δ-1 e^γ(T_i-1+x)^δdx
= L^2_i e^γT_i^δ
- ∫_0^L_i 2xe^γ(T_i-1+x)^δdx,
by integration by parts.
This implies
W_i𝔼_L [F_i^2]/W̅_i
   = L^2_i - ∫_0^L_i 2xe^-γ(T_i^δ- (T_i-1+x)^δ)dx
= L^2_i - ∫_0^L_i 2xe^-γT_i^δ(1 - (1-(L_i-x)/T_i)^δ)dx

   = L^2_i - ∫_0^L_i 2(L_i-u)e^-γT_i^δ(1 - (1-u/T_i)^δ)du
= L^2_i - ∫_0^L_i 2(L_i-u)(1-γδu T_i^δ-1)du
+ r_i,
where we have set 

    r_i = ∫_0^L_i 2(L_i-u)(1-γδ u T_i^δ-1-e^-γ T_i^δ (1 - (1-u/T_i)^δ))du.

Thus,

    W_i𝔼_ L [F_i^2]/W̅_i
    = γδ T_i^δ-1∫_0^L_i 2(L_i-u) udu
    + r_i
    = γδ L_i^3/3T_i^1-δ + r_i,

which, by Lemma <ref>, implies

    ∑_i=1^n W_i𝔼_ L [F_i^2]/W̅_i
    = γ𝔼[L^3]/2(𝔼L)^1-δ· n^δ + o(n^δ/2) + ∑_i=1^n r_i.

Thus, it only remains to prove that ∑_i=1^n r_i = o(n^δ) almost surely as n↑∞.
First note that, almost surely for all i≥ 1, ϖ_i : u↦e^-γ T_i^δ (1 - (1-u/T_i)^δ)+γδ u T_i^δ-1-1 is non-decreasing on [0,L_i]. 
Indeed, we have, uniformly in u∈ [0,L_i], because L_i/T_i→ 0 almost surely as i↑∞ (see Lemma <ref>),
ϖ'_i(u) 
   = γδT_i^δ-1(1-(1-u/T_i)^δ-1e^-γT_i^δ(1 - (1-u/T_i)^δ))
∼γδT_i^δ-1(1-(1+(1-δ)u/T_i)(1-γδu/T_i^1-δ)

   ∼(γδ)^2 u,
almost surely as i↑∞.
Thus, almost surely for all i large enough, ϖ_i is non-decreasing on [0, L_i] as claimed.
Because ϖ_i(0) = 0, this implies that 0≤ϖ_i(u)≤ϖ_i(L_i) for all u∈ [0,L_i].
This implies that

    |r_i| ≤ϖ_i(L_i) ∫_0^L_i 2(L_i-u)du
    = L_i^2 ϖ_i(L_i)
    = L_i^2 e^-γ T_i^δ (1 - (1-L_i/T_i)^δ)+γδ L_iT_i^δ-1-1.

Because L_i/T_i^δ-1→ 0 almost surely as i↑∞ (see Lemma <ref>), we get that, almost surely as i↑∞,

    |r_i| ≤ o(L_i^3 T_i^δ -1),

which implies ∑_i=1^n r_i = o(∑_i=1^n L_i^3 T_i^δ -1) = o(n^δ), by Lemma <ref>, as claimed. This concludes the proof.




 §.§ Making (<ref>) rigorous



The aim of this section is to prove the following lemma:
 
Almost surely as n→∞,  
    ∑_i=1^n F_i W_i/W̅_i 
    = ∑_i=1^n 𝔼_ L[F_i] W_i/W̅_i  + o(n^δ/2),
  
and  

    ∑_i=1^n F_i^2 W_i/W̅_i( 1-W_i/W̅_i) 
    =  ∑_i=1^n 𝔼_ L[F_i^2] W_i/W̅_i +o(n^δ).
 


Before proving this lemma, note that Lemmas <ref>, <ref>, and <ref> together give that, almost surely as n↑∞,

    ∑_i=1^n F_i W_i/W̅_i  
    = σ(n) + o(n^δ/2)
       and   ∑_i=1^n F^2_i W_i/W̅_i( 1-W_i/W̅_i) 
    = γ𝔼[L^3]/3𝔼[L]^1-δ· n^δ +o(n^δ).



 
By Lemma <ref>, L_i/T_i-1→ 0 almost surely as i↑∞. 
Thus, almost surely as i↑∞,

    T_i-1^δ-T_i^δ
    = T_i-1^δ- (T_i-1+L_i)^δ
    = T_i-1^δ(1-(1+L_i/T_i-1)^δ)
    =𝒪(T_i-1^δ -1 L_i) = 𝒪(T_i^δ-1L_i).




This implies 

    W_i/W̅_i
    =e^γ T_i^δ-e^γ T_i-1^δ/e^γ T_i^δ
    =1- exp(-γ(T_i^δ-T_i-1^δ))
    =𝒪(T_i^δ -1 L_i).
 
Thus,  

    ∑_i=1^n (F_i-𝔼_L[F_i])W_i/W̅_i 
    = 𝒪( ∑_i=1^n (F_i-𝔼_L[F_i])L_iT_i^δ -1).

We apply Theorem <ref> to α = 2, Δ_i =  (F_i-𝔼_ L[F_i])L_iT_i^δ -1 and 
a_i = T_i^δ/2, for all i≥ 1. 
Its assumption holds because, using the fact that F_i≤ L_i almost surely for all i≥ 1 (see (<ref>) for the definition of (F_i)_i≥ 1),

    ∑_i≥1Var_L(F_i)L^2_iT_i^2δ-2/T_i^δ≤∑_i=1^∞ L^4_iT_i^δ-2< ∞,

by Lemma <ref> (because, by assumption, 𝔼L^4<∞).
Thus, Theorem <ref> applies and gives ∑_i=1^n (F_i-𝔼_ L[F_i])L_iT_i^δ -1 = o(T_n^δ/2) = o(n^δ/2) almost surely when n↑∞ (the last equality holds by the strong law of large numbers).
We thus get that, almost surely as n↑∞,

    ∑_i=1^n F_i W_i/W̅_i 
    = ∑_i=1^n 𝔼_L[F_i] W_i/W̅_i + o(n^δ/2),

which concludes the proof of the first statement. 

For the second statement of the lemma, we write

    ∑_i=1^n F_i^2 W_i/W̅_i( 1-W_i/W̅_i) = ∑_i=1^n F_i^2 W_i/W̅_i - ∑_i=1^n F_i^2 W_i^2/W̅_i^2.
 
For the first sum, we proceed as in the proof of the first statement:
we write

    ∑_i=1^n F_i^2 W_i/W̅_i 
    = ∑_i=1^n 𝔼_ L[F_i^2] W_i/W̅_i 
    + ∑_i=1^n (F_i^2-𝔼_ L[F_i^2]) W_i/W̅_i,

and note that, by (<ref>),

    ∑_i=1^n (F_i^2-𝔼_ L[F_i^2]) W_i/W̅_i
    = 𝒪(∑_i=1^n (F_i^2-𝔼_ L[F_i^2])L_i T_i^δ-1).

We now apply Theorem <ref> to α=2, Δ_i = (F_i^2-𝔼_ L[F_i^2])L_i T_i^δ-1, and a_i = T_i^δ. Its assumption holds because

    ∑_i≥ 1Var_ L(F_i^2) L_i^2T_i^2δ-2/T_i^2δ≤∑_i≥ 1 L_i^4T_i^-2<∞,

by Lemma <ref>.
Theorem <ref> thus implies that, almost surely as n↑∞,

    ∑_i=1^n (F_i^2-𝔼_ L[F_i^2])L_i T_i^δ-1 = o(n^δ),

and thus, by (<ref>),

    ∑_i=1^n (F_i^2-𝔼_ L[F_i^2]) W_i/W̅_i = o(n^δ).

For the second sum of (<ref>), we proceed along the same lines (we skip the technical details) and prove that, almost surely as n↑∞,

    ∑_i=1^n (F_i^2-𝔼_L[F_i^2])W_i^2/W̅_i^2 
    = 𝒪( ∑_i=1^n (F_i^2-𝔼_L[F_i^2]) L_i^2 T_i^2(δ -1))
    = o(n^δ),

which implies

    ∑_i=1^n F_i^2W_i^2/W̅_i^2 
    = ∑_i=1^n 𝔼_ L[F_i^2]W_i^2/W̅_i^2 +o(n^δ).

Now,

    ∑_i=1^n 𝔼_ L[F_i^2]W_i^2/W̅_i^2 
    =𝒪(∑_i=1^n 𝔼_ L[F_i^2]L_i^2T_i^2(δ-1))
    =𝒪(∑_i=1^n L_i^4 T_i^2(δ-1)).

Applying Theorem <ref> to α = 2, Δ_i = L_i^4 T_i^2(δ-1), and a_i = T_i^δ, we get

    ∑_i=1^n 𝔼_ L[F_i^2]W_i^2/W̅_i^2 = o(T_n^δ) = o(n^δ).

This, together with (<ref>), gives that, almost surely as n↑∞,

    ∑_i=1^n F_i^2W_i^2/W̅_i^2  = o(n^δ).

By (<ref>) and (<ref>), this concludes the proof.






 §.§ Proof of Proposition <ref>

As mentioned at the beginning of this section, the proof of Proposition <ref>
relies on applying Lindeberg's theorem. We apply it, conditionally on L and F, 
to the sum

    Φ(n) - ∑_i=1^n F_iW_i/W̅_i
    = ∑_i=1^n F_i( 1_i≺ n - W_i/W̅_i).

Indeed, this is a sum of centred random variables because 𝔼_ L,  F[ 1_i≺ n] = W_i/W̅_i, by Lemma <ref>.
To apply Lindeberg's theorem, we need to show that, for all ε>0,

    1/a_n^2∑_i=1^n 
    𝔼_ L, F[F_i^2( 1_i≺ n-W_i/W̅_i)^2 1_|F_i( 1_i≺ n-W_i/W̅_i)|>ε a_n] → 0,

as n↑∞, where 

    a_n^2:= ∑_i=1^n Var_ L,  F(F_i 1_i≺ n)
    = ∑_i=1^n F_i^2 Var_ L,  F( 1_i≺ n)
    = ∑_i=1^n F_i^2W_i/W̅_i(1-W_i/W̅_i),

by Lemma <ref>.
First note that, by definition of (F_i)_i≥ 1 (see (<ref>)), F_i≤ L_i almost surely for all i≥ 1. Also, 1_i≺ n-W_i/W̅_i∈ [-1, 1] almost surely for all i≥ 1. Thus, almost surely, 
1/a_n^2∑_i=1^n 
𝔼_L,F[F_i^2(1_i≺n-W_i/W̅_i)^21_|F_i(1_i≺n-W_i/W̅_i)|>εa_n] 
   ≤1/a_n^2∑_i=1^n L_i^2 ℙ_L,F(|F_i(1_i≺n-W_i/W̅_i)|>εa_n)

   ≤1/ε^2 a_n^4∑_i=1^n L_i^2 𝔼_L,F[|F_i(1_i≺n-W_i/W̅_i)|^2],
by Markov inequality. Using again the fact that |F_i( 1_i≺ n-W_i/W̅_i)|≤ L_i almost surely for all i≥ 1, we get 
1/a_n^2∑_i=1^n 
𝔼_L,F[F_i^2(1_i≺n-W_i/W̅_i)^21_|F_i(1_i≺n-W_i/W̅_i)|>εa_n] 
   ≤1/ε^2 a_n^4∑_i=1^n L_i^4 
= n𝔼[L^4]/ε^2 a_n^4,
almost surely as n↑∞, by the strong law of large numbers.
Now, by (<ref>), almost surely as n↑∞,

    a_n^2 = γ𝔼[L^3]/3𝔼[L]^1-δ· n^δ +o(n^δ).

Thus,

    1/a_n^2∑_i=1^n 
    𝔼_ L, F[F_i^2( 1_i≺ n-W_i/W̅_i)^2 1_|F_i( 1_i≺ n-W_i/W̅_i)|>ε a_n] = 𝒪(n^1-2δ) → 0,

almost surely as n↑∞ because δ>1/2.
Thus, Lindeberg's theorem applies and gives that, conditionally on L and F, in distribution as n↑∞,

    Φ(n) - ∑_i=1^n F_iW_i/W̅_i/a_n⇒𝒩(0,1).

By (<ref>) and (<ref>), this implies

    Φ(n) - σ(n)+o(n^δ/2)/√(γ𝔼[L^3]/3𝔼[L]^1-δ· n^δ)⇒𝒩(0,1),

which concludes the proof of Proposition <ref>.











§ PROOF OF THEOREM <REF>

In this section, we assume that δ = 1.
The proof follows the same route as in the case δ <1, and the key ingredient is the following limiting theorem for Φ(n):
 
Under the assumptions of Theorem <ref> and if δ = 1, then, in distribution as n↑∞,

    Φ(n) - n𝔼[L-(1-e^-γ L)/γ]/√(n)⇒Ω_1 + Ω_2,

where

    Ω_1∼𝒩(0, 1/γ^2 + 𝔼[L^2-(L+e^-γ L/γ)^2])   and   Ω_2∼𝒩(0,Var(L- 1-e^-γ L/γ)),

and

    Cov(Ω_1, Ω_2) 
    = Var(L - 1- e^-γ L/γ).
 


Before proving Proposition <ref>, we show how it implies Theorem <ref>:

 
By the strong law of large numbers, i(t)→∞ almost surely as t↑∞. Thus, by Proposition <ref>, in distribution as t↑∞,

    Φ(i(t)-1)-i(t)𝔼[1-(1-e^-γ L)/γ]/√(i(t))⇒Ω_1+Ω_2.

Now, by the central limit theorem, in distribution as n↑∞

    ∑_i=1^n L_i - n𝔼L/√(n)⇒Ψ∼𝒩(0, Var(L)).

Thus, because i(t)↑∞ almost surely as t↑∞, we get

    ∑_i=1^i(t) L_i - i(t)𝔼L/√(i(t))⇒Ψ.

By standard results in renewal theory, L_i(t) converges in distribution as t↑∞. Because T_i(t)-L_i(t)≤ t<T_i(t), this implies that T_i(t) = ∑_i=1^i(t) L_i = t+𝒪(1) in probability as t↑∞.
Thus, in distribution as t↑∞,

    t - i(t)𝔼L/√(i(t))⇒Ψ.

This implies

    Φ(i(t)-1)- t𝔼[L-(1-e^-γ L)/γ]/𝔼[L]/√(i(t))⇒Ω_1+Ω_2 + Ω_3,

where we have set Ω_3 = Ψ𝔼[L-(1-e^-γ L)/γ]/𝔼[L].
Because A(t)/√(i(t))→ 0 in probability, by Lemma <ref>, and because, by definition, S(t) = Φ(i(t)-1)+A(t), this implies that

    S(t)- t𝔼[L-(1-e^-γ L)/γ]/𝔼[L]/√(i(t))⇒Ω_1+Ω_2 + Ω_3,

which implies

    S(t)- t𝔼[L-(1-e^-γ L)/γ]/𝔼[L]/√(t)⇒1/√(𝔼L)(Ω_1+Ω_2 + Ω_3) =: Ω

By Skorokhod's representation theorem, there exist a probability space (which we call Skorokhod's probability space) on which one can define a process (S̃(t))_t≥ 0 and a random variable Ω̃ such that S̃(t) = S(t) in distribution for all t≥ 0, Ω̃= Ω in distribution, and

    S̃(t)- t𝔼[L-(1-e^-γ L)/γ]/𝔼[L]/√(i(t))→Ω̃,

almost surely as t↑∞.
In Skorokhod's probability space, there also exist a process (Z̃(t))_t≥ 0 and a random variable Γ̃ of distribution γ such that (Z̃(t))_t≥ 0 is independent of (S̃(t))_t≥ 0, Z̃(t) = Z(t) in distribution for all t≥ 0, and

    Z̃(t)-a(t)/b(t)→Γ̃,

almost surely as t↑∞. 
Thus, by Assumption (A'2),

    Z̃(S̃(t))-a(s(t))/b(s(t))   = Z̃(S̃(t))-a(S̃(t))/b(S̃(t))·b(S̃(t))/a(s(t))  + a(S̃(t))-a(s(t))/b(s(t))
       → f(Ω̃)+Γ̃g(Ω̃).

This implies convergence in distribution on the original probability space. Thus, it only remains to calculate Cov(Ω_1, Ω_3) and Cov(Ω_2, Ω_3); this is done in Section <ref>, where we prove that

    Cov(Ω_1, Ψ) 
    =Cov(Ω_2, Ψ) 
    =Cov(L, L+ e^-γ L/γ).

This concludes the proof of Theorem <ref> because Ω_3 = Ψ𝔼[L-(1-e^-γ L)/γ]/𝔼[L].


As in Section <ref>, the idea to prove Proposition <ref> is to
apply Lindeberg's theorem. However, this time, we only condition on L (and not on F).
This will give

    Φ(n)-𝔼_ L[Φ(n)]/√(Var_ L(Φ(n)))⇒𝒩(0,1).

By Lemma <ref>, and because, 
given L, the sequences (F_i)_1≤ i≥ n and ( 1_i≺ n)_1≤ i≤ n are independent, we get

    𝔼_ L[Φ(n)]
    =∑_i=1^nW_i𝔼_ L[F_i]/W̅_i.

For the variance, we use the fact that, given L, (F_i 1_i≺ n)_1≤ i≤ n is a sequence of independent random variables, and thus 

    Var_ L(Φ(n)) = ∑_i=1^n Var_ L(F_i  1_i≺ n).

Using the total variance law in the first equality and Lemma <ref> in the second one, we get that, for all 1≤ i≤ n,
Var_L(F_i 1_i≺n)
   = Var_L(𝔼_L,F[F_i 1_i≺n])
+ 𝔼_L[Var_L,F(F_i 1_i≺n)]
= Var_L(F_iW_i/W̅_i)
+ 𝔼_L[F_i^2W_i/W̅_i(1-W_i/W̅_i)]

   = (W_i/W̅_i)^2 Var_L(F_i) + W_i/W̅_i(1-W_i/W̅_i)𝔼_L[F_i^2]
= W_i/W̅_i 𝔼_L[F_i^2] - (W_i/W̅_i)^2𝔼_L[F_i]^2.

We thus get

    Var_ L(Φ(n)) 
    = ∑_i=1^n(W_i/W̅_i𝔼_ L[F_i^2] - (W_i/W̅_i𝔼_ L[F_i])^2).

The rest of the section is dedicated to proving Proposition <ref>: In Section <ref>, we give asymptotic estimates for 𝔼_ L[Φ(n)] and 
Var_ L(Φ(n)). In Section <ref>, we apply Lindeberg theorem to prove (<ref>) and conclude the proof.



 §.§ Estimating the expectation and variance of Φ(n)

In this section, we prove the following lemma:

Almost surely for all n≥ 1,

    𝔼_ L[Φ(n)] = 
    ∑_i=1^n(L_i - 1- e^-γ L_i/γ),

and

    Var_ L(Φ(n)) = n/γ^2+
    ∑_i=1^n (L^2_i-(L_i+e^-γ L_i/γ)^2).



Before proving this result, we note that, by the central limit theorem for 𝔼_ L[Φ(n)]
and the law of large numbers for Var_ L(Φ(n)),

    1/√(n)(𝔼_ L[Φ(n)] - n𝔼[L - 1- e^-γ L/γ])
    ⇒𝒩(0,Var(L - 1- e^-γ L/γ) ),

in distribution as n↑∞, and

    Var_ L(Φ(n)) =n/γ^2+n𝔼[L^2-(L+e^-γ L/γ)^2] + o(n),

almost surely as n↑∞.


First note that, in the case δ = 1, for all i≥ 1,

    W_i/W̅_i = W̅_i - W̅_i-1/W̅_i 
    = e^γ T_i - e^γ T_i-1/e^γ T_i
    = 1- e^-γ L_i.

Also, using the definition of (F_i)_i≥ 1 (see (<ref>)) in the first equality 
and integration by parts in the third one, we get that, for all i≥ 1,
W_i 𝔼_L[F_i]
   = ∫_0^L_i γxe^γ(T_i-1+x)dx
= ∫_T_i-1^T_i γ(x-T_i-1)e^γxdx
= [(x-T_i-1)e^γx]_T_i-1^T_i
- ∫_T_i-1^T_i e^γxdx

   = L_i e^γT_i - e^γT_i-e^γT_i-1/γ,because, μ(x) = γe^γ x in the case when δ =1.
Using (<ref>), we thus get that, for all i≥ 1,

    W_i 𝔼_ L[F_i]/W̅_i= L_i - 1- e^-γ L_i/γ.

Thus, by (<ref>), we get

    𝔼_ L[Φ(n)] 
    = ∑_i=1^n(L_i - 1- e^-γ L_i/γ).

For the variance, recall that, by (<ref>),

    Var_ L(Φ(n)) 
    = ∑_i=1^n(W_i/W̅_i𝔼_ L[F_i^2] - (W_i/W̅_i𝔼_ L[F_i])^2).

By (<ref>), we have

    (W_i/W̅_i𝔼_ L[F_i])^2
    =(L_i - 1- e^-γ L_i/γ)^2.

Also, by definition of (F_i)_i≥ 1, for all i≥ 1,
W_i𝔼_L[F_i^2]
   = ∫_0^L_i γx^2 e^γ(T_i-1+x)dx
= ∫_T_i-1^T_i γ(x-T_i-1)^2 e^γxdx

   = [(x-T_i-1)^2 e^γx]_T_i-1^T_i
- 2∫_T_i-1^T_i  (x-T_i-1) e^γxdx
= L_i^2 W̅_i - 2/γW_i𝔼_L[F_i],
where we have used the fact that W_i𝔼_ L[F_i] = ∫_T_i-1^T_iγ(x-T_i-1) e^γ xdx (as seen in (<ref>)).
Now using (<ref>), we get

    W_i𝔼_ L[F_i^2]/W̅_i 
    = L_i^2 - 2/γ(L_i - 1- e^-γ L_i/γ).

This, together with (<ref>), gives

    W_i/W̅_i𝔼_ L[F_i^2] - (W_i/W̅_i𝔼_ L[F_i])^2
    =L_i^2 - 2/γ(L_i - 1- e^-γ L_i/γ)-(L_i - 1- e^-γ L_i/γ)^2
    = L^2_i+ 1/γ^2-(L_i+e^-γ L_i/γ)^2,

which concludes the proof.





 §.§ Applying Lindeberg's theorem

In this section, we prove that, conditionally on L, in distribution as n↑∞,

    Φ(n)-𝔼_ L[Φ(n)]/√(Var_ L(Φ(n)))⇒𝒩(0,1).

To do so, we apply Lindeberg's theorem to the triangular array 
(F_i  1_i≺ n)_1≤ i≤ n, conditionally on L.
For all n≥ 1, we let

    a_n^2 
    = ∑_i=1^n Var_ L(F_i  1_i≺ n)
    = Var_ L(Φ(n)) 
    ∼n/γ^2+n𝔼[L-(1+e^-γ L/γ)^2],

almost surely as n↑∞.
To apply Lindeberg's theorem, we need to show that

    1/a_n^2∑_i=1^n 𝔼_ L[
    (F_i  1_i≺ n-𝔼_ L[F_i  1_i≺ n])^2
     1_|F_i  1_i≺ n-𝔼_ L[F_i  1_i≺ n|>ε a_n]
    → 0,

almost surely as n↑∞, for all ε>0.
Using the fact that, almost surely, 0≤ F_i 1_i≺ n≤ L_i for all 1≤ i≤ n, we get
1/a_n^2∑_i=1^n 𝔼_L[
(F_i 1_i≺n-𝔼_L[F_i 1_i≺n])^2
1_|F_i 1_i≺n-𝔼_L[F_i 1_i≺n|>εa_n
]
   ≤1/a_n^2∑_i=1^n L_i^2ℙ_L(
|F_i 1_i≺n-𝔼_L[F_i 1_i≺n|>εa_n
)

   ≤1/a_n^2∑_i=1^n L_i^2·Var_L(F_i 1_i≺n)/ε^2 a_n^2,
by Markov's inequality. Now, using again the fact that 0≤ F_i 1_i≺ n≤ L_i almost surely for all 1≤ i≤ n, we get

    1/a_n^2∑_i=1^n 𝔼_ L[
    (F_i  1_i≺ n-𝔼_ L[F_i  1_i≺ n])^2
     1_|F_i  1_i≺ n-𝔼_ L[F_i  1_i≺ n|>ε a_n]
    ≤1/ε^2 a_n^4∑_i=1^n L_i^4 ∼𝔼[L^4]n/ε^2 a_n^4→ 0,

almost surely as n↑∞, by (<ref>).
This concludes the proof of (<ref>).



 §.§ Proof of Proposition <ref>

The proof of Proposition <ref> relies on Equations (<ref>), (<ref>)  and (<ref>).
Indeed, we write
Φ(n) - n𝔼[1-(1-e^γL)/γ]/√(n)
   = Φ(n) - 𝔼_L[Φ(n)]/√(Var_L(Φ(n)))
·√(Var_L(Φ(n))/n)
+ 𝔼_L[Φ(n)] - n𝔼[1-(1-e^γL)/γ]/√(n)

   ⇒Ω_1 + Ω_2,
where Ω_1 and Ω_2 are as in (<ref>).
To prove Proposition <ref>, 
it only remains to calculate Cov(Ω_1, Ω_2).
To do so, note that

    Cov(Φ(n), 𝔼_ L[Φ(n)])
    =𝔼[Φ(n) 𝔼_ L[Φ(n)]]
    -𝔼[Φ(n)] 𝔼[𝔼_ L[Φ(n)]]
    = 𝔼[𝔼_ L[Φ(n)]^2]
    -𝔼[𝔼_ L[Φ(n)]]^2,

by the tower rule.
Thus,

    Cov(Φ(n), 𝔼_ L[Φ(n)])
    =Var(𝔼_ L[Φ(n)])
    = Var(∑_i=1^n(L_i - 1- e^-γ L_i/γ)),

by Lemma <ref>.
By independence,

    Cov(Φ(n), 𝔼_ L[Φ(n)])
    = nVar(L - 1- e^-γ L/γ).

Thus,
Cov(Ω_1,Ω_2)
   =lim_n↑∞Cov(Φ(n) - 𝔼_L[Φ(n)]/√(n), 
𝔼_L[Φ(n)] - n𝔼[1-(1-e^γL)/γ]/√(n))

   = lim_n↑∞ 1/n Cov(Φ(n), 𝔼_L[Φ(n)])
= Var(L - 1- e^-γL/γ),
which concludes the proof.



 §.§ Covariances

The aim of this section is to prove Equation (<ref>).
Note that, for all n≥ 1,
Cov(∑_i=1^n L_i, 𝔼_L[Φ(n)])
   = Cov(∑_i=1^n L_i, ∑_i=1^n(1 - 1- e^-γL_i/γ))
= ∑_i=1^n ∑_j=1^n  Cov(L_i, (1 - 1- e^-γL_j/γ))

   = ∑_i=1^n  Cov(L_i, (L_i - 1- e^-γL_i/γ))
= nCov(L, (L - 1- e^-γL/γ))

   = nVar(L) + nCov(L, e^-γL/γ).
Thus, by definition of Ψ (see (<ref>)) and Ω_2 (see (<ref>))

    Cov(Ψ, Ω_2)
    = lim_n→∞Cov(∑_i=1^n L_i - n𝔼L/√(n),
    𝔼_ L[Φ(n)] - n𝔼[1-(1-e^γ L)/γ]/√(n))
    = Var(L) + Cov(L, e^-γ L/γ).

Finally, by the tower rule,

    Cov(∑_i=1^n L_i, Φ(n))
    = Cov(∑_i=1^n L_i, 𝔼_ L[Φ(n)]),

which concludes the proof of (<ref>).
 










§ PROOF OF THEOREM <REF>

In this section, we assume that δ >1.
As in the two previous cases, we need to first understand the asymptotic behaviour of Φ(n):
 
If δ>1, under the assumptions of Theorem <ref>, then, conditionally on L,

almost surely as n↑∞,

    Φ(n) =  
    T_n + 𝒪(1)     if δ >2
     T_n - ∑_i=1^n 1/γδ T_i^δ-1 + 𝒪(1)
        if δ∈ (3/2, 2]
     T_n - ∑_i=1^n 1/γδ T_i^δ-1 + o(n^3/2-δ(log n)^2)
        if δ∈ (1, 3/2],


Before proving Proposition <ref>, we how how it implies Theorem <ref>:


Since, by the strong law of large numbers, i(t)↑∞ almost surely as t↑∞, 
Proposition <ref> implies that, almost surely as t↑∞,

    Φ(i(t)-1)
    =   
    T_i(t)-1 + 𝒪(1)     if δ >2
     T_i(t)-1 - ∑_i=1^i(t)-11/γδ T_i^δ-1 + 𝒪(1)
        if δ∈ (3/2, 2]
     T_i(t)-1 - ∑_i=1^i(t)-11/γδ T_i^δ-1 + o(√(i(t)))
        if δ∈ (1, 3/2]

Recall that, by definition, i(t) is the integer such that T_i(t)-1≤ t < T_i(t)-1 + L_i(t) = T_i(t).
By standard renewal theory, L_i(t) converges in distribution as t↑∞ (see the proof of Lemma <ref>), and thus, L_i(t) = 𝒪(1) in probability as t↑∞. 



For δ∈ (1,2], we have, on the one hand,

    ∑_i=1^i(t)-11/γδ T_i^δ-1≤∑_i=1^i(t)-1∫_T_i-1^T_i1/γδ x^δ-1dx
    = ∫_0^T_i(t)-11/γδ x^δ-1dx
    = T_i(t)-1^2-δ/γδ (2-δ) 
    = t^2-δ/γδ (2-δ) + 𝒪(1),

and, on the other hand,

    ∑_i=1^i(t)-11/γδ T_i^δ-1≥∑_i=1^i(t)-1∫_T_i^T_i+11/γδ x^δ-1dx
    = ∫_T_1^T_i(t)1/γδ x^δ-1dx
    = T_i(t)^2-δ - T_1^2-δ/γδ (2-δ).

Because T_i(t) = t + 𝒪(1) in probability as t↑∞, and because T_1 = L_1 = 𝒪(1) as well, we get

    ∑_i=1^i(t)-11/γδ T_i^δ-1 
    = t^2-δ/γδ (2-δ) + 𝒪(1),

in probability as t↑∞, if δ∈(1, 2].
Now recall that, in distribution for all t≥ 0, S(t) = Φ(i(t)-1) + A(t) (see (<ref>)).

Thus, because T_i(t)-1 + A(t) = t, by definition, we get

    S(t) = Φ(i(t)) + A(t) = 
    
    t + 𝒪(1)     if δ >2
     t - t^2-δ/γδ(2-δ)𝔼[L] + 𝒪(1)
        if δ∈ (3/2, 2]
     t - t^2-δ/γδ(2-δ)𝔼[L] + o(t^3/2-δ(log t)^2)     if δ∈ (1, 3/2].

By definition of s(t) (see (<ref>) for δ>1), 
we get 
Z(S(t))-a(s(t))/b(s(t))
    = Z(S(t))-a(S(t))/b(S(t))·b(S(t))/b(s(t)) + a(S(t))-a(s(t))/b(s(t))

    ⇒Γ,
by Assumption (A2_δ).
This concludes the proof because X(t) = Z(S(t)) in distribution for all t≥ 0 (see Section <ref>).




 §.§ Preliminary lemmas

We start with the following preliminary lemmas:

For all δ>1, if 𝔼[L^2]<∞,
then, for all ε>0, 
almost surely for all i large enough, L_i/T_i≤ε.



We prove this using Borel-Cantelli's lemma.
Indeed, first note that, by the strong law of large numbers, almost surely for all i large enough, T_i≥ i𝔼[L]/2. Also, for all i≥ 1, for all ε>0,

    ℙ(L_i ≥ε (i𝔼[L]/2))
    ≤𝔼[L^2]/ε^2 (i𝔼[L]/2)^2,

which is summable.
Thus, Borel-Cantelli's lemma implies that, almost surely for all i large enough, 

    L_iT_i^-1≤ L_i (i𝔼[L]/2)^-1<ε,

as desired.




For all δ>1, almost surely

    ∑_i≥ 1L^2_i/T_i-1^δ<∞.




First note that, by the strong law of large numbers, T_i ∼ i𝔼[L] almost surely as i↑∞. Thus, ∑_i≥ 1 L^2_i T_i-1^-δ converges if and only if ∑_i≥ 1 L^2_i i^-δ does. Now, we write

    ∑_i≥ 1 L^2_i i^-δ
    =  𝔼[L] ∑_i≥ 1 i^-δ
    + ∑_i≥ 1 (L^2_i-𝔼[L^2]) i^-δ.

The first sum above is convergent because δ >1. For the second sum, note that
(M_n := ∑_i=1^n (L^2_i-𝔼[L^2]) i^-δ)_n≥ 1 is a martingale whose quadratic variation satisfies

    ⟨ M⟩_n =∑_i=1^n Var(L^2)/i^2δ≤𝔼[L^4] ∑_i≥ 11/i^2δ<∞,

because δ>1.



Almost surely as i↑∞,

    ∑_i=1^n 1/T_i^δ-1 =
    𝒪(1)     if δ>2
    n^2-δ/(2-δ)𝔼[L]^δ-1 + 𝒪(1)     if δ∈ (3/2, 2]
    n^2-δ/(2-δ)𝔼[L]^δ-1 + 𝒪(n^3/2 - δ√(log n))     if δ∈ (1, 3/2].




Almost surely as i↑∞,

    ∑_i=1^n e^-γδ L_i T_i^δ-1/T_i^δ-1 =
    𝒪(1).




First note that, for all δ>2,

    ∑_i=1^n e^-γδ L_i T_i^δ-1/T_i^δ-1≤∑_i=1^n 1/T_i^δ-1 <∞,

by Lemma <ref>,
which concludes the proof.
We first note that, for all α≥ 1, for all x≥ 0, F_α(x):=x^αe^-x≤ (α/e)^α.
Indeed, for all x≥ 0, F'_α(x) = (α - x)x^α-1e^-x and thus F reaches its maximum at x= α and this maximum is F(α) = (α/e)^α, as claimed.
Thus, for all α≥ 1,

    ∑_i=1^n e^-γδ L_i T_i^δ-1/T_i^δ-1≤(α/e)^α∑_i=1^n 1/(γδ L_i)^α T_i^(δ-1)(α+1)






For all δ>1, for all x∈[0,1],

    1-δ x≤ (1-x)^δ≤ 1-δ x+δ(δ-1) x^2





 §.§ Proof of Proposition <ref>





To prove Proposition <ref>, we first write

    Φ(n) 
    = ∑_i=1^n (F_i 1_i≺ n-𝔼_ L[F_i 1_i≺ n])+ ∑_i=1^n 𝔼_ L[F_i 1_i≺ n].

We treat the two sums in two separate lemmas:


Almost surely as n↑∞,

    ∑_i=1^n (F_i 1_i≺ n-𝔼_ L[F_i 1_i≺ n])
    = 𝒪(1).




Given L, we let (B_i)_i≥ 1 be a sequence of independent Bernoulli-distributed random variables of respective parameters W_i/W̅_i, independent of (F_i)_i≥ 1. 
Recall that, by Lemma <ref>, for all n≥ 1, ( 1_i≺ n)_1≤ i≤ n = (B_i)_1≤ i≤ n.
Also note that, by definition, conditionally on L,

    (M_n :=∑_i=1^n (F_i 1_i≺ n-𝔼_ L[F_i 1_i≺ n]))_n≥ 0

is a martingale.
In the rest of the proof, we show that its quadratic variation satisfies

    ⟨ M ⟩_n= ∑_i≥ 1Var_ L(F_iB_i)<∞.

For all i≥ 1, by (<ref>),

    Var_ L(F_i B_i) 
    = W_i/W̅_i𝔼_ L[F_i^2]-(W_i/W̅_i)^2
    𝔼_ L[F_i]^2

By definition of F_i (see (<ref>)) in the first equality, and integration by parts in the second,
W_i𝔼_L[F_i^2]
   =∫_0^L_i x^2 γδ(T_i-1+x)^δ-1e^γ(T_i-1+x)^δdx
= [x^2e^γ(T_i-1+x)^δ]_0^L_i
- ∫_0^L_i 2x e^γ(T_i-1+x)^δdx

   = L_i^2 W̅_i
-  ∫_0^L_i 2x e^γ(T_i-(L_i-x))^δdx,
because W̅_i = e^γ T_i^δ, by definition (see (<ref>)).
We now use the fact that, for all x∈[0,1], (1-x)^δ≥ 1-δ x, and get

    W_i𝔼_ L[F_i^2]
    ≤ L_i^2 W̅_i
    -  ∫_0^L_i 2x exp(γ T_i^δ(1-δ·L_i-x/T_i))dx
    = L_i^2 W̅_i
    -  2W̅_i ∫_0^L_i x exp(-γδ T_i^δ-1(L_i-x))dx.

Using integration by parts again, we get
   ∫_0^L_i x  exp(-γδT_i^δ-1(L_i-x))dx

   = [x exp(-γδT_i^δ-1(L_i-x))/γδT_i^δ-1]_0^L_i
- 1/γδT_i^δ-1∫_0^L_iexp(-γδT_i^δ-1(L_i-x))dx

   = L_i/γδT_i^δ-1 - 1-e^-γδL_i T_i^δ-1/(γδT_i^δ-1)^2.
This implies

    W_i𝔼_ L[F_i^2]/W̅_i≤ L_i^2
    -  2L_i/γδ T_i^δ -1
    + 1/(γδ T_i^δ-1)^2.

Similarly,
W_i𝔼_L[F_i] 
   = ∫_0^L_i x γδ(T_i-1+x)^δ-1e^γ(T_i-1+x)^δdx
= [x e^γ(T_i-1+x)^δ]_0^L_i
-  ∫_0^L_i e^γ(T_i-1+x)^δdx

   = L_i W̅_i -   ∫_0^L_i e^γ(T_i-1+x)^δdx
= L_i W̅_i - 1/δ∫_T_i-1^δ^T_i^δ u^1/δ-1 e^γudu,
where we have changed variables and set u = (T_i-1+x)^δ.
We thus get

    W_i𝔼_ L[F_i]/W̅_i≥ L_i - 1/δW̅_i T_i-1^δ-1∫_T_i-1^δ^T_i^δe^γ udu
    = L_i - 1/γδ T_i-1^δ-1.

Using (<ref>) and (<ref>), we thus get
Var_L(F_i B_i)
   ≤L_i^2
-  2L_i/γδT_i^δ-1
+ 1/(γδT_i^δ-1)^2 
- ( L_i - 1/γδT_i-1^δ-1)^2

   = 2L_i/γδ (1/T_i-1^δ-1-1/T_i^δ-1) +
1/(γδT_i^δ-1)^2 - 1/(γδT_i-1^δ-1)^2
≤2L_i/γδT_i-1^δ-1 (1-(1-L_i/T_i)^δ-1)

   ≤2(δ-1)L_i^2/γδT_i-1^δ-1T_i
≤2(δ-1)L_i^2/γδT_i-1^δ,
where we have used the fact that, 
for all x∈[0,1], (1-x)^δ-1≥ 1-(δ-1) x (since δ>1).
We thus get that

    ∑_i≥ 1Var_ L(F_i B_i) 
    ≤∑_i≥ 12(δ-1)L_i^2/γδ T_i-1^δ 
    <∞,

by Lemma <ref>.
Thus, (<ref>) holds and implies that (M_n)_n≥ 1 converges almost surely as n↑∞, which concludes the proof.



Almost surely as n↑∞,

    ∑_i=1^n 𝔼_ L[F_i 1_i≺ n] 
    = 
    T_n + 𝒪(1)     if δ >2
     T_n - ∑_i=1^n 1/γδ T_i^δ-1 + 𝒪(1)
        if δ∈ (3/2, 2]
     T_n - ∑_i=1^n 1/γδ T_i^δ-1 + o(n^3/2-δ(log n)^2)
        if δ∈ (1,3/2].




First note that, for all i≥ 1, 𝔼_ L[F_i 1_i≺ n]  = W_i𝔼_ L[F_i]/W̅_i, because, given L,  (F_i)_1≤ i≤ n is independent of ( 1_i≺ n),
and because, by Lemma <ref>, 1_i≺ n is Bernoulli-distributed with parameter W_i/W̅_i.
By definition of (F_i)_i≥ 1 (see Definition (<ref>)) in the first equality, and integration by parts in the second, we get
W_i𝔼_L[F_i]/W̅_i
   = ∫_0^L_i γδx(T_i-1+x)^δ-1 
e^-γ[T_i^δ-(T_i-1+x)^δ]dx

   = L_i -  ∫_0^L_i e^-γ[T_i^δ-(T_i-1+x)^δ]dx
= L_i -  ∫_0^L_i e^-γT_i^δ [1 -(1-u/T_i)^δ]du,
where we have changed variables and set u = L_i-x.
This means that

    ∑_i=1^n𝔼_ L[F_i 1_i≺ n]  
    = T_n - ∑_i=1^n ∫_0^L_ie^-γ T_i^δ [1 -(1-u/T_i)^δ]du.

Thus, it only remains to show that

    ∑_i=1^n ∫_0^L_ie^-γ T_i^δ [1 -(1-u/T_i)^δ]du
    = 𝒪(1)    if δ >2
    ∑_i=1^n 1/γδ T_i^δ-1 + 𝒪(1)
        if δ∈ (3/2, 2]
    ∑_i=1^n 1/γδ T_i^δ-1 + o(n^3/2-δ(log n)^2)
        if δ∈ (1, 3/2],

almost surely as n↑∞.





By Lemma <ref>, because u≤ L_i≤ T_i almost surely,
∫_0^L_i e^-γδu T_i^δ-1du
≤∫_0^L_i e^-γT_i^δ [1 -(1-u/T_i)^δ]du
   ≤∫_0^L_i e^-γδu T_i^δ-1(1-(δ-1)u/T_i)du


   ≤∫_0^L_i e^-γδu T_i^δ-1(1-(δ-1)L_i/T_i)du.In the last inequality, we have used the fact that u≤ L_i and δ>1.
This implies

    1-e^-γδ L_i T_i^δ-1/γδ T_i^δ-1≤∫_0^L_ie^-γ T_i^δ [1 -(1-u/T_i)^δ]du
    ≤1/γδ T_i^δ-1(1-(δ-1)L_i/T_i).

Note that, by Lemma <ref>, almost surely, L_i/T_i<1/2(δ-1) for all i large enough.
Using the fact that 1/1-u≤ 1+2u for all u∈[0,1/2], we thus get that, almost surely for all i large enough,

    1-e^-γδ L_i T_i^δ-1/γδ T_i^δ-1≤∫_0^L_ie^-γ T_i^δ [1 -(1-u/T_i)^δ]du
    ≤1/γδ T_i^δ-1+2(δ-1)L_i/γδ T_i^δ.

This implies that

    -∑_i=1^n 2(δ-1)L_i/γδ T_i^δ≤∑_i=1^n 1/γδ T_i^δ-1 - ∑_i=1^n ∫_0^L_ie^-γ T_i^δ [1 -(1-u/T_i)^δ]du
    ≤∑_i=1^n e^-γδ L_i T_i^δ-1/γδ T_i^δ-1.

By Lemma <ref>, the left-hand side is 𝒪(1) as n↑∞.
Furthermore, by Lemma <ref>, ∑_i=1^n 1/(γδ T_i^δ-1)<∞ if δ>2.
Thus, to prove (<ref>),
it is enough to prove that

    ∑_i=1^n e^-γδ L_i T_i^δ-1/γδ T_i^δ-1 
    = 𝒪(1)     if δ>3/2
    
    o(n^3/2-δ(log n)^2)     if δ∈ (1,3/2],

almost surely as n↑∞.
If δ>2, this is implied by Lemma <ref>.
For δ∈ (1, 2], 
we first use the strong law of large numbers to write that T_i≥ i𝔼L/2 almost surely for all i large enough, and thus

    ∑_i=1^n e^-γδ L_i T_i^δ-1/γδ T_i^δ-1
    = 𝒪(∑_i=1^n e^-γδ L_i (i𝔼L/2)^δ-1/γδ (i𝔼L/2)^δ-1)
    = 𝒪(∑_i=1^n e^-γδ L_i (i𝔼L/2)^δ-1/i^δ-1),

almost surely as n↑∞.
First note that (M_n := ∑_i=1^n e^-γδ L_i (i𝔼L/2)^δ-1i^1-δ)_n≥ 0 is a martingale whose quadratic variation satisfies

    ⟨ M⟩_n
    = ∑_i=1^n 𝔼[e^-2γδ L_i (i𝔼L/2)^δ-1]/i^2(δ-1).

If δ>3/2, then 2(δ -1)>1 implying that

    ⟨ M⟩_n≤∑_i≥ 11/i^2(δ-1)<∞,

and thus that (M_n)_n≥ 0 converges almost surely as n↑∞. 
This, together with (<ref>), concludes the proof of (<ref>) in the case when δ∈ (3/2, 2].
For δ∈ (1, 3/2], we distinguish two cases:
First assume that lim_n↑∞⟨ M⟩_n<∞. In his case, M_n converges almost surely as n↑∞, which, together with (<ref>), implies that

    ∑_i=1^n e^-γδ L_i T_i^δ-1/γδ T_i^δ-1
    = 𝒪(1) = o(n^3/2-δ(log n)^2),

as claimed in (<ref>).
If lim_n↑∞⟨ M⟩_n = ∞, then by, e.g. <cit.>,
almost surely as n↑∞,

    M_n = o(√(⟨ M⟩_n)(log n)^2).

By (<ref>),

    ⟨ M⟩_n≤∑_i=1^n 1/i^2(δ-1) = 𝒪(n^3-2δ),

which gives that, almost surely as n↑∞, M_n = o(n^3/2-δ(log n)^2). Together with (<ref>), this implies that

    ∑_i=1^n e^-γδ L_i T_i^δ-1/γδ T_i^δ-1
    = o(n^3/2-δ(log n)^2),

which concludes the proof of (<ref>).

Note that (<ref>), together with (<ref>), implies (<ref>).
To conclude the proof of (<ref>), 
it only remains to prove that, for all δ>2, almost surely as n↑∞,

    ∑_i=1^n 1/γδ T_i^δ-1 
    = 𝒪(1)

This is true because T_i ∼ i𝔼L almost surely as i↑∞.


By Lemmas <ref> and <ref>, almost surely as n↑∞,
Φ(n) 
   = ∑_i=1^n (F_i1_i≺n-𝔼_L[F_i1_i≺n])+ ∑_i=1^n 𝔼_L[F_i1_i≺n]

   = 
T_n + 𝒪(1)      if δ>2

T_n - ∑_i=1^n 1/γδT_i^δ-1 + 𝒪(1)
     if δ∈(3/2, 2]

T_n - ∑_i=1^n 1/γδT_i^δ-1 + o(n^3/2-δ(logn)^2)
     if δ∈(1, 3/2],

as claimed in Proposition <ref>.


plain   



