# On a Model for the Storage of Files on a Hardware: Statistics at a Fixed Time and Asymptotic Regimes

Authors: Vincent Bansaye
Journal: Journal of Probability and Statistics
 (2009)

---

## Abstract

We consider a version in continuous time of the parking problem of Knuth. Files arrive following a Poisson point process and are stored on a hardware identified with the real line, in the closest free portions at the right of the arrival location. We specify the distribution of the space of unoccupied locations at a fixed time and give asymptotic regimes when the hardware is becoming full.


---

## Body

## 1. Introduction

We consider a version in continuous time of the original parking problem of Knuth. Knuth was interested in the storage of data on a hardware represented by a circle withn spots. Files arrive successively at locations chosen uniformly at random and independently among these n spots. They are stored in the first free spot at the right of their arrival point (at their arrival point if it is free). Initially Knuth worked on the hashing of data (see, e.g., [1–3]): he studied the distance between the spots where the files arrive and the spots where they are stored. Later Chassaing and Louchard [4] have described the evolution of the largest block of data in such coverings when n tends to infinity. They observed a phase transition at the stage where the hardware is almost full, which is related to the additive coalescent. Bertoin and Miermont [5] have extended these results to files of random sizes which arrive uniformly on the circle.We consider here a continuous time version of this model where the hardware is large and now identified with the real line. A file labelledi of length (or size) li arrives at time ti≥0 at location xi∈ℝ. The storage of this file uses the free portion of size li of the real line at the right of xi as close to xi as possible (see Figure 1). That is, it covers [xi,xi+li[ if this interval is free at time ti. Otherwise this file can be split into several parts which are then stored in the closest free portions at the right of the arrival location. We require uniformity of the location where the files arrive and identical distribution of their sizes. Thus we model the arrival of files by a Poisson point process (PPP): {(ti,xi,li):i∈ℕ} is a PPP with intensity dt⊗dx⊗ν(dl) on ℝ+×ℝ×ℝ+. We denote m:=∫0∞lν(dl) and assume m<∞. So m is the mean of the sum of sizes of files which arrive during a unit interval time on some interval with unit length.Figure 1
Arrival and storage of the5-file and representation of Y(5). The first four files have been stored without splitting and are represented by the black rectangles.We begin by constructing this random covering (Section2). The first questions which arise and are treated here concern statistics at a fixed time t for the set of occupied locations 𝒞(t). What is the distribution of the covering at a fixed time? At what time the hardware becomes full? What are the asymptotics of the covering at this saturation time? What is the length of the largest block on a part of the hardware?It is quite easy to see that the hardware becomes full at a deterministic time equal to1/m. In Section 3.1, we give some geometric properties of the distribution of the covering at a fixed time and we characterize this distribution by giving the joint distribution of the block of data straddling 0 and the free spaces on both sides of this block. The results given in this section will be useful for the problem of the dynamic of the covering considered in [6], where we investigate the evolution in time of a typical data block.Then, using this characterization, we determine in Sections3.2 and 3.3 the asymptotic regimes at the saturation time, which depend on the tail of ν, as in [4, 5, 7]. More precisely, we give the asymptotic of 𝒞(t) when t tends to 1/m (Theorem 3.6) and the asymptotic of 𝒞(t) restricted to [0,x] when x tends to infinity and t tends to 1/m (Theorem 3.10).We derive then the asymptotic behavior of the largest block of the hardware restricted to[0,x] when x tends to infinity and t tends to 1/m (Corollary 3.11). As Chassaing and Louchard in [4], we observe a phase transition. Results are stated in Section 3 and proved in Section 4.It is easy to check that for each fixed timet, 𝒞(t) does not depend on the order of arrival of files before time t. If ν is finite, we can view the files which arrive before time t as customers: the size of the file l becomes the service time of the customer and the location x where the file that arrives becomes the arrival time of the customer. We are then in the framework of the M/G/1 queue model in the stationary regime and the covering 𝒞(t) becomes the union of busy periods (see, e.g., [8, Chapter 3] or [9]). Thus, results of Sections 3.1 and 3.3 for finite ν follow easily from known results on M/G/1. When ν is infinite, results are similar though the busy cycle is not defined. Thus the approach is different and proving asymptotics on random sets requires results about Lévy processes (see the appendix) and regenerative sets. One motivation for the case when ν is infinite comes from storage models which appear by renormalization when both the number of customers who store files independently and the size of the hardware go to infinity. Moreover, as far as we know, the longest busy period and more generally asymptotic regimes on [0,x] when x tends to infinity and t tends to the saturation time (Section 3.4) have not been considered in the queuing model.


## 2. Preliminaries

In this section, we introduce some notations and recall some definitions we need to state the results. We also provide an elementary construction of the model studied in this paper.Throughout this paper, we use the classical notationδx for the Dirac mass at x and ℕ={1,2,…}.Ifℛ is a measurable subset of ℝ, we denote by |ℛ| its Lebesgue measure and by ℛcl its closure. For every x∈ℝ, we denote by ℛ-x the set {y-x:y∈ℛ} and
(2.1)gx(ℛ)=sup{y≤x:y∈ℛ},dx(ℛ)=inf{y>x:y∈ℛ}.
By convention, sup∅=-∞ and inf∅=∞.Topology of Matheron
IfI is a closed interval of ℝ, we denote by ℋ(I) the space of closed subsets of I. For all x,y∈ℝ and A⊂ℝ we define
(2.2)d(x,y)=1-e-|x-y|,d(x,A)=inf{d(x,y):y∈A},
and we endow ℋ(I) with the Hausdorff distance dH defined for all A,B∈ℋ(I) by
(2.3)dH(A,B)=max(supx∈Ad(x,B),supx∈Bd(x,A)).
The topology induced by this distance is the topology of Matheron [10]: a sequence ℛn in ℋ(I) converges to ℛ if and only if for each open set G and each compact K,
(2.4)ℛ∩G≠∅impliesℛn∩G≠∅fornlargeenough,ℛ∩K=∅impliesℛn∩K=∅fornlargeenough.
It is also the topology induced by the Hausdorff metric on a compact set using arctan(ℛ∪{-∞,∞}) or the Skorokhod metric using the class of “descending saw-tooth functions’’ (see [10, 11] for details).Tail ofν and Lévy Processes Indexed by ℝ
We give here several definitions which will be useful for the study of the asymptotic regimes. Following the notation in [5], we say that ν∈𝒟2+ if ν has a finite second moment m2:=∫0∞l2ν(dl). For α∈]1,2], we say that ν∈𝒟α whenever
(2.5)∃C>0suchthatν̅(x)~x→∞Cx-α.
Then, for α∈]1,2[, we put
(2.6)Cα:=(CΓ(2-α)m(α-1))1/α.
We denote by (Bz)z∈ℝ a two-sided Brownian motion; that is, (Bx)x≥0 and (B-x)x≥0 are independent standard Brownian motions. For α∈]1,2[, we denote by (σz(α))z∈ℝ a càdlàg process with independent and stationary increments such that (σx(α))x≥0 is a standard spectrally positive stable Lévy process with index α, that is,
(2.7)∀x≥0,λ≥0,𝔼(exp(-λσx(α)))=exp(xλα).
Finally, for all λ≥0 and α∈]1,2[, we introduce the following processes indexed by z∈ℝ:
(2.8)Yz2+,λ=-λz+m2mBz,Yz2,λ=-λz+CmBz,Yzα,λ=-λz+Cασz(α),
and their infimum process defined Ixα,λ:=inf{Yyα,λ:y≤x} for x∈ℝ.Construction of the Covering𝒞(t)
We give here an elementary construction of𝒞(t) and some basic identities we will use next. They are classical in queuing theory (see, e.g., [8]) and storage systems (see, e.g., [9]), and so we skip details and refer to the version [12] for complete proofs.We provide a deterministic construction of𝒞(t) for any fixed t. As 𝒞(t) does not depend on the order of arrival of files before t, this amounts to construct the covering 𝒞 associated with a given sequence of files labelled by i∈ℕ. The file labelled by i∈ℕ has size li and arrives after the files labelled by j≤i-1, at location xi on the real line. Files are stored following the process described in the Introduction and 𝒞 is the portion of line which is used for the storage.The covering𝒞 is the increasing union of the coverings 𝒞(n) (n≥0) obtained by considering only the first n files, that is,
(2.9)𝒞:=⋃n∈ℕ𝒞(n),
where 𝒞(n) can be defined in an elementary way by the following induction. Set 𝒞(0):=∅, and introduce the complementary set ℛ(n) of 𝒞(n) (i.e., the free space of the real line). Let yn+1=inf{y≥0,|ℛ(n)∩[xn+1,y[|=ln+1}, so yn+1 is the right-most point which is used for storing the (n+1)th file. Define then
(2.10)𝒞(n+1):=𝒞(n)∪[xn+1,yn+1[.
Now we introduce Rx(n) as the quantity of data which we have tried to store at the location x (successfully or not) when n files are stored. These data are the data fallen in [gx(ℛ(n)),x] which could not be stored in [gx(ℛ(n)),x]; so Rx(n) is defined by
(2.11)Rx(n):=-(x-gx(ℛ(n)))+∑i≤nxi∈[gx(ℛ(n)),x]li.
Note that in queuing systems, R(n) is the workload. This quantity can be expressed using the function Y(n), which sums the sizes of the files arrived at the left of a point x minus the drift term x. It is defined by Y0(n)=0 and
(2.12)Yb(n)-Ya(n)=-(b-a)+∑i≤nxi∈]a,b]lifora<b.
Introducing also its infimum function defined for x∈ℝ by Ix(n):=inf{Yy(n):y≤x}, we get the following expression, for every n≥1:
(2.13)R(n)=Y(n)-I(n).As a consequence, the covered set when the firstn files are stored is given by
(2.14)𝒞(n)={x∈ℝ:Y(n)-I(n)>0}.Finally, we introduce the functionY defined on ℝ by Y0=0 and
(2.15)Yb-Ya=-(b-a)+∑xi∈]a,b]lifora<b,
and its infimum I defined for x∈ℝ by
(2.16)Ix:=inf{Yy:y≤x}.
Assuming that the quantity of data arriving on a compact set is finite,
(2.17)∀L≥0,∑xi∈[-L,L]li<∞,
we can let n→∞ in (2.14). More precisely, the covering
(2.18)𝒞=⋃n∈ℕ𝒞(n)
is given by the following proposition (see [12, Section  2.1] for the proof).Proposition 2.1.
Assuming (2.17), one has the following.Iflimx→-∞Yx=+∞, then 𝒞={x∈ℝ:Yx-Ix>0}≠ℝ.Iflim infx→-∞Yx=-∞, then 𝒞={x∈ℝ:Yx-Ix>0}=ℝ.


## 3. Properties at a Fixed Time and Asymptotics Regimes

### 3.1. Statistics at a Fixed Time

Our purpose in this section is to specify the distribution of the covering𝒞(t) using Lévy processes. This characterization will be useful to prove asymptotics results (Theorems 3.6, 3.10 and Corollary 3.11) and for the dynamic results given in [6]. To that end, following the previous section, we consider the process (Yx(t))x∈ℝ associated to the PPP {(ti,li,xi):i∈ℕ} defined by
(3.1)Y0(t):=0;Yb(t)-Ya(t)=-(b-a)+∑ti≤txi∈]a,b]lifora<b,
which has independent and stationary increments, no negative jumps, and bounded variation. Introducing also its infimum process defined for x∈ℝ by
(3.2)Ix(t):=inf{Yy(t):y≤x},
we can give now a handy expression for the covering at a fixed time and obtain that the hardware becomes full at a deterministic time equal to 1/m, which is the random counterpart of Proposition 2.1 (see Section 4 for the proof).Proposition 3.1.
For everyt<1/m, one has 𝒞(t)={x∈ℝ:Yx(t)>Ix(t)}≠ℝ a.s. For every t≥1/m, one has 𝒞(t)=ℝ a.s.One can note that in queuing system,tm is the charge and 𝒞(t)≠ℝ⇔tm<1 is the standard claim of stability for tm<1, for finite ν.To specify the distribution of𝒞(t), it is equivalent and more convenient to describe the distribution of its complementary set, denoted by ℛ(t), which corresponds to the free space of the hardware at time t. By the previous proposition, there is the following identity:
(3.3)ℛ(t)={x∈ℝ:Yx(t)=Ix(t)}a.s.
We begin by giving some geometric properties of this set, which are classical for finite ν for storage systems (see [13]) and queuing theory (see [14]).Proposition 3.2.
For everyt≥0, ℛ(t) is stationary, its closure is symmetric in distribution, and it enjoys the regeneration property: For every x∈ℝ, (ℛ(t)-dx(ℛ(t)))∩[0,∞[ is independent of ℛ(t)∩]-∞,x] and is distributed as (ℛ(t)-d0(ℛ(t)))∩[0,∞[.
Moreover for everyx∈ℝ, ℙ(x∈𝒞(t))=min(1,mt).Stationarity is plain from the construction of the covering and regeneration property is a direct consequence of Lemma4.1 given in the next section. Symmetry is then a consequence of [25, Lemma  6.5] or [26, Corollary  7.19]. Computation of ℙ(x∈𝒞(t)) can be then derived from [15, Theorem  1]. See [12, Section  3.1] for the complete proof.Even though for each fixedt the distribution of ℛ(t)cl is symmetric, the processes (ℛ(t)cl:t∈[0,1/m]) and (-ℛ(t)cl:t∈[0,1/m]) are quite different. For example, we shall observe in [6] that the left extremity of the data block straddling 0 is a Markov process but the right extremity is not.We want now to characterize the distribution of the free spaceℛ(t). For this purpose, we need some notation. The drift of the Lévy process (Yx(t))x≥0 is equal to -1, its Lévy measure is equal to tν, and its Laplace exponent Ψ(t) is then given by (see the appendix for background on Lévy processes)
(3.4)Ψ(t)(ρ):=-ρ+∫0∞(1-e-ρx)tν(dx).
For sake of simplicity, we write, recalling (2.1),
(3.5)g(t):=g0(ℛ(t)),d(t)=d0(ℛ(t)),l(t)=d(t)-g(t),
which are, respectively, the left extremity, the right extremity, and the length of the data block straddling 0, B0(t). Note that g(t)=d(t)=0 if B0(t)=∅.We work withℛ, a subset of ℝ of the form ⨆n∈ℕ[an,bn[, and we denote by ℛ̃:=⨆n∈ℕ[-bn,-an[ the symmetrical of ℛ with respect to 0 closed at the left, open at the right. We consider the positive part (resp., negative part) of ℛ defined by
(3.6)ℛ→:=(ℛ-d0(ℛ))∩[0,∞]=⨆n∈ℕ:an≥d0(ℛ)[an-d0(ℛ),bn-d0(ℛ)[,ℛ←:=ℛ̃→=⨆n∈ℕ:bn≤g0(ℛ)[g0(ℛ)-bn,g0(ℛ)-an[.Example 3.3.
For a givenℛ represented by the dotted lines, we give below ℛ→ and ℛ←, which are also represented by dotted lines. Moreover the endpoints of the data blocks containing 0 are denoted by g0 and d0(see Figure 2).Figure 2Thusℛ(t)→ (resp., ℛ(t)←) is the free space at the right of B0(t) (resp., at the left of B0(t), turned over, closed at the left and open at the right). We have then the identity
(3.7)ℛ(t)=(d(t)+ℛ(t)→)⊔(-g(t)+ℛ(t)←̃).
Introducing also the processes (τ→x(t))x≥0 and (τ←x(t))x≥0 defined by
(3.8)τ→x(t):=inf{y≥0:|ℛ(t)→∩[0,y]|>x},τ←x(t):=inf{y≥0:|ℛ(t)←∩[0,y]|>x}
enables us to describe ℛ(t) in the following way (see Section 4 for the proof).Proposition 3.4.
(i) The random setsℛ(t)→ and ℛ(t)← are independent, identically distributed, and independent of (g(t),d(t)).
(ii)ℛ(t)→ and ℛ(t)← are the range of the subordinators τ→(t) and τ←(t), respectively, whose Laplace exponent κ(t) is the inverse function of -Ψ(t).
(iii) The distribution of(g(t),d(t)) is specified by
(3.9)(g(t),d(t))=(-Ul(t),(1-U)l(t)),ℙ(l(t)∈dx)=(1-mt)(δ0(dx)+1{x>0}xΠ(t)(dx)),
where U is an uniform random variable on [0,1] independent of l(t) and Π(t) is the Lévy measure of κ(t).Remark 3.5.
Such results are classical for regenerative sets (see, e.g., [13, 17, 18]). But we need this particular characterization and expressions given in the proof in the next section for forthcoming results.


### 3.2. Asymptotics at Saturation of the Hardware

We focus now on the asymptotic behavior ofℛ(t) when t tends to 1/m, that is, when the hardware is becoming full. First, note that if ν has a finite second moment, then
(3.10)𝔼(l(t))=∫0∞l2ν(dl)(1-mt)2.
Thus we may expect that if ν has a finite second moment, then (1-mt)2l(t) should converge in distribution as t tends to 1/m. Indeed, in the particular case ν=δ1 or in the conditions of [4, Corollary  2.4], we have an expression of Π(t)(dx) and we can prove that (1-mt)2l(t) does converge in distribution to a gamma variable.More generally, we shall prove that the rescaled free space(1-mt)2ℛ(t) converges in distribution as t tends to 1/m. To that end, we need to prove that the process (Y(1-mt)-2x(t))x∈ℝ converges after suitable rescaling to a random process. Thanks to (3.3), (1-mt)2ℛ(t) should then converge to the set of points where this limiting process coincides with its infimum process. We shall also handle the case where ν has an infinite second moment and find the correct normalization, which depends on the tail of ν. Proofs are close to those of Section 3.3 and given simultaneously in Section 4.In queuing systems, asymptotics at saturation are known as heavy traffic approximation (ρ=tm→1), which depend similarly on the tail of ν. And for ν finite, results given here could be directly derived from results in queuing theory (see [8, Section III.7.2] or [14] if ν has a second moment order and [7] for heavy tail of ν). The main difference is that ν can be infinite in this paper. Then the busy cycle is not defined and we consider here the whole random set of occupied locations.To state the main result, we introduce now the following functions defined for everyt∈[0,1/m[ and α∈]1,2[ by
(3.11)ϵ2+(t)=(1-mt)2,ϵ2(t)=2(1-mt)2-log((1-mt)),ϵα(t)=(1-mt)α/(α-1).Recalling Notations of Section2, we have then the following weak convergence result for the Matheron topology.Theorem 3.6.
Ifν∈𝒟α(α∈]1,2]∪{2+}), then ϵα(t)·ℛ(t)cl converges weakly in ℋ(ℝ) as t tends to 1/m to {x∈ℝ:Yxα,1=Ixα,1}cl.First we prove the convergence of the Laplace exponentΨ(t) after suitable rescaling as t tends to 1/m, which ensures the convergence of the Lévy process Y(t) after suitable rescaling (see Lemma 4.2). These convergences will not a priori entail the convergence of the random set ϵα(t)·ℛcl(t) since they do not entail the convergence of excursions. Nevertheless, they will entail the convergence of κ(t) since κ(t)∘(-Ψ(t))=Id (Lemma 4.4). Then we get the convergence of τ(t) as t tends to infinity and thus of its range ϵα(t)·ℛcl(t).Remark 3.7.
More generally, as in queuing theory and [5], we can generalize these results for regularly varying functions ν̅. If ν̅ is regularly varying at infinity with index -α∈]-1,-2[, then we have the following weak convergence in ℋ(ℝ):
(3.12)z-1ℛ((1-zν̅(z))m)cl⇒z→∞{x∈ℝ:Yxα,1=Ixα,1}clwithC=1.
For instance, the case ν̅(x)~x→∞cx-αlog(x)β with (α,β,c)∈]1,2[×ℝ×ℝ+* leads to
(3.13)((1-mt)log(11-mt)-β)α/(α-1)ℛ(t)cl⇒t→1/m{x∈ℝ:Yxα,1=Ixα,1}clwithC=c(α-1)β.
If ν̅ is regularly varying at infinity with index -2, there are many cases to consider.We get then the asymptotic of(g(t),d(t)).Corollary 3.8.
Ifν∈𝒟α(α∈]1,2]∪{2+}), then ϵα(t)·(g(t),d(t)) converges weakly as t tends to 1/m to (sup{x≤0:Yxα,1=I0α,1},inf{x≥0:Yxα,1=I0α,1}).
Ifν∈𝒟2+ (resp., 𝒟2), ϵα(t)·l(t) converges weakly to a gamma variable with parameter (1/2,m/(4m2)) (resp., (1/2,m/4)).Remark 3.9.
The density of data blocks of sizedx in ϵα(t)·ℛ(t)cl is equal to (mt/(1-mt))Π(t)(dx). By the previous theorem or corollary, this density converges weakly as t tends to 1/m to the density of data block of size dx of the limit covering {x∈ℝ:Yxα,1=Ixα,1}cl. This limit density, denoted by Πα,1(dx), can be computed explicitly in the cases ν∈𝒟α(α∈{2,2+}), thanks to the last corollary:
(3.14)Π2+,1(dx)=m4πm2x3exp(-m4m2x),Π2,1(dx)=m4πx3exp(-m4x).
Note that this is also the Lévy measure of the limit covering {x∈ℝ:Yxα,1=Ixα,1}cl.


### 3.3. Asymptotic Regime on a Large Part of the Hardware

Here we look at the set of occupied locations𝒞(t) in a window of size x. We consider the asymptotics of 𝒞(t)∩[0,x] when x tends to infinity and t tends to the saturation time. As far as we know, results given here are new even when ν is finite. We introduce the following functions defined for all x∈ℝ+* and α∈]1,2[ by
(3.15)f2+(x)=1x,f2(x)=log(x)x,fα(x)=x1/α-1.
And we have the following asymptotic regime (see Section 4 for the proof).Theorem 3.10.
Ifν∈𝒟α(α∈]1,2]∪{2+}), x tends to infinity and t to 1/m such that 1-mt~λfα(x) with λ>0, then x-1(ℛ(t)cl∩[0,x]) converges weakly in ℋ([0,1]) to {z∈[0,1]:Yzα,λ=Izα,λ}cl.Thus as in [4], we observe a phase transition of the size of largest block of data in [0,x] as x→∞ according to the rate of filling of the hardware. More precisely, denoting B1(x,t)=|I1(x,t)| where (Ij(x,t))j≥1 is the sequence of component intervals of 𝒞(t)∩[0,x] ranked by decreasing order of size, we have the following.Corollary 3.11.
Letν∈𝒟α(α∈]1,2]∪{2+}), x tends to infinity and t to 1/m. (i)
If1-mt~λfα(x) with λ>0, then B1(x,t)/x converges in distribution to the largest length of excursion of (Yzα,λ-Izα,λ)z∈[0,1].(ii)
Iffα(x)=o(1-mt), then B1(x,t)/x→ℙ0.(iii)
If1-mt=o(fα(x)), then B1(x,t)/x→ℙ1.The phase transition occurs at timet such that 1-mt~λfα(x) with λ>0. The more data arrive in small files (i.e., the faster ν̅(x) tends to zero as x tends to infinity), the later the phase transition occurs. In [4, 5], the hardware is a circle and processes required for asymptotics are the bridges of the processes used here. A consequence is that in our model, B1(t,x)/x tends to zero or one with a positive probability at phase transition, which is not the case for the parking problem in [4, 5]. More precisely, denoting by Bα,λ the law of the largest length of excursion of (Yxα,λ-Ixα,λ)x∈[0,1], we have
(3.16)∀(λ,α)∈ℝ+*×]1,2[∪{2+},ℙ(Bα,λ=0)>0,ℙ(Bα,λ=1)>0.


### 3.4. Observations

We give here some complementary results about the distribution of the set of occupied locations at a fixed time and about the storage process.We have for everyρ≥0 (use (A.10)),
(3.17)κ(t)(ρ)=ρ+∫0∞(1-e-ρx)Π(t)(dx),
and using (A.11),
(3.18)Π̅(t)(0)=tν̅(0),∫0∞xΠ(t)(dx)=mt1-mt.
Using (A.9), we have also the following identity of measures on [0,∞[×[0,∞[(3.19)xℙ(τ→l(t)∈dx)dl=lℙ(-Yx(t)∈dl)dx.We can give the distribution ofthe extremities ofB0:
(3.20)ℙ(-g(t)∈dx)=ℙ(d(t)∈dx)=(1-mt)(δ0(dx)+1{x>0}Π̅(t)(x)dx).
Writing -g(t)=γ(t) (see (4.9) and (4.10)) and using the identity of fluctuation (A.17) gives an other expression for the Laplace transform of g(t). For all t∈[0,1/m[ and λ≥0, we have
(3.21)𝔼(exp(λg(t)))=exp(∫0∞(e-λx-1)x-1ℙ(Yx(t)>0)dx).
As a consequence, we see that the law of g(t) is infinitively divisible. Moreover this expression will give the generating triplet of the additive process (g(t))t∈[0,1/m[ [6, Theorem  2, Section  4].We can also estimatethe number of data blocks on the hardware. If ν has a finite mass, we write Nx(t) as the number of data blocks of the hardware restricted to [-x,x] at time t. This quantity has a deterministic asymptotic as x tends to infinity which is maximum at time 1/(2m). And the number of blocks of the hardware reaches a.s. its maximal at time 1/(2m). More precisely, we have the following.Proposition 3.12.
Ifν̅(0)<∞, then for every t∈[0,1/m[,
(3.22)limx→∞Nx(t)2x=ν̅(0)t(1-mt)a.s.Finally, we can describe herethe hashing of data. We recall that a file labeled by i is stored at location xi. In the hashing problem, one is interested by the location where the file i is stored knowing xi. By stationarity, we can take xi=0 and consider a file of size l which we store at time t at location 0 on the hardware whose free space is equal to ℛ(t). The first point (resp., the last point) of the hardware occupied for the storage of this file is equal to d(t) (resp., to d(t)+τ→l(t)). This gives the distribution of the extremities of the portion of the hardware used for the storage of a file.


### 3.5. Examples

Let us now consider three explicit examples.(1) The basic example is when ν=δ1 (all files have the same unit size as in the original parking problem in [4]). Then for all x∈ℝ+ and n∈ℕ,
(3.23)ℙ(Yx(t)+x=n)=e-tx(tx)nn!,ℙ(τ→x(t)=x+n)=xx+ne-t(x+n)(t(n+x))nn!,
where the second identity follows from integrating (3.19). Then,
(3.24)Π(t)(n)=(tn)nn.n!e-tn,
and l(t) follows a size-biased Borel law:
(3.25)ℙ(l(t)=n)=(1-t)(tn)nn!e-tn.(2) Another example where calculus can be made explicitly is the gamma case when ν(dl)=1{l≥0}l-1e-ldl. Note that ν̅(0)=∞ and m=1. Then, for every x∈ℝ+,
(3.26)ℙ(Yx(t)∈dz)=1[-x,∞[(z)Γ(tx)-1e-(z+x)(z+x)tx-1dz,ℙ(τ→x(t)∈dz)=1[x,∞[(z)x(zΓ(tz))-1e-(z-x)(z-x)tz-1dz.
Further
(3.27)Π(t)(dz)=(zΓ(tz))-1e-zztz-1dz,ℙ(l(t)∈dx)=(1-t)(δ0(dx)+Γ(tz)-1e-xxtx-1dx).(3) For the exponential distribution ν(dl)=1{l≥0}e-ldl, we can get
(3.28)Ψ(t)(λ)=λ(-1+tλ+1),κ(t)(λ)=λ+t-1+(λ+t-1)2+4λ2.


## 3.1. Statistics at a Fixed Time

Our purpose in this section is to specify the distribution of the covering𝒞(t) using Lévy processes. This characterization will be useful to prove asymptotics results (Theorems 3.6, 3.10 and Corollary 3.11) and for the dynamic results given in [6]. To that end, following the previous section, we consider the process (Yx(t))x∈ℝ associated to the PPP {(ti,li,xi):i∈ℕ} defined by
(3.1)Y0(t):=0;Yb(t)-Ya(t)=-(b-a)+∑ti≤txi∈]a,b]lifora<b,
which has independent and stationary increments, no negative jumps, and bounded variation. Introducing also its infimum process defined for x∈ℝ by
(3.2)Ix(t):=inf{Yy(t):y≤x},
we can give now a handy expression for the covering at a fixed time and obtain that the hardware becomes full at a deterministic time equal to 1/m, which is the random counterpart of Proposition 2.1 (see Section 4 for the proof).Proposition 3.1.
For everyt<1/m, one has 𝒞(t)={x∈ℝ:Yx(t)>Ix(t)}≠ℝ a.s. For every t≥1/m, one has 𝒞(t)=ℝ a.s.One can note that in queuing system,tm is the charge and 𝒞(t)≠ℝ⇔tm<1 is the standard claim of stability for tm<1, for finite ν.To specify the distribution of𝒞(t), it is equivalent and more convenient to describe the distribution of its complementary set, denoted by ℛ(t), which corresponds to the free space of the hardware at time t. By the previous proposition, there is the following identity:
(3.3)ℛ(t)={x∈ℝ:Yx(t)=Ix(t)}a.s.
We begin by giving some geometric properties of this set, which are classical for finite ν for storage systems (see [13]) and queuing theory (see [14]).Proposition 3.2.
For everyt≥0, ℛ(t) is stationary, its closure is symmetric in distribution, and it enjoys the regeneration property: For every x∈ℝ, (ℛ(t)-dx(ℛ(t)))∩[0,∞[ is independent of ℛ(t)∩]-∞,x] and is distributed as (ℛ(t)-d0(ℛ(t)))∩[0,∞[.
Moreover for everyx∈ℝ, ℙ(x∈𝒞(t))=min(1,mt).Stationarity is plain from the construction of the covering and regeneration property is a direct consequence of Lemma4.1 given in the next section. Symmetry is then a consequence of [25, Lemma  6.5] or [26, Corollary  7.19]. Computation of ℙ(x∈𝒞(t)) can be then derived from [15, Theorem  1]. See [12, Section  3.1] for the complete proof.Even though for each fixedt the distribution of ℛ(t)cl is symmetric, the processes (ℛ(t)cl:t∈[0,1/m]) and (-ℛ(t)cl:t∈[0,1/m]) are quite different. For example, we shall observe in [6] that the left extremity of the data block straddling 0 is a Markov process but the right extremity is not.We want now to characterize the distribution of the free spaceℛ(t). For this purpose, we need some notation. The drift of the Lévy process (Yx(t))x≥0 is equal to -1, its Lévy measure is equal to tν, and its Laplace exponent Ψ(t) is then given by (see the appendix for background on Lévy processes)
(3.4)Ψ(t)(ρ):=-ρ+∫0∞(1-e-ρx)tν(dx).
For sake of simplicity, we write, recalling (2.1),
(3.5)g(t):=g0(ℛ(t)),d(t)=d0(ℛ(t)),l(t)=d(t)-g(t),
which are, respectively, the left extremity, the right extremity, and the length of the data block straddling 0, B0(t). Note that g(t)=d(t)=0 if B0(t)=∅.We work withℛ, a subset of ℝ of the form ⨆n∈ℕ[an,bn[, and we denote by ℛ̃:=⨆n∈ℕ[-bn,-an[ the symmetrical of ℛ with respect to 0 closed at the left, open at the right. We consider the positive part (resp., negative part) of ℛ defined by
(3.6)ℛ→:=(ℛ-d0(ℛ))∩[0,∞]=⨆n∈ℕ:an≥d0(ℛ)[an-d0(ℛ),bn-d0(ℛ)[,ℛ←:=ℛ̃→=⨆n∈ℕ:bn≤g0(ℛ)[g0(ℛ)-bn,g0(ℛ)-an[.Example 3.3.
For a givenℛ represented by the dotted lines, we give below ℛ→ and ℛ←, which are also represented by dotted lines. Moreover the endpoints of the data blocks containing 0 are denoted by g0 and d0(see Figure 2).Figure 2Thusℛ(t)→ (resp., ℛ(t)←) is the free space at the right of B0(t) (resp., at the left of B0(t), turned over, closed at the left and open at the right). We have then the identity
(3.7)ℛ(t)=(d(t)+ℛ(t)→)⊔(-g(t)+ℛ(t)←̃).
Introducing also the processes (τ→x(t))x≥0 and (τ←x(t))x≥0 defined by
(3.8)τ→x(t):=inf{y≥0:|ℛ(t)→∩[0,y]|>x},τ←x(t):=inf{y≥0:|ℛ(t)←∩[0,y]|>x}
enables us to describe ℛ(t) in the following way (see Section 4 for the proof).Proposition 3.4.
(i) The random setsℛ(t)→ and ℛ(t)← are independent, identically distributed, and independent of (g(t),d(t)).
(ii)ℛ(t)→ and ℛ(t)← are the range of the subordinators τ→(t) and τ←(t), respectively, whose Laplace exponent κ(t) is the inverse function of -Ψ(t).
(iii) The distribution of(g(t),d(t)) is specified by
(3.9)(g(t),d(t))=(-Ul(t),(1-U)l(t)),ℙ(l(t)∈dx)=(1-mt)(δ0(dx)+1{x>0}xΠ(t)(dx)),
where U is an uniform random variable on [0,1] independent of l(t) and Π(t) is the Lévy measure of κ(t).Remark 3.5.
Such results are classical for regenerative sets (see, e.g., [13, 17, 18]). But we need this particular characterization and expressions given in the proof in the next section for forthcoming results.


## 3.2. Asymptotics at Saturation of the Hardware

We focus now on the asymptotic behavior ofℛ(t) when t tends to 1/m, that is, when the hardware is becoming full. First, note that if ν has a finite second moment, then
(3.10)𝔼(l(t))=∫0∞l2ν(dl)(1-mt)2.
Thus we may expect that if ν has a finite second moment, then (1-mt)2l(t) should converge in distribution as t tends to 1/m. Indeed, in the particular case ν=δ1 or in the conditions of [4, Corollary  2.4], we have an expression of Π(t)(dx) and we can prove that (1-mt)2l(t) does converge in distribution to a gamma variable.More generally, we shall prove that the rescaled free space(1-mt)2ℛ(t) converges in distribution as t tends to 1/m. To that end, we need to prove that the process (Y(1-mt)-2x(t))x∈ℝ converges after suitable rescaling to a random process. Thanks to (3.3), (1-mt)2ℛ(t) should then converge to the set of points where this limiting process coincides with its infimum process. We shall also handle the case where ν has an infinite second moment and find the correct normalization, which depends on the tail of ν. Proofs are close to those of Section 3.3 and given simultaneously in Section 4.In queuing systems, asymptotics at saturation are known as heavy traffic approximation (ρ=tm→1), which depend similarly on the tail of ν. And for ν finite, results given here could be directly derived from results in queuing theory (see [8, Section III.7.2] or [14] if ν has a second moment order and [7] for heavy tail of ν). The main difference is that ν can be infinite in this paper. Then the busy cycle is not defined and we consider here the whole random set of occupied locations.To state the main result, we introduce now the following functions defined for everyt∈[0,1/m[ and α∈]1,2[ by
(3.11)ϵ2+(t)=(1-mt)2,ϵ2(t)=2(1-mt)2-log((1-mt)),ϵα(t)=(1-mt)α/(α-1).Recalling Notations of Section2, we have then the following weak convergence result for the Matheron topology.Theorem 3.6.
Ifν∈𝒟α(α∈]1,2]∪{2+}), then ϵα(t)·ℛ(t)cl converges weakly in ℋ(ℝ) as t tends to 1/m to {x∈ℝ:Yxα,1=Ixα,1}cl.First we prove the convergence of the Laplace exponentΨ(t) after suitable rescaling as t tends to 1/m, which ensures the convergence of the Lévy process Y(t) after suitable rescaling (see Lemma 4.2). These convergences will not a priori entail the convergence of the random set ϵα(t)·ℛcl(t) since they do not entail the convergence of excursions. Nevertheless, they will entail the convergence of κ(t) since κ(t)∘(-Ψ(t))=Id (Lemma 4.4). Then we get the convergence of τ(t) as t tends to infinity and thus of its range ϵα(t)·ℛcl(t).Remark 3.7.
More generally, as in queuing theory and [5], we can generalize these results for regularly varying functions ν̅. If ν̅ is regularly varying at infinity with index -α∈]-1,-2[, then we have the following weak convergence in ℋ(ℝ):
(3.12)z-1ℛ((1-zν̅(z))m)cl⇒z→∞{x∈ℝ:Yxα,1=Ixα,1}clwithC=1.
For instance, the case ν̅(x)~x→∞cx-αlog(x)β with (α,β,c)∈]1,2[×ℝ×ℝ+* leads to
(3.13)((1-mt)log(11-mt)-β)α/(α-1)ℛ(t)cl⇒t→1/m{x∈ℝ:Yxα,1=Ixα,1}clwithC=c(α-1)β.
If ν̅ is regularly varying at infinity with index -2, there are many cases to consider.We get then the asymptotic of(g(t),d(t)).Corollary 3.8.
Ifν∈𝒟α(α∈]1,2]∪{2+}), then ϵα(t)·(g(t),d(t)) converges weakly as t tends to 1/m to (sup{x≤0:Yxα,1=I0α,1},inf{x≥0:Yxα,1=I0α,1}).
Ifν∈𝒟2+ (resp., 𝒟2), ϵα(t)·l(t) converges weakly to a gamma variable with parameter (1/2,m/(4m2)) (resp., (1/2,m/4)).Remark 3.9.
The density of data blocks of sizedx in ϵα(t)·ℛ(t)cl is equal to (mt/(1-mt))Π(t)(dx). By the previous theorem or corollary, this density converges weakly as t tends to 1/m to the density of data block of size dx of the limit covering {x∈ℝ:Yxα,1=Ixα,1}cl. This limit density, denoted by Πα,1(dx), can be computed explicitly in the cases ν∈𝒟α(α∈{2,2+}), thanks to the last corollary:
(3.14)Π2+,1(dx)=m4πm2x3exp(-m4m2x),Π2,1(dx)=m4πx3exp(-m4x).
Note that this is also the Lévy measure of the limit covering {x∈ℝ:Yxα,1=Ixα,1}cl.


## 3.3. Asymptotic Regime on a Large Part of the Hardware

Here we look at the set of occupied locations𝒞(t) in a window of size x. We consider the asymptotics of 𝒞(t)∩[0,x] when x tends to infinity and t tends to the saturation time. As far as we know, results given here are new even when ν is finite. We introduce the following functions defined for all x∈ℝ+* and α∈]1,2[ by
(3.15)f2+(x)=1x,f2(x)=log(x)x,fα(x)=x1/α-1.
And we have the following asymptotic regime (see Section 4 for the proof).Theorem 3.10.
Ifν∈𝒟α(α∈]1,2]∪{2+}), x tends to infinity and t to 1/m such that 1-mt~λfα(x) with λ>0, then x-1(ℛ(t)cl∩[0,x]) converges weakly in ℋ([0,1]) to {z∈[0,1]:Yzα,λ=Izα,λ}cl.Thus as in [4], we observe a phase transition of the size of largest block of data in [0,x] as x→∞ according to the rate of filling of the hardware. More precisely, denoting B1(x,t)=|I1(x,t)| where (Ij(x,t))j≥1 is the sequence of component intervals of 𝒞(t)∩[0,x] ranked by decreasing order of size, we have the following.Corollary 3.11.
Letν∈𝒟α(α∈]1,2]∪{2+}), x tends to infinity and t to 1/m. (i)
If1-mt~λfα(x) with λ>0, then B1(x,t)/x converges in distribution to the largest length of excursion of (Yzα,λ-Izα,λ)z∈[0,1].(ii)
Iffα(x)=o(1-mt), then B1(x,t)/x→ℙ0.(iii)
If1-mt=o(fα(x)), then B1(x,t)/x→ℙ1.The phase transition occurs at timet such that 1-mt~λfα(x) with λ>0. The more data arrive in small files (i.e., the faster ν̅(x) tends to zero as x tends to infinity), the later the phase transition occurs. In [4, 5], the hardware is a circle and processes required for asymptotics are the bridges of the processes used here. A consequence is that in our model, B1(t,x)/x tends to zero or one with a positive probability at phase transition, which is not the case for the parking problem in [4, 5]. More precisely, denoting by Bα,λ the law of the largest length of excursion of (Yxα,λ-Ixα,λ)x∈[0,1], we have
(3.16)∀(λ,α)∈ℝ+*×]1,2[∪{2+},ℙ(Bα,λ=0)>0,ℙ(Bα,λ=1)>0.


## 3.4. Observations

We give here some complementary results about the distribution of the set of occupied locations at a fixed time and about the storage process.We have for everyρ≥0 (use (A.10)),
(3.17)κ(t)(ρ)=ρ+∫0∞(1-e-ρx)Π(t)(dx),
and using (A.11),
(3.18)Π̅(t)(0)=tν̅(0),∫0∞xΠ(t)(dx)=mt1-mt.
Using (A.9), we have also the following identity of measures on [0,∞[×[0,∞[(3.19)xℙ(τ→l(t)∈dx)dl=lℙ(-Yx(t)∈dl)dx.We can give the distribution ofthe extremities ofB0:
(3.20)ℙ(-g(t)∈dx)=ℙ(d(t)∈dx)=(1-mt)(δ0(dx)+1{x>0}Π̅(t)(x)dx).
Writing -g(t)=γ(t) (see (4.9) and (4.10)) and using the identity of fluctuation (A.17) gives an other expression for the Laplace transform of g(t). For all t∈[0,1/m[ and λ≥0, we have
(3.21)𝔼(exp(λg(t)))=exp(∫0∞(e-λx-1)x-1ℙ(Yx(t)>0)dx).
As a consequence, we see that the law of g(t) is infinitively divisible. Moreover this expression will give the generating triplet of the additive process (g(t))t∈[0,1/m[ [6, Theorem  2, Section  4].We can also estimatethe number of data blocks on the hardware. If ν has a finite mass, we write Nx(t) as the number of data blocks of the hardware restricted to [-x,x] at time t. This quantity has a deterministic asymptotic as x tends to infinity which is maximum at time 1/(2m). And the number of blocks of the hardware reaches a.s. its maximal at time 1/(2m). More precisely, we have the following.Proposition 3.12.
Ifν̅(0)<∞, then for every t∈[0,1/m[,
(3.22)limx→∞Nx(t)2x=ν̅(0)t(1-mt)a.s.Finally, we can describe herethe hashing of data. We recall that a file labeled by i is stored at location xi. In the hashing problem, one is interested by the location where the file i is stored knowing xi. By stationarity, we can take xi=0 and consider a file of size l which we store at time t at location 0 on the hardware whose free space is equal to ℛ(t). The first point (resp., the last point) of the hardware occupied for the storage of this file is equal to d(t) (resp., to d(t)+τ→l(t)). This gives the distribution of the extremities of the portion of the hardware used for the storage of a file.


## 3.5. Examples

Let us now consider three explicit examples.(1) The basic example is when ν=δ1 (all files have the same unit size as in the original parking problem in [4]). Then for all x∈ℝ+ and n∈ℕ,
(3.23)ℙ(Yx(t)+x=n)=e-tx(tx)nn!,ℙ(τ→x(t)=x+n)=xx+ne-t(x+n)(t(n+x))nn!,
where the second identity follows from integrating (3.19). Then,
(3.24)Π(t)(n)=(tn)nn.n!e-tn,
and l(t) follows a size-biased Borel law:
(3.25)ℙ(l(t)=n)=(1-t)(tn)nn!e-tn.(2) Another example where calculus can be made explicitly is the gamma case when ν(dl)=1{l≥0}l-1e-ldl. Note that ν̅(0)=∞ and m=1. Then, for every x∈ℝ+,
(3.26)ℙ(Yx(t)∈dz)=1[-x,∞[(z)Γ(tx)-1e-(z+x)(z+x)tx-1dz,ℙ(τ→x(t)∈dz)=1[x,∞[(z)x(zΓ(tz))-1e-(z-x)(z-x)tz-1dz.
Further
(3.27)Π(t)(dz)=(zΓ(tz))-1e-zztz-1dz,ℙ(l(t)∈dx)=(1-t)(δ0(dx)+Γ(tz)-1e-xxtx-1dx).(3) For the exponential distribution ν(dl)=1{l≥0}e-ldl, we can get
(3.28)Ψ(t)(λ)=λ(-1+tλ+1),κ(t)(λ)=λ+t-1+(λ+t-1)2+4λ2.


## 4. Proofs

In this section, we provide rigorous arguments for the original results which have been stated in Section3.Proof of Proposition3.1.
Firstm<∞ entails that for all L≥0, ∑ti≤t,xi∈[-L,L]li<∞ a.s. and condition (A.7) is satisfied a.s. Then, by Proposition 2.1,
(4.1)𝒞(t)={x∈ℝ:Yx(t)-Ix(t)>0}a.s.
(i) Ift<1/m, then 𝔼(Y-1(t))=1-mt>0 and the càdlàg version of (Y(-x)-(t))x≥0 is a Lévy process. So we have (see [20, Corollary  2, page 190])
(4.2)Yx(t)→x→-∞∞a.s.
Then Proposition 2.1 ensures that for every t<1/m, 𝒞(t)={x∈ℝ:Yx(t)>Ix(t)}≠ℝ a.s.
(ii) Ift≥1/m, then 𝔼(Y-1(t))≤0 ensures (see [20, Corollary  2, page 190]) that
(4.3)Yx(t)→x→-∞-∞a.s.or(Yx(t))x≤0oscillatesa.s.in-∞.
Similarly, we get that for every t≥1/m, 𝒞(t)=ℝ a.s.For the forthcoming proofs, we fixt∈[0,1/m[, which is omitted from the notation of processes for the sake of simplicity.To prove the regeneration property and characterize the Laplace exponent ofτ→, we need to establish first a regeneration property at the right extremities of the data blocks. In that view, we consider, for every x≥0, the files arrived at the left/at the right of x before time t:
(4.4)𝒫x:={(ti,xi,li):ti≤t,xi≤x},𝒫x:={(ti,xi-x,li):ti≤t,xi>x}.Lemma 4.1.
For allx≥0, 𝒫dx(ℛ(t)) is independent of 𝒫dx(ℛ(t)) and distributed as 𝒫0.Proof.
The simple Markov property for PPP states that, for everyx∈ℝ, 𝒫x is independent of 𝒫x and distributed as 𝒫0. Clearly this extends to simple stopping times in the filtration σ(𝒫x)x∈ℝ and further to any stopping time in this filtration using the classical argument of approximation of stopping times by a decreasing sequence of simple stopping times (see also [21]). As dx(ℛ(t)) is a stopping time in this filtration, 𝒫dx(ℛ(t)) is independent of 𝒫dx(ℛ(t)) and distributed as 𝒫0.Using well-known results on Lévy processes, which we recall in Section4, we can prove Proposition 3.4.Proof of Proposition3.4.
(i) By symmetry,ℛ(t)cl, ℛ(t)→, and ℛ(t)← are identically distributed. The regeneration property ensures that ℛ(t)→ is independent of (ℛ(t)←,g(t),d(t)). By symmetry, ℛ(t)← is independent of (g(t),d(t),ℛ(t)→). So ℛ(t)→, ℛ(t)←, and (g(t),d(t)) are independent.
(ii) Asℛ→(t) is a.s. the union of intervals of the form [a,b[, then x→|ℛ(t)∩[0,x]| increases at x∈ℛ→(t). So, for every x≥0,
(4.5)τ→|ℛ(t)∩[0,x]|=dx(ℛ(t)),τ→x=dτ→x(ℛ(t))a.s.
So the range of τ→ is equal to ℛ(t)→. The fact that τ→ is a subordinator will be proved below but could be also derived directly from the regeneration property of ℛ→(t) (see [17]). Similarly the range of τ← is equal to ℛ(t)←.
Moreover,dY=-1 on ℛ(t) and Ya-=Yb if [a,b[ is an interval component of 𝒞(t). By integrating on [d(t),d(t)+y], we have a.s for every y≥0 such that d(t)+y∈ℛ(t),
(4.6)Yy+d(t)-Yy=-|ℛ(t)∩[d(t),d(t)+y]|.
Then using again the definition of τ→ given in Section 3.1 and that ℛ(t)→ is the range of τ→,
(4.7)τ→x=inf{y≥0:y∈ℛ(t)→,|ℛ(t)→∩[0,y]|>x}=inf{y≥0:d(t)+y∈ℛ(t),|ℛ(t)∩[d(t),d(t)+y]|>x}=inf{y≥0:Yy+d(t)-Yd(t)<-x}.
Moreover
(4.8)Yy+d(t)-Yd(t)=-y+∑(ti,xi,li)∈𝒫d(t)0≤xi≤yli,
and Lemma 4.1 entails that 𝒫d(t) is distributed as a PPP on [0,t]×ℝ+×ℝ+ with intensity ds⊗dx⊗ν(dl). So (Yy+d(t)-Yd(t))y≥0 is a Lévy process with bounded variation and drift -1 which verifies condition (A.7) (use (A.5) and -1+mt<0). Then Theorem A.1 in the appendix entails that τ→ is a subordinator whose Laplace exponent is the inverse function of -Ψ(t).
Asℛ(t)← is distributed as ℛ(t)→, τ← is distributed as τ→ by definition.
(iii) We determine now the distribution of(g(t),d(t)) using fluctuation theory, which enables us to get identities useful for the rest of the work. We write (Ỹx)x≥0 for the càdlàg version of (-Y-x)x≥0 and
(4.9)S(t):=sup{Ỹx,x≥0}=-I0,γ(t):=arg(S(t))=inf{x≥0:Ỹx=S(t)}.
Using (3.3) and the fact that Y has no negative jumps, we have
(4.10)g(t)=g0(ℛ(t))=sup{x≤0:Yx=Ix}=sup{x≤0:Yx-=I0}=-inf{x≥0:Ỹx=-I0}=-γ(t).
Using again (3.3) and the fact that (Yx)x≥0 is regular for ]-∞,0[ (see [20, Proposition  8, page 84]), we have also a.s. 							(4.11)d(t)=inf{x>0:Yx=Ix}=inf{x>0:Yx=I0}=inf{x>0:Yx<I0}=inf{x>0:Yx<-S(t)}=TS(t),
where (Tx)x≥0 is distributed as (τ→x)x≥0 by (4.7) and (Tx)x≥0 is independent of (S(t),γ(t)) since (Yx)x≥0 is independent of (Yx)x≤0. Then for all λ,μ≥0 with λ≠μ,
(4.12)𝔼(exp(λg(t)-μd(t)))=𝔼(exp(-λγ(t))𝔼(exp(-μTS(t))))=𝔼(exp(-λγ(t)-κ(t)(μ)S(t)))=-[Ψ(t)]′(0)κ(t)(λ)-κ(t)(μ)λ-μusing(A.15)(4.13)=(1-mt)κ(t)(λ)-κ(t)(μ)λ-μusing(A.5),
which gives the distributions of d(t), g(t), and l(t) letting, respectively, λ=0, μ=0, and λ→μ. Computing then the Laplace transform of (-Ul(t),(1-U)l(t)) where U is a uniform random variable on [0,1] independent of l(t) gives the right-hand side of (20). So (g(t),d(t))=(-U′l(t),(1-U′)l(t)), where U′ is a uniform random variable on [0,1] independent of l(t).Proofs of Theorems3.6 and 3.10 are close and made simultaneously. For that purpose, we introduce now Ψα,λ as the Laplace exponent (see (A.1)) of Yα,λ given, for y≥0, λ≥0, and α∈]1,2[ by
(4.14)Ψ2+,λ(y)=-λy-m2my22,Ψ2,λ(y)=-λy-Cmy22,Ψα,λ(y)=-λy-(Cαy)α.
We denote by 𝔻 the space of càdlàg function from ℝ+ to ℝ which we endow with the Skorokhod topology (see [22, page 292]). First, we prove the weak convergence of Y(t) after suitable rescaling.Lemma 4.2.
Ifν∈𝒟α(α∈]1,2]∪{2+}), then for all y≥0 and λ>0,
(4.15)ϵα(t)-1Ψ(t)(ϵα(t)(1-mt)-1y)→t→1/mΨα,1(y),xΨ((1-λfα(x))/m)((xfα(x))-1y)→x→∞Ψα,λ(y),
which entail the following weak convergences of processes in 𝔻:
(4.16)(ϵα(t)(1-mt)-1Yϵα(t)-1y(t))y≥0⇒t→1/m(Yyα,1)y≥0,((xfα(x))-1Yxy((1-λfα(x))/m))y≥0⇒x→∞(Yyα,λ)y≥0.Remark 4.3.
Ifν̅ is regularly varying at infinity with index -α∈]-1,-2[, then ν̅(x)-1Ψ((1-λxν̅(x))/m)(x-1y) converges to Ψα,λ(y) as x tends to infinity.Proof of Lemma4.2.
Using (A.4), we have
(4.17)xΨ(t)(y)=xy(mt-1-t∫0∞(1-e-yu)ν̅(u)du)=xy(mt-1-ty-1∫0∞e-yuν̅̅(u)du)=x(y(mt-1)-t∫0∞e-yuν̅̅(u)du),
where ν̅̅(u)=∫u∞ν̅(v)dv. The first part of the lemma then follows by applying the Tauberian theorem in [20, page 10] which gives the asymptotic behavior of the last term. For a detailed proof, we refer to [12].
These convergences ensure the convergence of the finite-dimensional distributions of the processes. The weak convergence in𝔻, which is the second part of the lemma, follows from [16, Theorem  13.17].In the spirit of Section3.1, we introduce the expected limit set, that is, the free space of the covering associated with Yα,λ, and the extremities of the block containing 0:
(4.18)ℛ(α,λ):={x∈ℝ:Yxα,λ=Ixα,λ},g(α,λ):=g0(ℛ(α,λ)),d(α,λ):=d0(ℛ(α,λ)).
We have the following analog of Proposition 3.4. ℛ(α,λ)→ and ℛ(α,λ)← are independent, identically distributed and independent of (g(α,λ),d(α,λ)). Moreover ℛ(α,λ)→ and ℛ(α,λ)← are, respectively, the range of the subordinators τ→α,λ and τ←α,λ, whose Laplace exponent κα,λ is the inverse function of -Ψα,λ. Finally, using [Ψα,λ]′(0)=-λ, the counterpart of (4.12) gives for ρ,μ≥0 and ρ≠μ,
(4.19)𝔼(exp(ρg(α,λ)-μd(α,λ)))=λκα,λ(ρ)-κα,λ(μ)ρ-μ.
The proof of these results follow the proof of Proposition 3.4, except for two points.(1) We cannot use the point process of files to prove the stationarity and regeneration property of ℛ(α,λ) and we must use the process Yα,λ instead. The stationarity is a direct consequence of the stationarity of (Yxα,λ-Ixα,λ)x∈ℝ. The regeneration property is a consequence of the counterpart of Lemma 4.1 which can be stated as follows. For all x∈ℝ,
(4.20)(Ydx(ℛ(α,λ))+yα,λ-Ydx(ℛ(α,λ))α,λ)y≥0isindependentof(Ydx(ℛ(α,λ))-yα,λ-Ydx(ℛ(α,λ))α,λ)y≥0
and distributed as (Yyα,λ)y≥0. As Lemma 4.1, this property is an extension to the stopping time dx(ℛ(α,λ)) of the following obvious result: (Yx+yα,λ-Yxα,λ)y≥0 is independent of (Yx-yα,λ-Yxα,λ)y≥0 and distributed as (Yyα,λ)y≥0.(2) It is convenient to define directly (τ→xα,λ)x≥0 by
(4.21)τ→xα,λ:=inf{y≥0:Yd(α,λ)+yα,λ-Yd(α,λ)α,λ<-x}.
For λ>0, [Ψα,λ]′(0)=-λ<0 and so we can apply Theorem A.1 and τ→α,λ is a subordinator whose Laplace κα,λ is the inverse function of -Ψα,λ. Moreover its range is a.s. equal to ℛ(α,λ)→, since the Lévy process (Yd(α,λ)+yα,λ-Yd(α,λ)α,λ)y≥0 is regular for ]-∞,0[ [20, Proposition  8, page 84].To prove Theorems3.6 and 3.10, we need a final lemma, which states the convergence of the Laplace exponent of ℛ(t)→.Lemma 4.4.
Ifν∈𝒟α(α∈]1,2]∪{2+}), then for all z≥0 and λ>0,
(4.22)(1-mt)ϵα(t)-1κ(t)(ϵα(t)z)→t→1/mκα,1(z),xfα(x)κ((1-λfα(x))/m)(x-1z)→x→∞κα,λ(z).Remark 4.5.
Ifν̅ is regularly varying at infinity of index -α∈]-1,-2[, we have similarly
(4.23)ν̅(x)-1κ((1-λxν̅(x))/m)(x-1z)→x→∞κα,λ(z).Proof.
First we prove that(4.24)α(t)~t→1/mβ(t)⇒κ(t)(α(t))~t→1/mκ(t)(β(t)).
Indeed the function u∈ℝ+*↦(1-e-u)/u decreases so for all x≥0 and u,v>0, we have
(4.25)min(uv,1)≤1-e-ux1-e-vx≤max(uv,1).
This gives
(4.26)min(α(t)β(t),1)≤∫0∞(1-e-α(t)x)Π(t)(dx)∫0∞(1-e-β(t)x)Π(t)(dx)≤max(α(t)β(t),1)
and proves (4.24) recalling (3.17).
Then the first part of Lemma4.2 and the identity κ(t)∘(-Ψ(t))=Id give the first part of Lemma 4.4. Indeed for every y≥0, Ψ(t)(ϵα(t)(1-mt)-1y)~t→1/mϵα(t)Ψα,1(y). So (4.24) entails
(4.27)ϵα(t)(1-mt)-1y~t→1/mκ(t)(-ϵα(t)Ψα,1(y)).
Put y=κα,1(z) to get the first limit of the lemma and follow the same way to get the second one.Proof of Theorem3.6.
First, by (4.13), we have
(4.28)𝔼(exp(ρϵα(t)g(t)-μϵα(t)d(t)))=(1-mt)κ(t)(ϵα(t)ρ)-κ(t)(ϵα(t)μ)ϵα(t)(ρ-μ).
Letting t→1/m using Lemma 4.4 gives the right-hand side of (4.19). Then ϵα(t)·(g(t),d(t)) converges weakly as t tends to 1/m to (g(α,1),d(α,1)).
Moreoverϵα(t)ℛ(t)→cl (resp., ϵα(t)ℛ(t)←cl) converges weakly in ℋ(ℝ+) as t tends to 1/m to ℛ(α,1)→cl (resp., ℛ(α,1)←cl). Indeed, by [11, Proposition  3.9], this is a consequence of the convergence of the Laplace exponent of ϵα(t)ℛ(t)→ given by Lemma 4.4. Informally, ϵα(t)ℛ(t)→cl is the range of (ϵα(t)τ→(1-mt)ϵα(t)-1z(t))z≥0 whose convergence in 𝔻 follows from Lemma 4.4.
We can now prove the theorem. We know from (3.7) that
(4.29)ϵα(t)ℛ(t)=ϵα(t)·(d(t)+ℛ(t)→)⊔(ϵα(t)·(-g(t)+ℛ(t)←)̃),
where ϵα(t)ℛ(t)←, ϵα(t)(-g(t),d(t)), and ϵα(t)ℛ(t)→ are independent by Proposition 3.4. Similarly
(4.30)ℛ(α,1)=(d(α,1)+ℛ(α,1)→)⊔(-g(α,1)+ℛ(α,1)←̃),
where ℛ(α,1)←, (-g(α,1),d(α,1)), and ℛ(α,1)→ are independent. As remarked above, we have also the following weak convergences as t tends to 1/m:
(4.31)ϵα(t)ℛ(t)←cl⇒ℛ(α,1)←cl,ϵα(t)(-g(t),d(t))⇒(-g(α,1),d(α,1)),ϵα(t)ℛ(t)→cl⇒ℛ(α,1)→cl.
So ϵα(t)ℛ(t)cl converges weakly to ℛ(α,1)cl in ℋ(ℝ) as t tends to 1/m.Proof of Corollary3.8.
The first result is a direct consequence of Theorem3.6. We have then
(4.32)ϵα(t)l(t)⇒t→1/md(α,1)-g(α,1).
Moreover, as κ2+,1∘(-Ψ2+,1)=Id, we can compute κ2+,1 and (4.19) gives
(4.33)𝔼(exp(-μ(d(2+,1))-g(2+,1)))=(κ2+,1)′(μ)=(1+1+2(m2/m)μm2/m)′(μ)=1-1+2(m2/m)μ.
So, by identification of Laplace transform, d(α,1)-g(α,1) is a gamma variable of parameter (1/2,m/(4m2)) and we get the result. The argument is similar in the case α=2.Proof of Theorem3.10.
The argument is similar to that of the proof of Theorem3.6 using the other limits of Lemma 4.4. We get that if x→∞ and 1-mt~λfα(x) with λ>0, then x-1ℛ(t) converges weakly in ℋ(ℝ) to {x∈ℝ:Yxα,λ=Ixα,λ}cl. The theorem follows by restriction to [0,1].To prove the corollary of Theorem3.10, we need the following result.Lemma 4.6.
The largest length of excursion of(Yxα,λ-Ixα,λ)x∈[0,1], denoted by Bα,λ, converges in probability to 0 as λ tends to infinity and to 1 as λ tends to 0.Proof.
(i) Let0≤a<b≤1. Note that for all λ′≥1 and x≥0, Yxα,λ′-Yxα,1=(1-λ′)x ensures that Ixα,λ′-Ixα,1≥(1-λ′)x. Then,
(4.34)Ya+2((b-a)/3)α,λ′-Ia+(b-a)/3α,λ′≤Ya+2((b-a)/3)α,1-Ia+(b-a)/3α,1+(1-λ′)b-a3.
So a.s. there exists λ′ such that
(4.35)Ya+2((b-a)/3)α,λ′<Ia+(b-a)/3α,λ′.
As Yα,λ′ has no negative jumps, it reaches its infimum on ]-∞,2(b-a)/3] in a point c∈[a+(b-a)/3,a+2(b-a)/3]. Then a.s. there exists c∈[a+(b-a)/3,a+2(b-a)/3] and λ′>0 such that c∈ℛ(α,λ′), which entails that c does not belong to the interior of Bα,λ′. Adding that Bα,λ decreases as λ increases, this property ensures that Bα,λ converges in probability to 0 as λ tends to infinity.
(ii) As(Yxα,0)x∈ℝ oscillates when x tends to -∞ (see [20, Corollary  2, page 190]), then
(4.36)I0α,λ→λ→0-∞,
which ensures that Bα,λ converges in probability to 1 as λ tends to 0.Proof of Corollary3.11.
The first result is a direct consequence of Theorem3.10.
Ifo(1-mt)=fα(x)(x→∞), then for every λ>0 and x large enough, t≤(1-λfα(x))/m and
(4.37)B1(x,t)x≤B1(x,(1-λfα(x))/m)x.
The right-hand side converges weakly to Bα,λ as x tends to infinity. Letting λ tend to infinity, the lemma above entails that B1(x,t)/x→x→∞0 in ℙ.
Similarly if1-mt=o(fα(x))(x→∞) , then for every λ>0 and x large enough,
(4.38)B1(x,t)x≥B1(x,(1-λfα(x))/m)x.
Letting λ tend to 0, Lemma 4.6 entails that B1(x,t)/x→x→∞1 in ℙ.Finally, we prove the result stated in Section3.4.Proof of Proposition3.12.
Asν̅(0)<∞, then Π̅(0)=tν̅(0)<∞ (see (3.18)). So τ→ is the sum of a drift and a compound Poisson process. That is, there exists a Poisson process (Nx)x≥0 of intensity tν̅(0) and a sequence (Xi)i∈ℕ of i.i.d. variables of law ν/ν̅(0) independent of (Nx)x≥0 such that
(4.39)τ→x=x+∑i=1NxXi,x≥0.
As ℛ(t)→ is the range of τ→, the number of data blocks of 𝒞(t) between d(t) and d(t)+τ→x is equal to the number of jumps of τ→ before x, that is Nx. Thus,
(4.40)numberofdatablocksin[d(t),d(t)+τ→x]τ→x=Nxτ→x→x→∞𝔼(N1)𝔼(τ→1)=tν̅(0)(1-mt)a.s.
by the law of large numbers (see [20, page 92]). This completes the proof.



---

*Source: 586751-2009-12-02.xml*