Heavy-tailed random walks, buffered queues and hidden large deviations
Harald Bernhard Bikramjit Das





Heavy-tailed buffered queues




 
  



  H. Bernhard B. Das

  Singapore University of Technology and Design

  Singapore University of Technology and Design,
 Pillar of Engineering Systems and Design,
8 Somapah Road, Singapore 487372 

           e1
 e2




  It is well-known that large deviations of random walks driven by independent and identically distributed heavy-tailed random variables are governed by the so-called principle of one large jump.
  We note that further subtleties hold for such random walks in the large deviation scale which we call hidden large deviation. We apply this idea in the context of queueing processes with heavy-tailed
  service times and study approximations of severe congestion times for (buffered) queues. We conclude with simulated examples to verify our results.
	




[class=AMS]

[Primary ]60F10
60G50
60G70
[; secondary ]60B10
62G32




buffered queues
heavy-tails
large deviations
regular variation






















§ INTRODUCTION











Stochastic processes with heavy-tailed components as building blocks are of interest in many areas of application, including, but not restricted to,  hydrology <cit.>, finance, insurance and risk management
  <cit.>,  tele-traffic data <cit.>, queueing theory <cit.>, social networks and random
  graphs <cit.>. The notion of heavy-tails in applied probability is often studied under the paradigm of regular variation. In this paper we concentrate on understanding subtle properties of heavy-tailed random walks which enables us to understand structures of simple GI/G/1 queues with heavy-tailed service times under certain regularity conditions. In particular, we establish how queueing congestion may occur (which we define in terms of long intense periods), not only because of one large jump, but also in terms of further jumps occurring in the process.

  It is well-known that if {Z_i}_i≥ 1  are iid zero mean  regularly varying random variables, then large deviations of their partial sums  S_n = ∑_i=1^n Z_i are essentially due to one of the random variables Z_i attaining a large value, 
see <cit.> for further details. Early results on this notion popularly known as the principle of one large jump were obtained in <cit.>. More formally, the notion of one large jump in this case  can be written as

    |S_n| > x = n|Z_1|>x (1+ o(1)),      x>b_n

for some choice of b_n ↑∞ as n→∞. Similar large deviation principles (LDPs) have been obtained in <cit.> under the more general assumption of the random variables being sub-exponential. Moving forward from random variables, the notion of regular variation of càdlàg processes has been characterized in <cit.>. It was aptly noted in <cit.> that large deviations for such processes with heavy-tailed margins are very closely related to the notion of regular variation.

A precise large deviation result for partial sum processes on the space [0,1] of càdlàg functions was provided in <cit.>; in fact this result was obtained for d-dimensional processes. In particular for d=1, the authors establish  that if S^n =(S_⌊ nt⌋)_t∈[0,1]
 is the càdlàg embedding of {S_k}_k=1^n into [0,1] with S_0=0, for suitably chosen sequences γ_n>0 and λ_n ↑∞ one can observe that

    γ_n S^n /λ_n ∈ ·  w^#→μ(· ),    n→∞,

for a non-null measure μ, where w^#→ denotes convergence in the space of boundedly finite measures on _0, see <cit.> and <cit.> for further details on the space and w^#-convergence. In particular the result  shows that an appropriate  choice of scaling is γ_n = [n Z_1>λ_n]^-1 and  the limit measure μ concentrates all its mass on step functions with exactly one jump discontinuity, which essentially retrieves the one large jump principle. 

Now it seems likely that there are possibilities - albeit rarer than the above case - that a large deviation of S_n may occur because two or more of the random variables {Z_i}_i=1^n were large. The probabilities of these events, although negligible under the scaling γ_n = [n Z_1>λ_n]^-1, are not exactly zero. Consequently, in this paper we aim to recover the rates at which such deviations happen and examine their structure. Furthermore our goal is to use such results in the context of queueing to understand the behavior of what we call long intense periods in a large-deviation-type event. 
Analysis of hidden behavior of regularly varying sequences on ^d <cit.> and more recently on ^∞ and Lévy processes on [0,1]   <cit.> has been conducted under the name hidden regular variation. Connections between hidden regular variation and elements of the classical large deviations framework have been established recently in <cit.>.
 
 

In this paper, our first contribution is to extend the large deviation principle in (<ref>) to hidden large deviations in the spirit of hidden regular variation. We establish that the most probable way a large deviation event occurs, which is not the result of only one random variable being large, is actually when two random variables are large; resulting in a non-null limit measure as in (<ref>) concentrating on processes having two jump discontinuities. For our analysis we use the framework proposed in <cit.> and  the notion of convergence used here is known as  -convergence which is closely related to the w^#-convergence of boundedly finite measures and developed in <cit.>.  We briefly recall the required background on regular variation and -convergence  in Section <ref>. The results on hidden large deviations of random walks are dealt with in Section <ref>, where the key result is obtained in Theorem <ref>. 


Queues with heavy-tailed service times have been of interest to researchers for a few years <cit.>. Our interest lies in figuring out when do we see long busy or intense periods in a queue.  In <cit.>, the author shows that for a GI/G/1 queue with heavy-tailed service times, the most likely way a long busy period occurs is when one big service requirement arrives at the beginning of the busy period and the queue drifts back to zero linearly thereafter. Consequently, a large deviation of a queueing process also  looks exactly the same. 
<cit.> studies the steady state loss in buffered queues and shows that for large buffers K the steady state loss can be approximated by the expected loss due to one arrival A filling the buffer completely starting zero, that is the expected loss is approximately [A-K]; see <cit.> for similar results concerning fluid queues. 


Equipped with a hidden large deviation principle for random walks, in Section <ref> we study queuing processes with heavy-tailed service times and finite capacity, which is a natural model to assume in many contexts. We define a long intense period as the fraction of time a queue with buffer capacity K>0 spends continuously above a level θ K,  θ∈ (0,1) for one sojourn and study the length of the longest such period for a given observation horizon.
A closely related notion of long strange segments  <cit.> has been consequently investigated in <cit.>, which examines the length of time the average process value spends in an unexpected regime. Considering hidden large deviations in such a setting  provides more insight since we observe that the first large deviation approximation gives only a crude estimate of the distribution of the length of intense periods for large buffers.  

In Theorem <ref> we derive an approximation to the distribution of the length of long intense periods in queues with large buffer sizes and conduct a simulation study in Section <ref> to show the effectiveness of the result. Finally, future directions are indicated and conclusions drawn in Section <ref>.
















§ NOTATIONS AND BACKGROUND












In this section we provide a summary of frequently used notations and concepts along with a review of material necessary for the results in the following sections.  We mostly  adhere to the notations and definitions introduced in <cit.>.




 §.§ Basic notations

A few notations and concepts are summarized here. 
Detailed discussions are in the references provided. Unless otherwise specified, capital letters like X,Z, S with various subscripts and superscripts are reserved for real-valued (and sometimes vector-valued) random variables, whereas bold-symboled capital letters like ,, (again with various subscripts and superscripts) denote vector- or function-valued random elements. Small letters in bold, like , are vectors in a suitable Euclidean space where =(z_1,…,z_n) if ∈^n.  






p0.17 p0.77
	β     
		
		Regularly varying functions with index β∈: that is, f:ℝ_+↦ℝ_+ satisfying lim_t→∞f(tx)/f(t)=x^β, for x>0.  
		
		We abuse notation and write X∈-α for regularly varying random variables as in Definition <ref>. In case of positive random variables, this is equivalent to requiring the tail of the cumulative distribution function to satisfy the limit relation above.
		
	

	
	(𝕊\ℂ)     
		(𝕊, ℂ) = (𝕊\ℂ) is the set of Borel measures on 𝕊\ℂ that  are finite on sets bounded away from ℂ.
	

	
	μ_n→μ     
		Convergence in (𝕊\ℂ); see  Definition <ref>.
	

	
	U_j^↑     
		{∈[0,1]^j:   0≤ u_1 < … < u_j ≤ 1 }.
	

	
	=([0,1],)     
		Space of all real-valued càdlàg functions on [0,1] equipped with the Skorohod J_1 metric.
	

	
	d_J_1    
		Metric on . If Λ denotes the class of strictly increasing continuous functions λ: [0,1] → [0,1] with λ(0)=0, λ(1)=1, then for f,g∈, we define		

    d_J_1 (f,g) :=   inf_λ∈Λmax{sup_t∈[0,1] |f(t)-g∘λ (t)|, sup_t∈ [0,1] |λ(t)-t| }
     
    		=   inf_λ∈Λf-g∘λ∨λ-e
where e(t)=t, ∀ t∈ [0,1]. See <cit.> for further details on the J_1-topology. Note that similar definitions could be worked out if we take _M =([0,M],) in place of . 
		
	

	_=j     
		Space of all real-valued step functions on [0,1] with exactly j jumps, j≥ 1. Assume _=0 is the space containing only the constant function at 0. Moreover, _=j⊂.
	

	
	_≤ j     
		Space of all step functions on [0,1] with  j or less jumps, _≤ j=⋃_k=0^j_=k.
	

	
	k (λ)     
		{∈^n:   |{i: |z_i| > λ}| = k}  for  λ>0, 1≤ k≤ n. It denotes the subset of ^n where exactly k co-ordinates are above λ > 0 in absolute value. Moreover ^n = ⋃_k=0^n  k (λ). See Section <ref>.
	

	
	ν_α^j     
		Product measure on (\{0})^j: ν_α×…×ν_α_j times with ν_α as defined in (<ref>).







 §.§ Convergence in 


We state our results as convergence in , a mode of convergence closely related to standard weak convergence of probability measures. 

The idea is as follows: to allow for hidden large deviations we need to exclude the set of possible large deviations from the space we consider in order to keep the limit measure non-degenerate in that region. This is similar to how large deviations avoid the law of large numbers for zero mean random variates: we need to exclude 0 from the non-negative real line to obtain a limit measure for |Z_1 + ⋯ + Z_n| ≥ nz,  z> 0. Convergence in  follows the same principle but we allow for the removal of an arbitrary closed set. As a consequence, we can define convergence in càdlàg spaces where we exclude certain types of step functions which form a closed set in .

In particular, let 𝕊 be a complete separable metric space, ℬ(𝕊) the collection of Borel sets on 𝕊 and ℂ⊂𝕊 a closed subset of 𝕊. Then we denote (𝕊, ℂ) = (𝕊\ℂ) the set of Borel measures on 𝕊\ℂ which are finite on sets bounded away from ℂ,
that is, the collection of  sets A ∈ℬ(𝕊) such that inf{ d(x,y): x ∈ℂ,   y ∈ A}>0 where d denotes the metric on 𝕊. 
Finally, we call a sequence {μ_n }_n≥ 0 convergent if the assigned values converge for a suitable class of test functions or sets. Denoting 𝕆 = 𝕊\ℂ the support set we use the notation := (𝕊, ℂ) as eponym for the mode of convergence and use the following definition of  -convergence.

A sequence of measures {μ_n}_n≥ 0⊂ converges to  μ_0 ∈ if for all closed sets F and open sets G in ℬ() which are bounded away from ℂ we have 

    lim sup_n→∞μ_n (F)  ≤μ_0(F), 
    lim inf_n →∞μ_n(G) ≥μ_0(G).

We write μ_n →μ_0 in  as n →∞, or simply μ_n →μ_0.


The definition above only states -convergence in terms of open and closed subsets of 𝕆. Theorem 2.1 of <cit.> provides several alternative characterizations of convergence in . The corresponding version of a continuous mapping theorem in  follows as Theorem 2.3 in the same publication. We state the continuous mapping theorem again for the sake of convenience. We denote a second space with the same properties as 𝕊 by 𝕊' and similarly add dashes to the corresponding elements of the second space.



	
	Denote h: 𝕊→𝕊' a measurable mapping such that for all sets A' ∈ℬ(𝕊') ∩ h(𝕊\ℂ) bounded away from ℂ' also h^-1(A') is bounded away from ℂ. Then μ_n →μ in (𝕊, ℂ) implies μ_n∘ h^-1→μ∘ h^-1 in (𝕊',ℂ') if the measure μ attains zero mass on the set of discontinuity points of h.





 



  
Relationship between -convergence and w^# convergence

<cit.> state their version of a large deviation result for random walks in terms of w^# convergence, working with boundedly finite measures instead. Specifically they consider the space _0 = (0,∞] ×𝕊_, where 𝕊_ is the unit sphere in . 
The metric on the radius is defined as d_(0,∞](x,y):= |1/x - 1/y|, thus making any set not bounded away from the zero function (in the usual J_1 metric) unbounded in the modified space. In turn, one may work with convergence of boundedly finite measures. Unfortunately it is not immediately clear how to extend this theory to allow for the removal of more than just the zero function, whereas convergence in  on the contrary is specifically designed for this purpose.





 §.§ Regular variation and heavy-tailed large deviations

A measurable function f: (0,∞) → (0,∞) is regularly varying at infinity with index α∈ if lim_t→∞f(tx)/f(t) = x^α for all x>0. A sequence of positive numbers {a_n}_n≥ 1 is regularly varying with index α∈ if lim_n→∞a_[cn]/a_n = c^α for all c>0.
Regular variation of unbounded random variables thus usually is defined in terms of regular variation of the tail of the corresponding cumulative distribution functions at infinity; see <cit.>, <cit.>, or <cit.> for related properties and examples.   We work with an equivalent definition stated in terms of -convergence <cit.>.

A random variable X is  regularly varying at infinity if there exists a regularly varying sequence γ_n and a non-zero measure μ∈(\{0}) such that

    γ_n X/n ∈·→μ(·),    n→∞,

in (\{0}). 

Since the measure μ satisfies the scaling property μ(sA) = s^-αμ(A),  s>0, A ∈\{0} for some α≥ 0 we write X∈-α.  For this paper we assume α>0.  Moreover, for X∈-α, we also assume that the following condition is satisfied.

    lim_n→∞X>n/|X|>n = p,   lim_n→∞X<-n/|X|>n = 1-p:=q.

for some 0≤ p ≤ 1. This is called the tail balance condition. For univariate X∈-α we stick to this choice unless otherwise specified. We also denote by ν_α, the following measure on \{0} for x>0,y>0,

    ν_α((-∞,-y) ∪ (x,∞)) = qy^-α + px^-α.

The limit measure μ in Definition <ref> is equal to ν_α if we choose the sequence γ_n to be [|X| > n]^-1.
Now, a heavy-tailed large deviation principle for real-valued random variables can be defined as follows in terms of -convergence.

A sequence of random variables {X_n}_n≥ 1, with X_n → 0 in probability, satisfies a heavy-tailed large deviation principle if there exists a positive sequence γ_n ↑∞ and a non-zero measure μ∈(\{0}) such that as n→∞

    γ_n X_n ∈·→μ(·),

in (\{0}).  



The similarity between the definitions of regular variation and heavy-tailed large deviation principle (LDP) is quite evident here. One salient difference is that regular variation is defined for a single random element, whereas an LDP, for a sequence of random elements. The special case of X_n = X/n shows that regular variation is a specific form of heavy tailed LDP according to our definition.

The definition of an LDP implies that X_n ∈·→ 0 as n→∞ for all sets in \{0}.

















For our purposes we give a more general definition of LDPs for random elements on a metric space 𝕊. Additionally we do no longer restrict to removing the zero element, but an arbitrary closed set ℂ⊂𝕊.


The random elements {_n}_n≥ 1⊂𝕊 satisfy a (heavy-tailed) large deviation principle on 𝕊\ℂ for a closed set ℂ⊂𝕊 if there exists a positive sequence γ_n ↑∞, and a non-zero measure μ∈(𝕊\ℂ) such that as n→∞

    γ_n _n∈ · →μ(·),

in (𝕊\ℂ).  We write _n∈LD( γ_n,μ,𝕊\ℂ).


The definition of heavy-tailed LDP as given in <cit.> is equivalent to Definition <ref> for stochastic processes with sample paths in . It has been observed, especially in the case of heavy-tailed random walks, that the limit measure μ obtained in the LDP, concentrates only on step functions with one jump; see <cit.>. Hence we may ask whether a different structure is observable if  we do not allow one jump functions to be in the support of the limit  measure for an LDP. Essentially, we are asking how often do we see events which are not governed by one jump in the space . 
The same question can be asked iteratively by removing the support set of a new found limit measure and examining the hidden structure of rarer and rarer events.

Hence a sequence of large deviation principles can be defined here.


The random elements {_n}_n≥ 1⊂𝕊 satisfy a sequence of (heavy-tailed) large deviation principles if there exists an increasing sequence {ℂ^(j)}_j≥ 1 of closed subsets of 𝕊 (i.e. ℂ^(k)⊃ℂ^(j) for k>j≥ 1), positive sequences γ_n^(j)↑_n ∞, j≥ 1 with γ_n^(j+1) / γ_n^(j)→_n ∞,  and non-zero measures μ^(j)∈(𝕊\ℂ^(j)), j ≥ 1 such that 

    _n ∈LD(γ_n^(j),μ^(j),𝕊\ℂ^(j)),    j≥ 1.



A similar definition could be stated for random elements satisfying only a finite number J≥ j ≥ 1 of large deviation principles. 







	The limit measure μ^(j) necessarily satisfies μ^(j)( (ℂ^(j+1))^c )=0 for all j≥ 1. More precisely, the measure concentrates on ℂ^(j+1)\ℂ^(j). Thus, the k level LDP uncovers the structure of rare events which were hidden (i.e. negligible) under the scaling of the preceding j level LDPs of the sequence with j<k. 
















We state a few useful facts about regularly varying functions that will be used repeatedly in the text. All of these are contained among others in Appendix B of <cit.>. 
In the following let f ∈-α_f,g ∈-α_g be two regularly varying functions. Then the sign of the regular variation exponent determines the behaviour at infinity:

    α_f>0:     lim_x→∞ f(x) = 0 
    α_f<0:     lim_x→∞ f(x) = ∞

Furthermore the product and composition of two regularly varying functions is also regularly varying

    fg ∈ℛ𝒱_-α_f -α_g
    
            g(x)→∞:     f ∘ g ∈ℛ𝒱_α_fα_g

Finally, we will repeatedly appeal to Karamata's theorem, especially the part concerning the tail integral, namely if α_f>1 then

    α_f >1:      lim_x →∞xf(x)/∫_x^∞ f(t)  t = α_f -1, 
    α_f <1:      lim_x →∞xf(x)/∫_x_0^x f(t)  t = 1-α_f.

















































































§ HIDDEN LARGE DEVIATIONS AND RANDOM WALKS












Equipped with the terminology and tools in Section <ref>, we proceed to understand the structure of heavy-tailed random walks in this section.  We look at heavy-tailed random walks as elements of . The key result for hidden LDPs for heavy-tailed random walks is in Theorem <ref>.




 §.§ Bounds on sums of random variables

For random variables Z_1, …, Z_n, denote their sum by S_n= Z_1+…+Z_n. Here S_n denotes the n-th step of a random walk. One of the key tools to bound movements in the random walk caused by “small” realizations will be Bernstein's inequality, see <cit.>.


Let Z_1, … , Z_n be iid bounded random variables with zero mean, variance Z_1=σ^2 and  |Z_1|≤ M. Then for any t>0,

    P(|S_n| ≥ t) < 2exp{-  t^2/ 2nσ^2 + 2/3Mt}.









We use this exponential bound on the absolute value of the sum to bound the probability of a large deviation in the sum of regularly varying random variables happening due to many variables attaining a small but non-negligible value. This bound, as we see hence,  turns out to be exponential rather than polynomial in the deviation level λ_n. 


Let {Z_i}_i=1^∞ be a sequence of iid random variables with Z_1 ∈ℛ𝒱_-α, α >0. In case the expectation exists, we assume it to be zero.
Denote S_n= ∑_k=1^n Z_k and let λ_n ∈ℛ𝒱_ρ be a regularly varying sequence such that in case

    Z_1<∞,   we have  ρ > 1/2
       Z_1=∞,   we have  αρ >1.


Then for any δ>0  and ε_0>0 small enough, there exists a constant c>0 such that for large enough n,

    |S_n| > δλ_n, |Z_i| ≤λ_n^1-ε_0, ∀  i≤ n  < 2exp(-cλ_n^ε_0 ).




When Z_1 has finite variance, the condition, ρ > 1/2, guarantees that λ_n↑∞ fast enough such that we avoid the central limit regime. When Z_1 has infinite variance, then αρ>1 ensures that the probability of at least one of the variables exceeding a large threshold on the scale of λ_n still tends to zero.



We transform S_n by making the Z_i's bounded  (the bound still depending on n);  and then apply Lemma <ref>  appropriately to obtain the result.













First observe that given δ>0, for small enough ε_0 and large enough n,

    A_n   := |S_n| > δλ_n, |Z_i| ≤λ_n^1-ε_0∀ 1≤ i≤ n 
       ≤| ∑_i=1^n Z_i |Z_i|≤λ_n^1-ε_0| > δλ_n
       ≤|  ∑_i=1^n (Z_i |Z_i|≤λ_n^1-ε_0 - Z_i  |Z_i|≤λ_n^1-ε_0)| > δ/2λ_n ,

where in the last inequality above we used the following bound, valid for large enough n and some constant c>0.

    | n/λ_nZ_1  |Z_1|≤λ_n^1-ε_0|    ≤n/λ_n|Z_1|  |Z_1|≤λ_n^1-ε_0
       ≤n/λ_n|Z_1|  |Z_1|≤λ_n
       ≤ c n |Z_1|>λ_n.




Now using  Lemma <ref> (Bernstein's inequality) to bound the sum of n zero mean random variables bounded in absolute value by M = 2 λ_n^1-ε_0, we obtain that for large enough n

    A_n   ≤ 2 exp( - (δ/2λ_n)^2/2nZ_1  |Z_1|≤λ_n^1-ε_0 + 4/3λ_n^1-ε_0δ/2λ_n )          
       ≤ 2exp( -λ_n^ε_0c_1/c_2 + β(n)),

where c_1,c_2 are positive constants and 
    β(n) =   2nZ_1  |Z_1|≤λ_n^1-ε_0/λ_n^2-ε_0.

Next we show that β(n)→ 0 as n→∞ which will imply that for large enough n, there is a ζ>0 such that


    A_n≤ 2exp( -λ_n^ε_0c_1/c_2 + ζ) =2exp( -cλ_n^ε_0),

where c=c_1/c_2+ζ, and thus the lemma is proven.

We show β(n) → 0 for three different cases as follows.

	
  * If α∈ (0,2) (implying infinite variance and αρ>1), using Karamata's theorem <cit.>  for small enough ε_0, large enough n and constant C>0 we have
	
    β(n)    ≤2n/λ_n^2-ε_0[ Z_1^2|Z_1|≤λ_n^1-ε_0] 
       ∼2n/λ_n^2-ε_0× C λ_n^2(1-ε_0)|Z_1|>λ_n^1-ε_0
       ∼ 2 C nλ_n^-ε_0|Z_1|>λ_n^1-ε_0→ 0    (n→∞).

	
  * If Z_1 < ∞, then β(n)≤ Cn/λ_n^2-ε_0 for some C>0 and hence vanishes as n →∞ for small enough ε_0>0.
	
  * If α =2 and Z_1=∞, then the variance is a slowly varying function. Again, for ε_0 small enough nλ_n^-2+ε_0→ 0 at a polynomial rate and hence β(n)→ 0.



















 §.§ Random walks embedded in [0,1]
 We embed the random walk S_n=Z_1+…+Z_n in =[0,1] and discuss its large deviations. Let
 ^(n) = (Z_1,…,Z_n) where Z_i's are iid  realizations from Z_1. For t∈ [0,1] and k ∈{1,…,n} define the functions _k^(n)(t) = Z_kk/n≤ t on . Now define 
    ^(n)(t) := ∑_k=1^n ^(n)_k (t) = ∑_k=1^⌊ nt ⌋ Z_k =S_⌊ nt ⌋
 to be the embedding of the random walk induced by  Z_1, …, Z_n into the space . Moreover let 0 (λ) := {∈^n: |z_i| ≤λ, ∀ i}.
The following corollary is a consequence of Lemma <ref>.


Under the conditions of Lemma <ref>, for any δ>0  and ε_0>0 small enough, there exist a constant c>0 such that for large enough n,

    P(sup_t∈ [0,1] |^(n)| > δλ_n , ^(n)∈0(λ_n^1-ε_0)) ≤ 2exp(-cλ_n^ε_0/2)


 Observe that from Lemma <ref>, for any δ>0 and ε_0>0 small enough and for large enough n,

    sup_t∈ [0,1] |^(n)| > δλ_n , ^(n)∈0(λ_n^1-ε_0)    = 
    		sup_t∈ [0,1] |S_⌊ nt ⌋| > δλ_n , Z_i≤λ_n^1-ε_0, ∀  i≤ n
       ≤sup_1≤ k ≤ n |S_k| > δλ_n , Z_i≤λ_n^1-ε_0, ∀  i≤ n 
       ≤ 2 nexp(-cλ_n^ε_0)
       ≤ 2exp(-cλ_n^ε_0/2)

for some constant c>0.




Now we define functions which relate vectors in ^n to càdlàg step functions in . For  integers j∈, denote U_j^↑ := {∈[0,1]^j:   0≤ u_1 < … < u_j ≤ 1 } and define functions 

    h_j: × U_j^↑→, 
       h_j((,))(t) :=  ∑_i=1^j z_iu_i≤ t.


The maps h_j allow us to define the collection of functions with exactly j jumps as subsets of . Hence we define the following classes of càdlàg functions.

    _=0   :={x∈: x(t)=0, 0≤ t ≤ 1} = {the zero function in [0,1]}, 
    _=j   := {x∈: x(t) =  h_j(,)(t) , 0≤ t≤ 1,   (,)∈× U_j^↑) }, 
    _≤ j   := ⋃_i=0^j _=i = {càdlàg step functions with j or less jumps}.




The map h_j: × U_j^↑↦  is continuous for j∈.

 The proof which is similar to Lemma 5.3 in <cit.>  is skipped here.






The function h_j maps points in × U_j^↑ to functions in _=j⊂, which are càdlàg functions in [0,1] with exactly j jumps. Hence for any F⊂ bounded away from _≤ (j-1), we have h_j^-1(F) = h_j^-1(F∩_=j).  Hence  h_j∘ h_j^-1 (F) = F∩_=j. 



The following  result extends the large deviation result of <cit.> in the setting of <cit.> in order to obtain what we think of as hidden large deviations. The special case of j=1 in Theorem <ref> corresponds to  <cit.>. The Lebesgue measure (in ^j) is denoted _j and ν_α^j is the j-fold product measure of ν_α (again in ^j) with ν_α as defined in (<ref>).
















Let j≥ 1. Under the conditions of Lemma <ref> and subsequent notations,  for λ_n→∞ as n→∞,

    γ_n^(j)^(n)/λ_n ∈ · → (ν_α^j ×_j) ∘ h_j^-1 (·)

in 𝕄(\{_≤ (j-1)}) as n→∞, where   γ_n^(j) = [ n |Z_1|>λ_n]^-j.


Note that under the conditions of Lemma <ref> we have ^(n)/λ_n → 0 (0 ∈) in probability.


In other words, the theorem states that the random element _n = ^(n)/λ_n satisfies a sequence of LDPs on {_≤ j}_j≥ 1. That is, the large deviations of the random walk concentrate on step functions with an increasing number of steps at increasingly faster rates.
In particular, for polynomially bounded rates γ_n large deviations of partial sum processes of iid regularly varying random variables will always concentrate on step functions, among all functions in .


Naturally \_≤ j are not the only  possible spaces to look at; and other types of LDPs might hold for dependent processes; we do not investigate such possibilities here. 
Additionally we do not investigate large deviations on \⋃_j=0^∞_=j in this paper. 







We show convergence in  according to Definition <ref> for (<ref>), starting with the upper bound for closed sets. The idea is to dissect the space ^n, which contains the first n elements of the random walk, into a union of n disjoint sets that define which dimensions are allowed to be “big”. For any k=0,1,…, n, and λ>0, define

    k (λ)    = {∈^n:   |{i: |z_i| > λ}| = k}.

Hence k ⊂^n are all points in ^n which have exactly k-co-ordinates with absolute value greater than  λ. Clearly 
    _n = ⋃_k=0^n k (λ).






  
Upper bound Let F⊂ be a closed set, bounded away from _≤ (j-1). Then for small ϵ_0>0,

    ^(n)/λ_n ∈ F   = ^(n)/λ_n ∈ F,  ^(n)∈⋃_k=0^n  k(λ_n^1-ε_0) 
       = ∑_i=0^n^(n)/λ_n ∈ F,  ^(n)∈ k(λ_n^1-ε_0)  =: ∑_i=0^nB_i.

We show that when multiplied by γ_n^(j), all the probabilities above are negligible except B_j.
Now, since F was chosen to be bounded away from _≤ (j-1), there exists a δ_0>0, such that all elements of F have a minimum distance  δ_0 to step functions with at most j-1 jumps. In particular F is bounded away from the zero element in . 



  
1. Bounding B_0 Using Corollary <ref>, we have constants c_0>0 and ϵ_0>0 such that,

    B_0   ≤sup |^(n)(t)/λ_n| > δ_0/2, |Z_i| ≤λ_n^1-ε_0
       ≤ 2exp(- c_0λ_n^ε_0).

Hence this term is exponentially bounded and goes to 0 when multiplied by γ_n^(j).


  
2. Bounding B_i for 1≤ i ≤ j-1  For i∈:={1,2,…,n}, denote by 
    (i)={={k_1,…,k_i}: 1≤ k_1<…<k_i≤ n},
 all possible  subsets of size i of the index set .  We will show that B_i for 1≤ i ≤ j-1 are also exponentially bounded. With the same δ_0 as previously chosen, we have

    B_i    =  ^(n)/λ_n ∈ F,  ^(n)∈ i(λ_n^1-ε_0) 
        = ∑_∈(i)^(n)/λ_n ∈ F,    |Z_l| > λ_n^1-ε_0, ∀ l ∈,    |Z_l| ≤λ_n^1-ε_0 , ∀ł∈\
       ≤∑_∈(i)(sup_t ∈ [0,1]|^(n)(t)-∑_m= 1^i_k_m^(n)(t) | > λ_n δ_0/2,  .
                          |Z_l| > λ_n^1-ε_0, ∀ l ∈,    |Z_l| ≤λ_n^1-ε_0 , ∀ l ∈\)
       ≤∑_∈(i)(sup_t ∈ [0,1]|∑_l∈\_l^(n)(t) | > λ_n δ_0/2,  |Z_l| ≤λ_n^1-ε_0 , ∀ l ∈\)
        =   ∑_∈(i)(   S_ (n-i)^*()  > λ_n δ_0/2,  |Z_l| ≤λ_n^1-ε_0 , ∀ l ∈\),

where 
	
    S_(n-i)^*() = sup_t∈[0,1]| ∑_l∈\^(n)_l(t)| sup_t∈[0,1]| ∑_l=1^n-i^(n)_l (t) | = sup_1≤ l ≤ n-i |S_l|
 
for any ∈(i). Since the size of the set (i) is |(i)| = ni, we have

    B_i   ≤ ni ( sup_1≤ j ≤ n-i|S_j| > λ_n δ_0/2,  |Z_l| ≤λ_n^1-ε_0 ,  1≤ l ≤ n-i   ),
       ≤ 2  ni exp(-c_iλ_n^ε_0/2),

for some c_i>0 according to Corollary <ref>. Since our choice of γ_n^(j) = [ n |Z_1|>λ_n]^-j, clearly 
γ_n^(j)∑_i=1^j-1B_i→ 0, as n→∞.



  
3. Bounding B_i for j+1≤ i ≤ n 
We bound the quantity γ_n^(j)∑_i=j+1^nB_i together.  We argue that when multiplied with γ_n^(j), the  probability of events with more than j large jumps is also negligible. Observe that 

    γ_n^(j)∑_i=j+1^nB_i   ≤γ_n^(j)∃ k_1,…, k_j+1∈ :   |Z_k_i| >λ_n^1-ε_0,   i=1,…,j+1
       =  γ_n^(j)nj+1|Z_1| > λ_n^1-ε_0^j+1
       ≤ c n |Z_1|> λ_n^1-ε_0^j+1/|Z_1| > λ_n^j =:f_n,

for some c>0. Now f_n is a regularly varying sequence with parameter  
    r_0:= 1 -(j+1)ρα + ε_0ρ(j+1)α + jρα =  (1-αρ) + (j+1)ε_0ρα,
 see <cit.> for details on operations on regular variation.  Since by choice αρ>1, for small enough ε_0, we have r_0<0. Hence 
    γ_n^(j)∑_i=j+1^nB_i≤ f_n→ 0
 as n →∞.



  
4. Bounding B_j Finally, we are left with the term γ_n^(j)B_j which is the non-negligible contributing term for large n. For δ>0, let 
    F^δ := {x ∈: d_J_1(x,F)≤δ}
 with δ small enough such that F^δ is still bounded away from _≤(j-1).

    B_j    = ^(n)/λ_n ∈ F,  ^(n)∈ i(λ_n^1-ε_0) 
        = ∑_∈(j)^(n)/λ_n ∈ F,    |Z_l| > λ_n^1-ε_0, ∀ l ∈,    |Z_k| ≤λ_n^1-ε_0 , ∀ l ∈\
    
                                   ≤∑_∈(j)P(sup_t ∈ [0,1]|^(n)(t)-∑_m=1^j_k_m^(n)(t) | ≤λ_n δ, ^(n)/λ_n ∈ F , .
                              |Z_l| > λ_n^1-ε_0, ∀ l ∈,    |Z_l| ≤λ_n^1-ε_0 , ∀ l ∈\)
    
                                            +   ∑_∈(j)P(sup_t ∈ [0,1]|^(n)(t)-∑_m=1^j_k_m^(n)(t) | > λ_n δ, ^(n)/λ_n ∈ F , .
                                  |Z_l| > λ_n^1-ε_0, ∀ l ∈,    |Z_l| ≤λ_n^1-ε_0 , ∀ l ∈\)
    
    	   ≤∑_∈(j)∑_m=1^j^(n)_k_m/λ_n ∈ F^δ
            + njsup_t∈ [0,1]| ∑_l ∈\^(n)_l|> λ_nδ,  |Z_l| ≤λ_n^1-ε_0 , ∀ l ∈\
       = P_j,1^(n) + P_j,2^(n).

Now, using Lemma <ref>, and arguments similar to the one for bounding B_i for 1≤ i ≤ j-1, we can check that the quantity P_j,2^(n) is negligible at rate γ_n^(j) and hence γ_n^(j)P_j,2^(n)→ 0 as n→∞. 

In the remaining term P_j,1^(n), we use the inverse of the map h_j to measure the probability. 
For any closed set F^*⊂, define 

    (J(F^*),T(F^*)) :=h_j^-1(F^*∩_=j) ⊂× U_j^↑

to be the pre-image of F^* ∩_=j under the map h_j broken into the jump part and the time part. 
Also note that due to the continuity of h_j (Lemma <ref>), since F^δ  is closed, the pre-image of F^δ is also closed.  
Clearly, ∑_m=1^j^(n)_k_m/λ_n ∈ F^δ is equivalent to ∑_m=1^j^(n)_k_m/λ_n ∈ F^δ∩_=j, as F^δ is bounded away from _≤ j-1. Thus,


    P_j,1^(n)   = ∑_∈(j)∑_m=1^j^(n)_k_m/λ_n ∈ F^δ
       = ∑_∈(j)∑_m=1^j^(n)_k_m/λ_n ∈ F^δ∩_=j
        = ∑_∈(j)∑_m=1^j Z_k_mk_m/n(t)/λ_n ∈ F^δ∩_=j
       = ∑_1≤ k_1, …,k_j≤ n P( (Z_k_m/λ_n)_1≤ m≤ j∈ J(F^δ)) 1( (k_1/n,…,k_j/n)∈ T(F^δ) ) 
        = P((Z_1,…,Z_j)/λ_n∈ J(F^δ) )  ∑_1≤ k_1< …< k_j ≤ n1( (k_1/n,…,k_j/n)∈ T(F^δ) ).
 
Note that as n→∞,

    |Z_1|>λ_n^-jP((Z_1,…,Z_j)/λ_n∈ J(F^δ) )  →ν_α^j(J(F^δ)).

Similarly, for T(F^δ), we obtain for n→∞,




    n^-j∑_1≤ k_1< …< k_j ≤ n1( (k_1/n,…,k_j/n)∈ T(F^δ) ) → Leb_j(T(F^δ)).












Hence using (<ref>) and (<ref>), we have as n→∞,

    γ_n^(j) P_j,1^(n)→ (ν_α^j×_j)(J(F^δ),T(F^δ)) = (ν_α^j ×_j) ∘ h_j^-1 (F^δ).

Therefore

    lim sup_n→∞γ_n^(j)B_j≤  (ν_α^j ×_j) ∘ h_j^-1 (F^δ),

for δ>0.
Summing up  all the bounds we obtained, we have 

    lim sup_n→∞γ_n^(j)^(n)/λ_n ∈ F≤ (ν_α^j ×_j)(h_j^-1(F^δ)).
 
The continuity of h_j ensures h_j^-1(F) = ⋂_δ>0 h_j^-1(F^δ) and hence letting δ→ 0 gives us the required upper bound

    lim sup_n→∞γ_n^(j)^(n)/λ_n ∈ F≤  (ν_α^j ×_j) ∘ h_j^-1 (F).







  
Lower bound
Let G be open and bounded away from _≤ (j-1). Now define, G^-δ⊂ G,

    G^-δ = {f∈ G: 
    	  d_J_1(f,g) < δ implies  g∈ G}.
Choose δ small enough such that G^-δ is non-empty. It is still open and bounded away from _≤ (j-1). Searching for a lower bound, we shrink the set G to its bare minimum,

    ^(n)/λ_n ∈ G   ≥∑_1≤ k_1< …< k_j ≤ n∑_i=1^j _k_i^(n)/λ_n ∈ G^-δ, sup |^(n)-∑_i=1^j _k_i^(n)| < λ_nδ
       = ∑_1≤ k_1< …< k_j ≤ n∑_i=1^j _k_i^(n)/λ_n ∈ G^-δsup |^(n)-∑_i=1^j _k_i^(n)| < λ_nδ

The second factor converges to one since S_n/λ_n → 0 in probability as n→∞.

For the first factor, we proceed in the same fashion as for P_j,1^(n) above.




Note that instead of our functions being in [0,1], we can easily extend Theorem <ref>  to càdlàg functions in  _M=[0,M] for some number M>0, with minor modifications to the proof. Hence all the results obtained in this section hold if we amend the definitions of the spaces ,_=j,_≤ j accordingly. Without loss of generality we refer to these results as if they hold for _M and its appropriate subsets from now on.




 §.§ Random walks with a constant drift


The conclusion in Theorem <ref>  assumes that the random variables are centred. In case Z_1≠ 0, we can use the theorem to infer information about the deviations from the mean for a process created with iid variables Z_1^* = Z_1- Z_1. Nevertheless, if we assume α>1 and Z_1≠ 0 we may look at the random walk with drift. By setting λ_n = n we are able to  preserve the drift in the limit. Theorem <ref>  can be modified to incorporate a drift term; for this we require two further lemmas as given below. Recall that e denotes the identity function on the respective domain [0,M].

	Let f : [0,M] → be continuous. Then the map 	ϕ_f: _M →_M 

    ϕ_f:      x ↦ x+f

    is continuous in the J_1-topology.




	Let ε>0. Suppose x,y ∈_M and d_J_1(x,y)<δ. Then 
    
    d_J_1(ϕ_f(x), ϕ_f(y))    = inf_λ x + f - (y + f) ∘λ∨ e- λ
       ≤inf_λ(  x - y ∘λ∨e-λ + f-f∘λ∨ e-λ) 
       ≤ 2 δ +  f - f∘λ_min∨ 2δ ,

    where λ_min denotes a time-shift close to the infimum of the distance of x and y. We may bound the fluctuation of f by the modulus of continuity w_f(δ)= sup_|s-t| ≤δ |f(s) - f(t)| which tends to zero as δ→ 0 to obtain
    
    d_J_1(ϕ_f(x), ϕ_f(y))    ≤ 4δ + w_f(2δ).





	Let {μ_n}_n≥ 1 be a sequence of finite measures on 𝕊 and μ_0 ∈(𝕊\ℂ). Suppose μ_n →μ_0 in  as n →∞. 
    
	Additionally assume there is an addition operation such that (𝕊,+) forms a group. Let { y_n }_n≥ 1⊂𝕊 be a sequence with y_n → 0. For y∈𝕊 denote s_y: A ↦ A-y,  A ∈ℬ(𝕊) the map shifting sets by an element y. Then  
    
    μ_n ∘ s_y_n→μ_0 ,    n →∞

    in .





	Let F ⊆𝕊 be closed and bounded away from ℂ. Let δ >0 such that F^δ is still bounded away form ℂ. For n large enough d(y_n,0)<δ (where d denotes the metric on 𝕊) and hence
	
    μ_n ∘ s_y_n (F)    ≤μ_n(F^δ).

    A similar argument holds for open sets G bounded away form ℂ. Letting δ→ 0 proves the result.





	Let {Z_i}_i=1^∞ be a sequence of iid random variables with Z_1 ∈ℛ𝒱_-α, α>1. Denote m = Z_1 and define 

    h_j^m: (\{0})^j × U_j^↑→,
       h_j^m((,))(t) :=  ∑_i=1^j z_iu_i≤ t + mt,

and correspondingly _=j^m := h_j^m (^j\{0}× U_j^↑). Then, as n →∞,

    γ_n^(j)^(n)/n ∈·→ (ν_α^j ×_j) ∘(h_j^m)^-1 (·),

in 𝕄(\_≤ (j-1)^m).



	The space _=j^m is defined as the space of step functions with exactly j discontinuities and a constant drift term “mt”. In particular, _=0^m = { x(t) = mt,   t ∈ [0,M]}. Theorem <ref> allowed for scalings λ_n that are growing fast enough such that ^(n)/λ_n stays close to zero for large n. Note that in Corollary <ref> we restrict to α>1 and specify λ_n = n to preserve the drift term. Necessarily, we observe for sets A bounded away from _=0^m that ^(n)/n ∈ A→ 0 as n →∞. Hence we examine (a sequence of) large deviation principles on \_≤ j-1^m.



The proof to the corollary is an application of Lemmas  <ref> and <ref>, and the continuous mapping argument of Theorem <ref>.


By Theorem <ref> we have

    γ_n^(j)(^(n) - ⌊ ne ⌋ m )/n ∈·→ (ν_α^j ×_j ) ∘ h_j^-1(·),    n→∞,

in 𝕄(\_≤ (j-1)).
Continuous mapping yields

    γ_n^(j)(^(n) - ⌊ ne ⌋ m )/n  + me ∈·→ (ν_α^j ×_j ) ∘ (h_j^m)^-1(·),    n→∞,

in 𝕄(\_≤ (j-1)^m) by virtue of Lemma <ref>. The result then follows by Lemma <ref>.









































































§ APPLICATION TO FINITE BUFFER QUEUES












In this section we apply the results of Theorem <ref> to the modified Lindeley recursion; see (<ref>) below. This formula is usually interpreted as describing the evolution of the queue length in a queue with finite buffer. First we derive large deviation principles for what we call long intense periods, defined as the maximum time a queue-size process spends continuously above a certain threshold. These LDPs are derived in a limit where both, the threshold level and the buffer size, approach infinity while the arrival process is sped up appropriately. Second, we present a simulation study which combines two of the derived LDPs to provide a simple analytical approximation and explanation for the empirical distribution of extremal lengths of long intense periods.












 §.§ Queueing processes












We study recursions of the form 

    Q_n^K =  min{max{Q_n-1^K + A_n - C_n,0},K},

with Q_0 ≥ 0, n ≥ 1 where {A_n}_n ≥ 1 and {C_n}_n≥ 1 are two sequences of iid non-negative random variables. This is the modified version of Lindley's recursion <cit.> to accommodate queues with finite buffers of size K. The recursion in (<ref>) can be interpreted in many different ways. For example in the context of network traffic, A_n may be interpreted as the number of packets arriving in the time interval C_n-C_n-1, whereas Q_n-1 describes the amount of work previously in the buffer of a single server processing work at a fixed rate. Any number of packets arriving at a full buffer are immediately discarded. For example, <cit.> studies (<ref>) under the assumption that ∫_0^x A_1>z z/ A_1 follows a subexponential distribution to conclude that the stationary loss rate is essentially due to one large observation when the buffer size approaches infinity. That is

    (Q_n^K +A_n+1 - C_n+1 - B) ∨ 0  = (A-K) ∨ 0(1 + o(1)),    K→∞.


Sample path LDPs for queueing processes with both infinite and finite buffers are studied in <cit.> mostly under the assumption that the moment generating function exists. We work with regularly varying random variables A_1 ∈-α, α>0 throughout which do not satisfy this assumption. 

To study the queueing recursion (<ref>) we follow the continuous mapping approach. First we define a suitable embedding of the sequences {A_n} and {C_n} in the space _M and then employ a continuous map to obtain a process which agrees with the queueing recursion at specified discrete time stamps. See for example <cit.>, <cit.> or <cit.> for more on this approach applied to queueing processes. This map is usually called reflection or Skorohod map. 
We briefly recall the required results.
For a process x ∈_M with x(0) = 0 we call {v(t), l(t), u(t)} the solution to the Skorohod problem if v(t) ∈ [0,K] and

    v(t) = x(t) + l(t) - u(t),   ∫_0^∞ v(t)  l(t) = 0,   ∫_0^∞ (K-v(t))  u(t) = 0,

and both l,u are non-negative non-decreasing functions.
Denote ψ_0^K: _M →_M the reflection map on the interval [0,K] as

    ψ_0^K : x ↦ v,

where v denotes the resulting regulated process of the Skorohod problem. 





This map is (Lipschitz-) continuous on _M equipped with the J_1 metric, see e.g. Lemma 4.6 of <cit.>.

To facilitate the discussion let C_n = c, n≥ 1 for some c>0 and denote 

    (t) := ∑_i=1^∞ (A_i-c)  t≥ i,    t ≥ 0
 
the embedding of the random walk induced by A_n - c in _M. Then 

    ^K := ψ_0^K()

is an embedding of Q_n^K into _M satisfying ^K(t) = Q_t^K for t ∈_0. Consequently we call ^K a queueing process with buffer K.


	We could also work with other embeddings as for example 
    (t):= ∑_n=1^∞ A_nt ≥ n - ct,   t ≥ 0
 and define _B^K := ψ_0^K() to allow for more nuanced interpretations of the queueing process . But since this work focuses on scaled versions of the queueing process with both time t and space ^K(t) scaled appropriately, the exact form of the interpolation is mostly irrelevant for the limit.















 §.§ Long intense periods













We adopt the position that a queueing process with the queue size close to the buffer K corresponds to an undesirable state. In such a state the service quality (of which ^K(t) is a proxy) is perceived as suboptimal. In the following we introduce and study the longest period an observed queueing process spends above a certain threshold θ K during the observation horizon [0,M]. We call such intervals long intense periods and investigate their length. 

	For a càdlàg function x ∈_M and a fixed level η∈_+ we define
	
    L^η: _M →_+ 
            x ↦sup_0≤ s < t ≤ M{ t-s: x(u) >η ∀ u ∈ (s,t) }.

	For a queueing process  with buffer K we call L^θ K(^K) the length of the intense period at level θ∈ (0,1). 





 
 How useful is it to calculate large deviations for long intense periods in queues? Can we gain more insight into waiting times in queues with this information To illustrate the applicability of such results, we use a simulation study which investigates the distribution of long intense periods for large threshold levels θ∈ (0,1).





The object of our simulation study is a queueing process ^K(t) with N=50000 arrival variables following a power law distribution with tail index α=1.44 and expectation m = 0.5. The queue has a finite buffer K=20000 and any additional service requirements will be lost. We assume the server works at a fixed rate c=1 with A_i describing the amount of service requirements arriving in one unit of time. 
We study long intense periods above the level θ=0.85, that is ^K(t)> 17000 is considered intense. The queueing process is observed on [0,M] with M=N.
With this example we treat service time distributions that still have finite means but infinite variance. The particular α value corresponds to the tail parameter of file sizes in Internet traffic reported in <cit.>.
Specifically we consider the arrival distribution 

    A_1 > z = ( z/(α-1) m + 1 )^-α ,   z>0.

Trivially A_1 >z∈-α.



Figure <ref> contains a histogram of the realized lengths of the long intense periods in queueing processes with the parameters above. It is based on 22000 observations which exhibit a strictly positive long intense period. That is, Figure <ref> shows a histogram of L^θ K()|L^θ K() >0. We would like to understand the shape of the histogram that we observe here; why is there a peak in the middle and a  decay afterwards? We revisit the histogram at the end of this section, accompanied by an explanation for its shape, based on (hidden) large deviations.





 §.§ Large deviations for long intense periods



We work out the corresponding sequence of large deviation principles for long intense periods of queueing processes.


	Let A_i, i≥ 1 be a sequence of iid non-negative regularly varying random variables with A_1 ∈-α, α>1. Assume c>m:=A_1 and define the queueing process ^K,(n)(t):= ^nK(nt)/n,   t∈ [0,M],   n ≥ 1 with ^K defined as in (<ref>). Denote κ :=1-θ/c-m K.
	
	The intense periods L_n:= L^θ K (^K,(n)) of the queueing process ^K,(n) observed on [0,M] satisfy a sequence of large deviation principles on [0,M] \ [0,(j-1)κ ] with the limit measure μ^(j)_L concentrating it's mass on ( (j-1)κ, jκ]. Specifically,
	
    L_n ∈γ_n^(j), μ^(j)_L, [0,M] \ [0,(j-1)κ],    1 ≤ j ≤⌊M/κ⌋,

	where the limit measure is given by 
	
    μ^(j)_L = (ν_α^j ×_j) ∘(h^m-c_j)^-1∘( ψ_0^K )^-1∘( L^θ K)^-1.



The assumption c>A_1 ensures that the process will drift in the negative direction on average, such that the process being close to its buffer is actually a rare event. At the first level for j=1 the theorem states that the long intense periods of a queueing process with buffer K and negative drift may be approximated by summing over all one-jump functions that contain a jump of size at least θ K. Since the measure concentrates on one-jump functions, the maximum attainable long intense period is attained by a single jump that exceeds the buffer limit K, with the process drifting in negative direction at rate m-c afterwards. Thus, latest at time κ after the jump the process will leave the intense region, no matter the size of the jump. 






Measuring the longest connected interval of time spent above a certain threshold is not a continuous operation for càdlàg processes. For example consider for M>2 the function x∈_M

    x(t) := 
    		1-t    if  t ∈ [0,1) 
    
    		2-t    if  t ∈ [1,M].

Adding a small constant via ϕ_c(x)(t):= x(t) +c we obtain for c<0: L^0(ϕ_c(x)) = (1-|c|)∧ 0 but L^0(x) = L^0(ϕ_0(x))=2, while at the same time ϕ_c(x) → x as c→ 0. Consequently L is not continuous. 
Nevertheless L^θ K is continuous almost everywhere with respect to the limit measure μ = ν_α×_1∘(h_1^m)^-1∘( ψ_0^K ) ^-1 on _M as the only way to obtain a discontinuity is through the jump at the end of the long intense interval. But the jump position is uniformly distributed hence the measure of that set is zero. Additionally, for our purposes, there is no need to consider functions outside the support of μ.






We need the following lemma to prove Theorem <ref>.






Let j ∈. Denote

    E_j   := {x ∈_M: [     [ x(t)=0]   OR [x(t+s) = x(t) - s(c-m) , |s| small enough]; for all but j points t. Additionally  x(t) ≥ x(t-) ∀ t∈ [0,M]. ]},
    
    
    
    	D_j    := {[          x ∈ E_j: ∃ t ∈{discontinuity points of x}; such that  x(t-) = θ K  OR  x(t)=θ K  OR  t ∈{0,M} ]}.


Then L^θ K is continuous on E_j\ D_j.


Note that E_j contains all càdlàg functions which contain exactly j positive jumps and decrease at rate c-m otherwise, regulated to take values in [0,K]. The set D_j further restricts to those functions whose jumps are bounded away from the critical level θ K.



To show the claim we need to introduce additional machinery. Namely we define an intense period as a period during which the function x ∈ E_j stays continuously above the critical level θ K and enumerate all such periods. Subsequently we show that the length of each such period cannot change much in case x is not perturbed too much.

Denote 

    _sL(l,x,v), _tL(l,x,v)   :  _+ ×_M × [0,M] →_+ 
    
    	_sL(l,x,v)    := inf{u ∈ (v,M]:  x(u) > l }, 
    
    	_tL(l,x,v)    := inf{u ∈ ( _sL(l,x,v),M]:  x(u)<l OR  u=M }.

We assume - as is usually the case - that inf∅ = ∞. Next we recursively record the start and end times of what we call intense periods, starting at zero.

    s_1,t_1    := _sL(l,x,0), _tL(l,x,0), 
    
    	s_i,t_i    := _sL(l,x,s_i-1), _tL(l,x, s_i-1),    i≥ 2, 
    
    	n_x    := max{i: s_i < ∞}

In case the tuple s_i,t_i is finite - either both or none are - we call t_i-s_i the length of the i^th intense period of x. Note that for x ∈ E_j there are exactly n_x intense periods, with 0≤ n_x ≤ j. The length of the longest of these corresponds to what we defined above in (<ref>) as the length of the long intense period of x. The enumeration of intense periods is well-defined for any càdlàg function on [0,M], although their number need no longer be finite, nor must the linear enumeration from zero capture all instances of the function exceeding a level l. 


Let x ∈ E_j \ D_j. Then the set of time points at which x is above the critical level can be partitioned as

    { u:  x(u) > θ K} = ⋃_i=1^n_x [s_i,t_i).

Since all jump discontinuities of x have values bounded away from the critical level, all of the intervals [s_i,t_i) and [t_i,s_i+1) are of positive length. Moreover, denoting

    Δ^θ K_J(x) := min{ |x(u^-) - θ K|∧ |x(u) - θ K | ∧ u-0 ∧ M-u :  u  is a discontinuity point of x},

we find that for all 0<δ < Δ^θ K_J(x), 

    x(u) ∈ (θ K -δ, θ K + δ) ⇔ u ∈(t_i - δ/c-m, t_i + δ/c-m)∩ [0,M]  for some  1≤ i ≤ n_x.

Next we show that for all ε>0, small enough such that ε(c-m)< Δ^θ K_J(x), there exists a ζ such that whenever d_J_1(x,y) < ζ we have 

    [     u ∈ [s_i+ε,t_i-ε)                     ⇒          y(u) > θ K ,; u ∈ [t_i + ε,s_i+1-ε)                     ⇒           y(u) < θ K. ]

This implies that any y close enough to x has similar intense periods as x, ignoring any negligible intense periods of y. Hence, L^θ K is continuous at x in (_M,d_J_1). 
We proceed by showing that the above claim holds for ζ = ε ((c-m)∧ 1)/3. Then there exists a λ∈Λ such that 

    x- y∘λ   < ε ((c-m)∧ 1)/2, 
    λ - e   < ε ((c-m)∧ 1)/2.

Now (<ref>) combined with (<ref>) (where δ = ε(c-m)/2) implies

    u ∈ [s_i , t_i-ε/2)    ⇒ (y ∘λ)(u)> θ K + ε (c-m)/2 - ε((c-m)∧1)/2≥θ K, 
    
    	u ∈ (t_i-ε/2,s_i+1)    ⇒ (y ∘λ)(u)< θ K.

Accounting for the time change introduced through λ, we infer from (<ref>) that the last two implications in (<ref>) hold when the two intervals get reduced by a further ε/2 on each side. In turn this proves the statement in (<ref>) and thus continuity of L^θ K on E_j\ D_j for all j≥ 1. 















We apply the continuous mapping argument in Theorem <ref> twice.
First, using the Skorohod map of (<ref>), the large deviations result in Corollary <ref> and continuous mapping yield

    γ_n^(j)Q^nK(nt)/n ∈·→ (ν_α×_j) ∘(h^m-c_j)^-1∘( ψ_0^K )^-1 (·),    n →∞

in ( ψ_0^K ( _M \ (_M)^m-c_≤ j-1) ). This is due to the definition in (<ref>) satisfying ψ_0^K (x/n) = ψ_0^nK(x)/n. The queueing map ψ_0^K preserves the number of jumps and hence satisfies the “bounded away” condition of Theorem <ref>.

It is immediate from the definition of the Skorohod problem that ψ_0^K(_M \ (_M)^m-c_≤ j-1) ⊆ E_j.



Additionally, note that μ_Q^(j) (D_j) = 0,  j≥ 1 as (h^m-c_j)^-1∘( ψ_0^K )^-1(D_j) ⊂^2j is not of full dimension; the condition of having x(t) or  x(t^-) = θ K amounts to imposing restrictions linking the time and value of a jump through relations of the form 

    x(t_i) - (t_i-t_i-1) (c-m) + J(t_i) = θ K,

where J(t_i) denotes the size of the j jump.
Hence Lemma <ref> above combined with a second application of Theorem <ref> yields the result.










 §.§ Calculating explicit limit measures


In the following we compute the limit measures μ_L^(1) and μ_L^(2). We assume M> 2κ throughout. For j=1 we obtain

    μ^(1)_L( (l,∞) ) = 
    			(M-l) ( l(c-m) + θ K)^-α   if  l ∈ (0,κ] 
    
    			0    otherwise.

In other words, the measure μ_L^(1) is the sum of a point mass at l = κ with value K^-α(M-κ) and an absolutely continuous part on (0,κ). 
Considering this initial large deviations estimate on its own we would approximate ( L^θ K( ^K) > κ ) ≈ 0. For any finite buffer non-limit scenario this may be too coarse. A more refined estimate based on hidden large deviations allows for more accuracy. Namely on [0,M] \ [0,κ ] we have 

    γ_n^(2) L^θ nK(^nK(nt)) ∈·→μ_L^(2)(·),    n →∞,

in ( [0,M] \ [0,κ]), which concentrates on (κ,2κ]. This again can be explained by the rate γ_n^(2) only allowing for at most two jumps in the random walk. Any intense period with length L<κ is more likely to happen due to one jump hence processes containing only one jump must be excluded in the hidden large deviation principle. Long intense periods with length L>2κ are not possible since the maximum length is achieved if the buffer is filled at some initial time t_0< M-2κ starting the long intense period and an additional jump at time t_0 + κ of size at least (1-θ)K. We compute the limit measure for the events {L > l},   l ∈ (κ,2κ]:

    μ_L,θ,K^(2) ( (l,∞) )    = μ^(2) ( {All two jump functions with L>l}) 
       = (M-l) ∫_θ K^∞ν_α ( j_1) ∫_l-κ^(K∧ j_1 - θ K)/(c-m) u_2 ∫_l(c-m) - ( K∧ j_1 - θ K)^∞ν_α( j_2) 
       = (M-l) ∫_θ K^∞ν_α( j_1) K∧ j_1 - θ K /c-m > l-κK∧ j_1 - θ K /c-m - (l-κ)/( l(c-m) - (K ∧ j_1 - θ K)   )^α
       = M-l/c-m∫_θ K + l(c-m) - (1-θ)K^K α x^-α-1x - θ K - l(c-m) + (1-θ K) /( l(c-m) + θ K - x) ^α x 
          + M-l/c-mK^-α2(1-θ) K - l(c-m) /( l(c-m) - (1-θ) K )^α .


	Further limit measures can be computed but the explicit derivation becomes more cumbersome as the level increases.
	












 §.§ Simulation study - combining the first two LDPs
















In this section we provide some insights on the practical relevance of hidden large deviations. 





We find that in the setting of the simulation study described in Example <ref> we are able to numerically validate the rate and limit measure of hidden large deviations. 

The previous section established large deviation principles for long intense periods for any interval [(j-1)κ, jκ] with j≤⌊ M/κ⌋, each with its own rate. 

And indeed, for the theory of LDPs we may only treat these limit measures separately due to the different magnitudes of the rates γ_n^(j). In practice however, for any finite observation period of a queue with finite buffer size, several of the limit measures might be relevant for a single statistic. 
The simulation study will examine the interplay of different rates in a single probability estimate. 
We proceed to construct the two estimates involving the first and second level LDPs separately.






  
One jump
According to traditional large deviation estimates for heavy tailed queueing processes with “large” buffers, the long intense period will be due to a single jump reaching above the threshold level θ K and the queue drifting in direction -(c-m) thereafter.
To use Theorem <ref> we need to choose a queue sequence number n. 



We thus obtain the following approximation.

    L^θ K( ^K)> l    = L^θ K/n(^K/n,(n)) > l/n
       = L_n > l/n
       ≈1/γ_n^(1)μ^(1)_L((l/n,∞)) 
    
    
    
    
    	   = 
    		n^αA_1>n (M-l) (l(c-m) + θ K)^-α   if  l ∈ (0, κ] 
    
    		0    otherwise .

The point mass at κ yields

    L^θ K(^K)  ∈ (κ - ε ,κ + ε)≈(n/K)^αA_1 > n (M-κ).
 




  
One or two jumps
The two jump measure can be approximated in the same fashion as the approximation for one jump above using equation (<ref>) instead. To get a single estimate for the distribution of the long intense periods of the queueing process ^K we propose to combine the two estimates into a single approximation.

    L^θ K( ^K) > l≈
    		nA_1>nμ_L^(1)( (l/n,∞) )    if   l ∈ (0,κ] 
    
    		n^2 A_1>n^2 μ^(2)_L( ( l/n,∞) )    if   l ∈ ( κ, 2 κ] 
    
    		0    otherwise,

where the buffer size K and observation horizon M are scaled accordingly in the limit measures.







In Figure <ref> we plot the same histogram as in Figure <ref>, and view it as an estimate of the density 

    L^θ K( ^K) ∈ l | L^θ K( ^K)> 0,  l>0.
 
The limit measure μ^(1)_L puts zero mass on values beyond the vertical red line which marks the location of the point mass of μ^(1)_L. Due to n being finite we expect some values immediately to the right of the point mass as caused by only a finite number of random variables approximating the mean rate of decrease for the queue content. Nevertheless, concerning the values on the far right we believe an explanation via Hidden Large deviations (HLD) is best suited for the distribution of L^θ K( ^K).
Hence we add the estimate in (<ref>) to the plot. 
To visualize the point mass we fix two ε_1,ε_2>0 such that the point mass at κ gets distributed over the area (κ-ε_1 , κ + ε_2). Outside of this region we approximate the measure with the corresponding densities.
Additionally we provide a plot of the tail of the distribution on a log scale to better visualize the fit for the hidden large deviation estimate. The figures clearly show how our hidden large deviation estimates closely approximate the histogram observed (more clearly in the right plot in Figure <ref>.)
































§ CONCLUSION AND FURTHER REMARKS


We provide limit measures for successively rarer large deviations of random walks with regularly varying iid increments. Scaling time and space appropriately we are able to obtain limit measures for large deviations of queueing processes which preserve the drift term in the limit. In the final section we showed that hidden large deviations at the second level, though happening at the squared rate of the first large deviation, are numerically observable. Clearly, our (hidden) large deviation estimate performs quite well to approximate the histogram - even at the tail (on a log scale.)  



For future directions of study, one can explore large deviations on a space \⋃_j=1^∞_=j which we have not ventured into. The choice of our space of convergence was governed by jumps in heavy-tailed processes. Namely, we expect all of the random variables to attain values on the same scale. The exact structure of such deviations remains largely an open question. Similarly, we did not explore into situations where the “iid" assumption gets relaxed. A j level LDP happens at a rate 

which is the j power of the rate of the first LDP. This clearly is a consequence of the independence among the random variables driving the random walk. Future work on weakly dependent variables are under current investigation.


















§ ACKNOWLEDGEMENTS

We would like to thank Parthanil Roy for interesting discussions on the preliminary ideas of (hidden) large deviations.
Additionally, we gratefully acknowledge support from MOE Tier 2 grant MOE-2013-T2-1-158. 











imsart-nameyear


