The laws of iterated and triple logarithms for extreme values of regenerative processes
Alexander Marynych Ivan Matsak
math.PR



Research Article






[type=corresp,id=cor1]Corresponding author.
Taras Shevchenko National University of Kyiv,Faculty of Computer Science and Cybernetics, 01601 Kyiv, Ukraine












A.V. Marynych and I.K. MatsakExtreme values of regenerative processes


We analyze almost sure asymptotic behavior of extreme values of a regenerative
process. We show that under certain conditions a properly centered and
normalized running maximum of a regenerative process satisfies a law of
the iterated logarithm for the lim sup and a law of the triple logarithm
for the lim inf. This complements a previously known result of Glasserman
and Kou [Ann. Appl. Probab. 5(2) (1995), 424–445]. We apply our results
to several queuing systems and a birth and death process.



Extreme values
regenerative processes
queuing systems


[MSC2010]
60G70
60F15
60K25



11 1 2020
1 2 2020
1 2 2020
17 2 2020






§ INTRODUCTION AND MAIN RESULTS



Various problems related to asymptotic behavior of extreme values of regenerative
processesregenerative processes is of considerable practical interest and has attracted a lot
of attention in probabilistic community. For example, extremes in queuing
systemsextremes in queuing systems and of birth and death processes have been investigated in <cit.>,
to name but a few. Analysis carried out in the above papers is mostly based
on the classical theory of extreme values for independent identically distributed
(i.i.d.) random variables. A survey of early results in this direction
can be found, among other, in paper <cit.>. In recent paper <cit.>
a slightly different approach to the asymptotic analysis of extreme values
of regenerative processesregenerative processes using a nonlinear time transformations has been
proposed.

The aforementioned works were mostly aimed at the derivation of weak
limit theorems for extremes of regenerative processes.regenerative processes extremes In this article
instead, we are interested in almost sure (a.s.) behavior of general
regenerative processesregenerative processes and in particular of regenerative processesregenerative processes appearing
in queuing and birth–death systems. Our main results formulated in
Theorems <ref> and <ref> below provide the laws of
iterated and triple logarithms for the running maximum of regenerative
processes.regenerative processes A distinguishing feature of our results is a different scaling
required for lim sup and lim inf. Under the assumption that the right
tail of the maximum of a regenerative processregenerative processes over its regeneration cycle has
an exponential tail, this type of behavior has already been observed in
<cit.>, see Proposition 3.2 therein. Our theorems provide a
generalization of the aforementioned result and cover, for example,
regenerative processesregenerative processes with Weibull-like tails of the maximum over a
regeneration cycle. As in many other papers dealing with extremes of
regenerative processes,regenerative processes extremes our approach relies on analyzing the a.s. behavior of
the running maximum of i.i.d. random variables. In this respect, let us also
mention papers <cit.> dealing with
a.s. growth rate of the running maximum, see Section 3.5 in
<cit.> for a survey.

Before formulating the results we introduce necessary definitions. Let us
recall, see <cit.>, that a positive measurable function U defined in
some neighbourhood of +∞ is called regularly varying at +∞
with index κ∈ℝ if U(x)=x^κ V(x), and the
function V is slowly varying at +∞, that is


    lim _t→ +∞V(tx)/V(t) = 1  for all  x>0.


Given a function H:ℝ→ℝ we denote by H^-1 its
generalized inverse defined by



    H^-1(y)=inf{  x∈ℝ: H(x)>y}  ,   y∈ℝ.


The following definition is of crucial importance for our main results.



We say that a function H:ℝ→ℝ satisfies condition
(𝕌) if the following holds:




  * lim _x→ +∞H(x)=+∞;


  * the function H is eventually nondecreasing and differentiable;


  * the derivative h(x):=H'(x) is such that for some
κ∈ℝ the function


    ĥ(x) = (H^-1(x))'=1/h(H^-1(x)),   x∈ℝ,


is regularly varying at +∞ with index κ.




Note that the assumption of regular variation of ĥ implies that h
is eventually positive. Thus, H is eventually strictly increasing and the
generalized inverse H^-1 defined by (<ref>) eventually
coincides with the usual inverse.

Let X=(X(t))_t≥ 0 be a regenerative random process,regenerative random process that is,


    X(t) = ξ _k (t- S_k-1)    t ∈ [S_k-1 , S_k), k∈ℕ,


where


    S_0=0,     S_k = T_1 + ⋯ + T_k,   k ∈ℕ,


and (T_k , ξ _k (· ))_k∈ℕ is a sequence of
independent copies of a pair (T , ξ (· )), see, for example,
<cit.> and <cit.>. The points
(S_k) are called regeneration epochs and the interval [S_k-1 , S_k)
is the k-th period of regeneration.regeneration

For t≥ 0, put


    X̅(t) = sup _0≤ s < t X(s),


and note that X̅(T_1) is the maximum of the process X on the first
period of regeneration.regeneration Let F be the distribution function of
X̅(T_1), that is,


    F(x):= 𝐏(X̅(T_1)≤ x).


Put


    R(x):=-log (1-F(x)),   x∈ℝ,


and


    α _T = 𝐄T_1 = 𝐄T.


Note also that it is always possible to write a decomposition



    R(x)= R_0 (x)+ R_1 (x),   x∈ℝ,


where



    |R_1 (x)| ≤ C_1 < ∞ ,   x∈ℝ.


Here and hereafter we denote by C, C_1 , C_2 etc. some positive
constants which may vary from place to place and may depend on parameters of
the process X(· ).

We are ready to formulate our first result.



Let (X(t))_t≥ 0 be a regenerative random process.regenerative random process Assume that there
exists a decomposition (<ref>) such that (<ref>) holds and the
function R_0 satisfies condition (𝕌). Suppose further that
α _T < ∞. For large enough x∈ℝ, let r_0 be
the derivative of R_0. Then



    lim sup _t→∞ r_0 (A_0 (t)) (X̅(t)
    -A_0(t))/L_2 (t)=1   a.s.,


and



    lim inf _t→∞ r_0 (A_0 (t)) (X̅(t) -A_0
    (t))/L_3 (t) =-1   a.s.,


where


    A_0(t)=R_0^-1 (logt/α _T ),      L_2
    (t) = loglog t,     L_3 (t) = logloglog t .




Our next result is a counterpart of Theorem <ref> for discrete
processes taking values in some lattice in ℝ. Such processes are
important, among other fields, in the queuing theory. Assume that



    𝐏(X(t)∈{0,1,2,3,…})=1,   t≥ 0,


and, for k=0,1,2,3,…, put


    R_k:=-log𝐏(X̅(T_1) > k).


Similarly to (<ref>) and (<ref>) we can write a decomposition



    R_k= R_0(k) + R_1(k),   k=0,1,2,3,… ,


where R_0:ℝ→ℝ and R_1:ℝ→ℝ
are real-valued functions and R_1 is such that



    |R_1(k)| ≤ C_1 < ∞ ,    k=0,1,2,3,… .




Let (X(t))_t≥ 0 be a regenerative random processregenerative random process such that
(<ref>) holds. Assume that there exists a decomposition (<ref>)
such that (<ref>) is fulfilled and the function R_0 satisfies
condition (𝕌). Suppose also that α _T < ∞.




  (i) The asymptotic relation



    r_0 (R_0^-1 (x))= o(log x),   x→∞ ,


entails



    lim sup _t→∞ r_0 (A_0 (t)) (X̅(t) -A_0
    (t))/L_2 (t) =1   a.s.



  (ii) The asymptotic relation



    r_0 (R_0^-1 (x))= o(loglog x),   x→∞ ,


entails



    lim inf _t→∞ r_0 (A_0 (t)) (X̅(t) -A_0
    (t))/L_3 (t) =-1   a.s.


The functions A_0 and r_0 were defined in Theorem <ref>.







In the discrete setting we assume that there exist extensions of the
sequences (R_0(k)) and (R_1(k)) to functions defined on the whole
real line with the extension of R_0 being smooth. While such an
assumption might look artificial, it is necessary for keeping the paper
homogeneous and allows us to work both in continuous and discrete settings
with the same class of functions 𝕌.


The article is organized as follows. In Section <ref> we collect
and prove some auxiliary results needed in the proofs of our main theorems.
They are given in Section <ref>. In Section <ref> we
apply Theorems <ref> and <ref> to some queuing systemsqueuing system
and birth–death processes.




§ PRELIMINARIES


Let us consider a sequence (ξ _k)_k∈ℕ of independent
copies of a random variable ξ with the distribution function F_ξ(x)=𝐏(ξ≤ x) =: 1 - exp (-R_ξ(x)). Put



    z_n = max _1≤ i ≤ nξ _i .


The following result was proved in <cit.>, see Theorem 1 therein.



Assume that the distribution of ξ is such that R_ξ satisfies
condition (𝕌). With a(n)=R_ξ^-1(log n) it holds



    lim sup _n→∞r_ξ(a(n))(z_n-a(n))/L_2
    (n)=1   a.s.,


and



    lim inf _n→∞r_ξ(a(n))(z_n-a(n))/L_3
    (n)=-1   a.s.,


where, for large enough x∈ℝ,


    r_ξ(x):=R^'_ξ(x)= F^'_ξ(x)/1-F^'_ξ(x).




The proof of Lemma <ref>, given in <cit.>, consists of two steps.
Firstly, the claim is established for the standard exponential distribution
τ ^e, that is, assuming 𝐏(ξ≤ x)=𝐏(τ ^e≤ x)= 1- exp (-x). In the second step the claim is proved for an
arbitrary R_ξ using regular variation and the representation



    R_ξ^-1(τ ^e) d=ξ     R_ξ^-1(z_n ^e) d= z_n.


Here and hereafter z_n ^e = max _1≤ i ≤ nτ ^e_i and
(τ ^e_i)_i∈ℕ are independent copies of τ ^e.

We need the following generalization of Lemma <ref>.



Assume that the law of ξ is such that the function R_ξ possesses
a decomposition (<ref>) with R_1 satisfying (<ref>) and R_0
satisfying condition (𝕌). Then



    lim sup _n→∞r_0(a_0(n))(z_n-a_0(n))/L_2
    (n)=1   a.s.,


and



    lim inf _n→∞r_0(a_0(n))(z_n-a_0(n))/L_3
    (n)=-1   a.s.,


where a_0(n)=R_0^-1(logn) and r_0 (x)=R_0^'(x).


To prove Lemma <ref> we need the following simple result, see Theorem 3.1
in <cit.>.



Let H be a function regularly varying at +∞ and let (c_n)_n∈ℕ and (d_n)_n∈ℕ be two sequences of real numbers
such that lim _n→∞c_n=+∞, lim _n→∞c_n/d_n= 1. Then


    lim _n→∞H(c_n)/H(d_n)=1.





Fix a sequence of standard exponential random variables (τ
_i^e)_i∈ℕ and assume without loss of generality that the
sequence (z_n)_n∈ℕ is constructed from (τ
_i^e)_i∈ℕ via formula (<ref>). The subsequent proof is
divided into two steps.

Step 1. Suppose additionally that the function R_0 is everywhere
nondecreasing, differentiable, and R_0 (-∞ )=0. Then F_0 (x):=1 -
exp (-R_0(x)) is a distribution function. Put ξ ^'_i=
R_0^-1(τ ^e_i) for i∈ℕ and let z_n^' =
max _1≤ i ≤ nξ _i^'. From Lemma <ref> we infer



    lim sup _n→∞r_0(a_0(n))(z_n^'-a_0(n))/L_2 (n)=1   a.s.


Let C_1 be a constant such that (<ref>) holds. From the definition
of the function R_ξ^-1 and decomposition (<ref>) we obtain


    R_0^-1(x- C_1)≤ R_ξ^-1(x) ≤ R_0^-1(x+ C_1),   
    x∈ℝ,


and thereupon


    R_0^-1(z_n^e- C_1)≤ R_ξ^-1(z_n^e) ≤
    R_0^-1(z_n^e+ C_1).


Hence, by monotonicity of R_0^-1, we have



    | R_ξ^-1(z_n^e) -R_0^-1(z_n^e)|≤ R_0^-1(z_n^e+
    C_1) - R_0^-1(z_n^e- C_1) = 2C_1r̂_0 (z_n^e+ C_1
    (2θ _n -1)),


where the equality follows from the mean value theorem for differentiable
functions, r̂_0(x) = (R_0^-1(x))' and 0≤θ _n≤
1.

It is known, see <cit.>, that


    lim _n→∞z_n^e/log n=1  a.s.


Thus, from Lemma <ref> we deduce


    lim _n→∞r̂_0(z_n^e + C_1 (2θ _n
    -1))/r̂_0 (log n)= 1   a.s.


In conjunction with (<ref>) this yields



    | R_ξ^-1(z_n^e) -R_0^-1(z_n^e)|≤ 2C_1r̂_0
    (log n) (1+o(1)) = 2C_1/r_0 (a_0 (n) ) (1+o(1)) .


Taking together relations (<ref>), (<ref>) we arrive at
(<ref>).

Similarly, from Lemma <ref> we have



    lim inf _n→∞r_0(a_0(n))(z_n^'-a_0(n))/L_3 (n)=-1   a.s.


Therefore, (<ref>) follows from (<ref>) and (<ref>).

Step 2. Let us now turn to the general case where the function
R_0 is nondecreasing and differentiable on some interval [x_0 , ∞
) with x_0>0. Recall decomposition (<ref>). Let
R̃_0:ℝ→ℝ and R̃_1:ℝ→ℝ be arbitrary nondecreasing differentiable functions such that


    R̃_0(x)   =R_0(x)  and  R̃_1(x)=R_1(x)
      for  x≥ x_0,
    
    R̃_0(x)   =R̃_1(x)=0  for  x≤ 0.


Put


    R̃(x):=R̃_0(x)+R̃_1(x),   x∈ℝ.


The functions R̃_0, R̃_1 and R̃ satisfy all
the assumptions of Step 1. Thus, if we set


    ξ̃_i = R̃^-1(τ _i^e) ,     z̃_n = max
    _1≤ i ≤ nξ̃_i,


then the sequence (z̃_n)_n∈ℕ satisfies (<ref>)
and (<ref>) with the same normalizing functions r_0 (a_0(n)) and
a_0(n). The latter holds true since for sufficiently large x>0 we have
R̃_0^-1(x) = R_0^-1 (x).

It remains to note that the asymptotics of (z̃_n) and (z_n)
are the same. Indeed, set


    n_0: = min (i≥ 1: τ _i^e≥ y_0 ),


where y_0 := R(x_0) = R̃(x_0). Then z_n = z̃_n
for n≥ n_0 and we see that both (<ref>) and (<ref>) hold for
(z_n) as well. This finishes the proof of Lemma <ref>.


The next lemma is a counterpart of Lemma <ref> for discrete distributions.
Assume that ξ has distribution


    𝐏(ξ =k ) = p_k,


where p_k≥ 0 and ∑ _k=0^∞ p_k =1. Put


    q(k) = ∑ _i> k p_i=exp (-R_ξ ,k).




Let ξ be a random variable taking values in {0,1,2,3,…} and
let R_ξ ,k be such that there exists a decomposition (<ref>) with
R_1 satisfying (<ref>) and R_0 satisfying condition
(𝕌).




  (i) if (<ref>) holds, then (z_n) satisfies equality
    (<ref>);


  (ii) if (<ref>) holds, then (z_n) also satisfies
    (<ref>).





Similarly to Lemma <ref> the proof is divided into two steps. We provide
the details only for the first step leaving the second step for an interested
reader. Thus, we put ξ _i^' = R_0^-1(τ ^e_i) for
i∈ℕ. Note that ξ _i^' are i.i.d. with the
distribution function F_0 (x)=1 - exp (-R_0(x)). Thus, for
z_n^' = max _1≤ i ≤ nξ _i^', equality
(<ref>) holds.

Let us consider


    ⌈ R_ξ ,k^-1(y) ⌉ =inf{  k=0,1,2,3,… : R_ξ
    ,k≥ y}  ,


then


    |R_ξ ,k^-1(y) - ⌈ R_ξ ,k^-1(y) ⌉ | ≤ 1,


for all y∈ℝ, and therefore


    |R_ξ ,k^-1(z_n^e) - ⌈ R_ξ ,k^-1(z_n^e) ⌉ | ≤
    1 ,      |R_0^-1(z_n^e) - ⌈ R_0^-1(z_n^e) ⌉ |
    ≤ 1 .


Further, condition (<ref>) and monotonicity of the function ⌈·⌉ both imply


    ⌈ R_0^-1(z_n^e -C_1)⌉≤⌈ R_ξ ,k^-1(z_n^e)
    ⌉≤⌈ R_0^-1(z_n^e +C_1)⌉ .


Combining the above estimates, we derive


    R_0^-1(z_n^e -C_1) -2 ≤ R_ξ ,k^-1(z_n^e) ≤ R_0^-1(z_n^e
    +C_1) +2.


This means




    | R_ξ ,k^-1(z_n^e) -R_0^-1(z_n^e)|   ≤   
    R_0^-1(z_n^e+ C_1) -R_0^-1(z_n^e- C_1) +4 
       ≤   2C_1/r_0 (a_0 (n) ) (1+o(1)) +4,


see estimates (<ref>), (<ref>).

Assuming (<ref>) we see that (<ref>) holds. Similarly, condition
(<ref>) yields (<ref>).


The next simple lemma is probably known, however we prefer to give an
elementary few lines proof.



For arbitrary p>1 and b∈ℝ it holds



    Λ _n := ∑ _k=1^np^k/k^b =
    p^n+1/(p-1)n^b (1+o(1)),   n→∞ .





By the Stolz–Cesáro theorem we have


    lim _n→∞(p-1)n^bΛ _n/p^n+1   =lim _n →∞Λ _n-Λ
    _n-1/p^n+1/(p-1)n^b-p^n/(p-1)(n-1)^b
       =lim _n→∞p^n/n^b/p^n+1/(p-1)n^b-p^n/(p-1)(n-1)^b=
    lim _n→∞p-1/p-n^b/(n-1)^b=1.


The proof is complete.





§ PROOFS OF THEOREMS <REF> AND <REF>



Let us start with a proof of equality (<ref>). To this end, we introduce
the following notation


    Y_k = sup _ S_k-1≤ t < S_k X(t) ,      Z_n = max _1 ≤ k
    ≤ n Y_k,   k∈ℕ.


Since (S_k) are the moments of regenerationregeneration of the process (X(t))_t≥
0, (Y_k) are i.i.d. random variables. Furthermore, it is clear that the
sequence (Y_k) satisfies conditions of Lemma <ref>. Therefore,



    lim sup _n→∞r_0(a_0(n))(Z_n-a_0(n))/L_2
    (n)=1   a.s.


Denote by N the counting process for the sequence (S_k), that is,


    N(t) = max{k≥ 0 : S_k≤ t},    t≥ 0.


Since lim _t→∞N(t)=+∞ a.s. and N(t) runs through all
positive integers, from (<ref>) we obtain



    lim sup _t→∞r_0(R_0^-1(log
    N(t)))(Z_N(t)-R_0^-1(log N(t)))/L_2 (N(t))=1   a.s.


By the strong law of large numbers for N we have



    lim _t→∞N(t)/t = 1/α _T  a.s.,


whence, as t→∞,


    logN(t) = logt/α _T + o(1)   a.s.


In what follows o(1) is a random function which converges to zero a.s. as
t→∞. Plugging the above representations into (<ref>), we
obtain



    lim sup _t→∞r_0(R_0^-1(logt/α
    _T + o(1)))(Z_N(t)-R_0^-1(logt/α _T +
    o(1)))/L_2 (t/α _T(1 + o(1)) )=1   a.s.


Further, by the slow variation of L_2 we can replace the denominator in
(<ref>) by L_2 (t).

Let us recall that under the assumptions of Theorem <ref>, the
function r̂_0(x) = (R_0^-1(x))' is regularly varying at
infinity. So using once again Lemma <ref>, we obtain the equalities


    r̂_0(logt/α _T + o(1))= r̂_0(logt/α _T)(1+ o(1))= 1 + o(1)/r_0(R_0^-1(logt/α _T)),   t→∞ ,


and


    R_0^-1(logt/α _T + o(1)) -R_0^-1(logt/α _T)= o(1) r̂_0(logt/α _T +
    o(1)),   t→∞ .


Combining the above relations, from (<ref>) we derive



    lim sup _t→∞r_0(A_0(t))(Z_N(t)-A_0(t)
    )/L_2 (t)=1   a.s.,


with A_0(t) and r_0(t) as in Theorem <ref>. The same
argument with N(t) replaced by N(t) + 1 yields


    lim sup _t→∞r_0(A_0(t))(Z_N(t)+1-A_0(t)
    )/L_2 (t)=1   a.s.


It remains to note that


    Z_N(t)≤X̅(t) ≤ Z_N(t) + 1  a.s.


Summarizing this gives equality (<ref>). The proof of the relation
(<ref>) utilizes equality (<ref>) of Lemma <ref> and is similar. We
omit the details.


The derivation of Theorem <ref> is based on Lemma <ref> and
basically repeats the proof of Theorem <ref>. We leave the details
to a reader.

Suppose that under the assumptions of Theorem <ref> the parameter
t runs over a countable set t∈𝒯:= {t_0 =0 < t_1 < t_2
< ⋯} such that lim _i→∞t_i =+∞ as i →∞. The set 𝒯 can be random and the process X can depend on
𝒯. Assume that ℙ(S_i∈𝒯)=1 for all
i∈ℕ.

Put X_i:=X(t_i ) and X̅_n = max _0 ≤ i ≤ nX_i.
Assume that extreme values of the process X are attained at the points of
the set 𝒯. More precisely, for all t≥ 0,



    sup _0 ≤ s ≤ tX(s) = max _0 ≤ t_i≤ tX_i  a.s.


In what follows the next proposition will be useful.



Under the assumptions of Theorem <ref> suppose that there exists a
set 𝒯 such that condition (<ref>) holds and, further,



    lim _n→∞t_n/n=α  a.s.


Then



    lim sup _t→∞ r_0 (A (n)) (X̅_n -A
    (n))/L_2 (n) =1   a.s.,


and



    lim inf _n→∞ r_0 (A (n)) (X̅_n -A
    (n))/L_3 (n) =-1   a.s.,


where


    A(n)=R_0^-1 (logα n/α _T ).





A proof given below is similar to the proof of Theorem <ref>. From
equations (<ref>) and (<ref>) we obtain, as n→∞,



    N(t_n)/n= N(t_n)/t_nt_n/n →α/α _T  a.s.


Further, replacing n by N(t_n) in equality (<ref>), which is
possible because N(t_n) diverges to infinity through all positive
integers, we get



    lim sup _n→∞r_0(R_0^-1(log
    N(t_n)))(Z_N(t_n)-R_0^-1(log N(t_n)))/L_2 (N(t_n))=1   a.s.


Directly from (<ref>) we derive


    Z_N(t_n)≤X̅_n≤ Z_N(t_n) + 1  a.s.


These inequalities and relations (<ref>), (<ref>) yield equality
(<ref>). The same argument can be applied for proving (<ref>).





§ APPLICATIONS



[Queuing system GI/G/1]
Let us consider a single-channel queuing system with customers arriving at
0=t_0<t_1<t_2<⋯ < t_i<⋯. Let 0=W_0,W_1,W_2,
… , W_i, … be the actual waiting times of the customers. Thus,
at time t=0 a first customer arrives and the service starts immediately.
Denote by ζ _i = t_i - t_i-1, for i∈ℕ, the
interarrival times between successive customers, and η _i, i∈ℕ, is the service time of the i-th customer. Suppose that (ζ
_i ) and (η _i) are independent sequences of i.i.d.i.i.d
random variables. In the standard notation, this queuing systemqueuing system has the type
GI/G/1, see <cit.>.

Let W(t) be the waiting time of the last customer in the queue at time
t≥ 0, that is,


    W(t) =W_ν (t),  where ν (t)= max (k≥ 0: t_k≤ t),


and


    W(t_n) =W(t_n + ) = W_n.


Set


    W̅(t) = sup _0 ≤ s ≤ tW(s) = max _0 ≤ t_k≤ t W_k
    ,


then


    W̅_n = max _1≤ i ≤ nW_i = W̅(t_n).


Denote 𝐄ζ _i =a, 𝐄η _i =b and assume that
both expectations are finite. Further, we impose the following conditions on
ζ _i and η _i:



    ρ : = b/a <1


and for some γ > 0, it holds



    𝐄exp (γ (η _i - ζ _i)) =1,     𝐄( η
    _i - ζ _i)exp (γ (η _i - ζ _i))< ∞ .


Under these assumptions the evolution of the queuing systemqueuing system can be decomposed
into busy periods, when a customer is in service, interleaved by idle
periods, when the system is empty. Let us introduce regeneration moments
(S_k) of the process W as follows: S_0 =0 and, for i∈ℕ, S_i is the arrival time of a new customer at the end of
i-th idle period. Let T_i be the duration of the i-th regeneration
cycle, and W̅(T_1) be the maximum waiting time during the first
regeneration cycle. It is known, see <cit.> and <cit.>, that under
conditions (<ref>) and (<ref>), we have


    𝐏(W̅(T_1) > x) = (C+o(1)) exp (-γ x) ,    x
    →∞ .


Condition (<ref>) also guarantees that the average duration of the i-th
regeneration cycle is finite, that is, α _T = 𝐄T_i <
∞, see <cit.>.

Thus, if we set X(t)=W(t), R_0 (x)= γ x, R_1 (x)= log C +
o(1) and r_0 (x)= γ, then from Theorem <ref> and
Proposition <ref> we derive the corollary.



Assume that the queuing systemqueuing system GI/G/1 satisfies conditions (<ref>) and
(<ref>). Then



    lim sup _t→∞γW̅(t) -log t/L_2 (t)
    = lim sup _n→∞γW̅_n -log n/L_2
    (n) =1   a.s.,


and



    lim inf _t→∞γW̅(t) -log t/L_3 (t)
    = lim inf _n→∞γW̅_n -log n/L_3
    (n) =-1   a.s.










  (i) Suppose that


    𝐏(ζ _i≤ x) = 1 - exp (-λ x),    𝐏(η _i≤ x) = 1 - exp (-μ x),    x ≥ 0,


that is, we consider the queuing systemqueuing system M/M/1. Assume further, that ρ
:= λ /μ <1. It is easy to check that conditions (<ref>) and
(<ref>) are fulfilled, and therefore equalities (<ref>) and
(<ref>) hold with γ = μ - λ = μ (1-ρ ).


  (ii) Suppose that


    𝐏(ζ _i≤ x) = 1 - exp (-λ x) ,    x≥ 0,


and 𝐏(η _i = const = d)=1. Assume further, that ρ : =
λ d < 1. Then relations (<ref>)–(<ref>) hold with γ =
x_ρ/d, with x_ρ>0 being the unique positive root of the
equation


    e^x = 1 + x/ρ.









[Queuing system M/M/m]
Let us now consider a queuing systemqueuing system with m servers and customers which
arrive according to the Poisson process with intensity λ, and
service times being independent copies of a random variable η with
an exponential distribution


    𝐏(η≤ x) = 1 - exp (-μ x),   x≥ 0.


In the standard notation, this queuing systemqueuing system has the type M/M/m, see
<cit.>.

We impose the following assumption on the parameters λ and μ
ensuring existence of the stationary regime:



    ρ : = λ/m μ <1 .


For t≥ 0, let Q(t) denote the length of the queue at time t, that
is, the total number of customers in service or pending. Set


    Q̅(t) = sup _0≤ s < t Q(s),   t≥ 0.


In the same way as in Example <ref>, one can introduce regeneration
moments (S_k) for the process Q: S_0:=0 and, for i∈ℕ,
S_i is the arrival time of a new customer after the i-th busy period.
Let T_i be the duration of the i-th regeneration cycle and
Q̅(T_1) be the maximum length of the queue in the first regeneration
cycle. Put



    𝐏(Q̅(T_1) >x) = exp (-R(x)).


In recent paper <cit.> the authors established that function R in
(<ref>) satisfies conditions (<ref>) and (<ref>) with


    R_0 (x)= -x logρ ,      r_0 (x)= -logρ .


Using Theorem <ref> we infer



Assume that for a queuing systemqueuing system M/M/m, 1 ≤ m < ∞, the
condition (<ref>) is fulfilled. Then



    lim sup _t→∞Q̅(t)log1/ρ-logt/L_2 (t) =1  a.s.,


and



    lim inf _t→∞Q̅(t)log1/ρ-logt/L_3 (t) =-1,  a.s.






Relations (<ref>) and (<ref>) have been proved in <cit.> by
direct calculations. Let us note that in case m=∞, which has also
been treated in <cit.>, the asymptotics of Q̅(t) is of completely
different form, see also <cit.>.





[Birth and death processes]
Let X=(X(t))_t≥ 0 be a birth and death processes with parameters



    λ _n = λ n +a,     μ _n = μ n ,   λ , μ ,a
    >0,  n=0, 1, 2, … ,


see <cit.>. That is, (X(t))_t≥ 0 is a
time-homogeneous Markov process such that, for t≥ 0, given {X(t)=n}
the probability of transition to state n + 1 over a small period of time
δ is (λ n +a)δ +o(δ ), n=0,1,2,3,…, and
the probability of transition to n - 1 is μ n δ +o(δ ),
n=1,2,3,…. The parameter a can be interpreted as the
infinitesimal intensity of population growth due to immigration. The
birth–death process X is usually called the process with linear growth and
immigration.

We assume that X(0)=0 and



    ρ := λ/μ <1 .


Put


    θ _0 = 1,     θ _k = ∏ _i=1^kλ
    _i-1/μ _i ,    k∈ℕ .


It is not difficult to check that condition (<ref>) ensures



    ∑ _k≥ 1θ _k < ∞ ,


and



    ∑ _k≥ 11/λ _kθ _k = ∞ .


Under conditions (<ref>) and (<ref>), see <cit.> and
<cit.>, there exists a stationary regime, that is,


    lim _t →∞𝐏( X(t)= k) = p_k ,


with



    p_k = θ _k p_0,   k=0,1,2,3,… ,   where  p_0
    = (∑ _k= 0^∞θ _k)^-1.


Further, X is a regenerative processregenerative processes with regeneration moments (S_k),
whereS_0 =0 and S_i, i∈ℕ, is the moment of i-th
return to state 0. It is known that


    𝐄T_k = 1 /(λ _0+μ _0)p_0= 1 /a p_0 ,


where T_k =S_k - S_k-1 is the duration of the k-th regeneration
cycle, see Eq. (32) in <cit.>. If (<ref>) holds, then


    M(t) := 𝐄 X(t)→a/μ - λ,   t →∞ ,


see <cit.>. We are interested in the asymptotic behavior of extreme
values


    X̅(t) = sup _0≤ s < t X(s),    t≥ 0.


Let us show how to apply Theorem <ref> to the asymptotic analysis
of X̅(t). Firstly, we need to evaluate accurately the sequence
(R(n)) defined by


    q(n): = 𝐏 ( X̅(T_1) > n ) = exp (-R(n)).


It is known, see <cit.> or Eq. (34) in <cit.>, that



    q(n) = 1/∑ _k=0^nα _k,


where α _0 = 1 and α _k = ∏ _i=1^kμ
_i/λ _i for k∈ℕ.

Using equalities (<ref>) and (<ref>) we can rewrite α _k as
follows:



    α _k = β _k/ρ ^k ,     β _k = ∏
    _i=1^k (1 - 1/1+iλ /a ).


Further, using Taylor's expansion


    log (1 + x) = x - x^2/2 + x^3/3 - ⋯ ,    |x| <
    1,


we have



    logβ _k = ∑ _i=1^klog (1 - 1/1+iλ
    /a ) = - ∑ _i=1^k1/1+iλ /a + d_k ,


where d_k has a finite limit, as k→∞. Combining the relation



    |∑ _i=1^k1/1+iλ /a - ∑ _i=1^k1/iλ /a | = ∑ _i=1^ka/λ i
    (1+iλ /a) =C_1 +o(1),   k→∞ ,


and the fact



    lim _n→∞∑ _i=1^n1/i - log n = γ ,


with γ =0.577… being the Euler–Mascheroni constant, we conclude


    ∑ _i=1^klog (1 - 1/1+iλ /a ) = -
    a/λlog k + C_2 + o(1),   k→∞ .


Therefore,



    β _k =C k^-a/λ (1+o(1)) ,


where



    C=e^C_2:=lim _n→∞ n^a/λ∏ _i=1^n(1
    - 1/1+iλ /a).


Now we can apply Lemma <ref> to obtain


    Λ _n = ∑ _k=1^nρ ^-k/k^a/λ = ρ
    ^-n-1/(1/ρ-1)n^a/λ (1+o(1)),    n→∞ .


Taking into account equality (<ref>), we obtain


    ∑ _k=0^nα _k = C ρ ^-n-1/(1/ρ -1)n^a/λ (1+o(1)),   n→∞ .


Thus,



    q(n) =  1/ρ -1/C ρ ^n+1 n^a/λ(1+o(1)),    n→∞ ,


and we have the following representation


    R(n)= -log q(n) = R_0 (n) + R_1 (n),


where


    R_0 (n) = -n logρ - a/λlog n ,      R_1 (n)
    = -log 1/ρ -1/C -logρ + o(1),   n→∞ .


The function R_0 (x) = -x logρ - a/λlog x is
increasing for x ≥ x_0 = -a/λlogρ and,
furthermore, satisfies condition (𝕌).

Since r_0 (x) = -logρ - a/λ x, conditions
(<ref>), (<ref>) of Theorem <ref> hold.

It remains to find a simple formula for the function A_0 in
(<ref>) and (<ref>). To this end, let us write


    log (t/α _T )= R_0(A_0 (t)) = -A_0 (t)
    logρ - a/λlog A_0 (t)=A_0(t) (-logρ +o(1) ),


as t→∞. Upon taking logarithms we get


    log A_0 (t) = loglog (t/α _T ) +O(1),
       t→∞ ,


and plugging this back into the initial equality yields


    A_0 (t) =
    logt + a/λL_2 (t) + O(1)/-logρ.


Thus, from Theorem <ref> we infer the following.



Let (X(t))_t≥ 0 be the birth and death process with parameters
λ _n = λ n +a, μ _n = μ n, where λ ,μ ,
a>0, n=0, 1, 2,3,…. Suppose also that (<ref>) holds. Then



    lim sup _t→∞X̅(t)log1/ρ-log t/L_2 (t) =1+
    a/λ,  a.s.,


and



    lim inf _t→∞X̅(t)log1/ρ-log t-a/λL_2 (t)/L_3 (t) =-1,
      a.s.







It is clear from the above calculations that the condition X(0)=0 can
be removed, that is, equations (<ref>) and (<ref>) hold true for
an arbitrary starting point X(0)∈{0,1,2,…}.


Let us finally mention without a proof a statement which follows easily
from equations (<ref>), (<ref>) and Theorem 2 in
<cit.>.




Let (X(t))_t≥ 0 be the birth and death process that satisfies all
conditions of Corollary <ref>. Then



    lim _n→∞𝐏(X̅(t_n^*)≥ n) = 1-
    exp (-a p_0 x),   x>0,


where t^*_n = C ρ ^-n n^-a/ λx/(1/ρ -1), while
p_0 and C are defined by (<ref>) and (<ref>). This relation
can also be recast in a more transparent way as follows:



    lim _n→∞𝐏(C^-1(1/ρ -1)ρ ^n n^a/
    λX^-1(n)> x)=exp (-a p_0 x),


where X^-1(n)=inf{t∈ℝ:X(t)=n} is the first time when
(X(t))_t≥ 0 visits state n∈ℕ, that is, the distribution
of ρ ^n n^a/λX^-1(n) converges to an exponential law.







[title=Acknowledgments]
We thank anonymous referees for a number of useful suggestions and remarks.


vmsta-mathphys






99




akmi

Akbash, K.S.,
Matsak, I.K.:
One improvement of the law of the iterated logarithm for the maximum
scheme. Ukr. Math. J. 64(8),
1290–1296 (2013).
doi=10.1007/s11253-013-0716-7, mr=3104866


Akbash, K.S.,
Matsak, I.K.:
One improvement of the law of the iterated logarithm for the maximum
scheme. Ukrainian Math. J. 64(8),
1290–1296 (2013). doi:10.1007/s11253-013-0716-7.
3104866

structpyb



ande

Anderson, C.W.:
Extreme value theory for a class of discrete distributions with
applications to some stochastic processes.
J. Appl. Probab. 7, 99–113 (1970).
doi=10.1017/s0021900200026978, mr=256441


Anderson, C.W.:
Extreme value theory for a class of discrete distributions with
applications to some stochastic processes.
J. Appl. Probability 7, 99–113 (1970).
doi:10.1017/s0021900200026978. 256441

structpyb



asm

Asmussen, S.:
Extreme value theory for queues via cycle maxima.
Extremes 1(2), 137–168
(1998).
doi=10.1023/A:1009970005784, mr=1814621


Asmussen, S.:
Extreme value theory for queues via cycle maxima.
Extremes 1(2), 137–168
(1998). doi:10.1023/A:1009970005784. 1814621

structpyb



BGT

Bingham, N.H.,
Goldie, C.M.,
Teugels, J.L.: Regular Variation.
Encyclopedia of Mathematics and its Applications, vol. 27,
p. 494. Cambridge University Press, Cambridge (1989).
mr=1015093


Bingham, N.H.,
Goldie, C.M.,
Teugels, J.L.: Regular Variation.
Encyclopedia of Mathematics and its Applications, vol. 27,
p. 494. Cambridge University Press, Cambridge (1989).
1015093

structpyb



bu

Buldygin, V.V.,
Klesov, O.I.,
Steinebach, J.G.:
Properties of a subclass of Avakumović functions and their
generalized inverses. Ukr. Math. J. 54(2),
149–169 (2002).
doi=10.1023/A:1020178327423, mr=1952816


Buldygin, V.V.,
Klesov, O.I.,
Steinebach, J.G.:
Properties of a subclass of Avakumović functions and their
generalized inverses. Ukraïn. Mat. Zh. 54(2),
149–169 (2002). doi:10.1023/A:1020178327423.
1952816

structpyb



coh

Cohen, J.W.:
Extreme value distribution for the M/G/1 and the G/M/1
queueing systems.
Ann. Inst. Henri Poincaré Sect. B (N.S.) 4,
83–98 (1968).
mr=0232466


Cohen, J.W.:
Extreme value distribution for the M/G/1 and the G/M/1
queueing systems.
Ann. Inst. H. Poincaré Sect. B (N.S.) 4,
83–98 (1968). 0232466

structpyb



do_m

Dovgaĭ, B.V.,
Matsak, I.K.:
Asymptotic behavior of the extreme values of the queue length in
M/M/m queuing systems. Kibern. Sist. Anal.
55(2), 171–179 (2019).
mr=3927561


Dovgaĭ, B.V.,
Matsak, I.K.:
Asymptotic behavior of the extreme values of the queue length in
M/M/m queuing systems. Kibernet. Sistem. Anal.
55(2), 171–179 (2019).
mr=3927561

structpyb



Embrechts_et_al:2013

Embrechts, P.,
Klüppelberg, C.,
Mikosch, T.:
Modelling Extremal Events: for Insurance and Finance.
Springer (2013)
doi=10.1007/978-3-642-33483-2, mr=1458613


Embrechts, P.,
Klüppelberg, C.,
Mikosch, T.:
Modelling Extremal Events: for Insurance and Finance.
Springer (2013)

structpyb



fe

Feller, W.:
An Introduction to Probability Theory and Its Applications. Vol.
II. Second edition, p. 669.
John Wiley & Sons, Inc., New York-London-Sydney (1971).
mr=0270403


Feller, W.:
An Introduction to Probability Theory and Its Applications. Vol.
II. Second edition, p. 669.
John Wiley & Sons, Inc., New York-London-Sydney (1971).
0270403

structpyb



gal

Galambos, J.:
The Asymptotic Theory of Extreme Order Statistics, p. 352.
John Wiley & Sons, New York-Chichester-Brisbane (1978).
Wiley Series in Probability and Mathematical Statistics.
mr=489334


Galambos, J.:
The Asymptotic Theory of Extreme Order Statistics, p. 352.
John Wiley & Sons, New York-Chichester-Brisbane (1978).
Wiley Series in Probability and Mathematical Statistics.
489334

structpyb



Glass

Glasserman, P.,
Kou, S.-G.:
Limits of first passage times to rare sets in regenerative processes.
Ann. Appl. Probab. 5(2), 424–445
(1995).
mr=1336877


Glasserman, P.,
Kou, S.-G.:
Limits of first passage times to rare sets in regenerative processes.
Ann. Appl. Probab. 5(2), 424–445
(1995). 1336877

structpyb



gk1

Gnedenko, B.V.,
Kovalenko, I.N.:
Introduction to Queueing Theory, 2nd edn.
Mathematical Modeling, vol. 5, p. 314.
Birkhäuser Boston, Inc., Boston, MA (1989).
doi=10.1007/978-1-4615-9826-8.
Translated from the second Russian edition by Samuel Kotz.
1035707


Gnedenko, B.V.,
Kovalenko, I.N.:
Introduction to Queueing Theory, 2nd edn.
Mathematical Modeling, vol. 5, p. 314.
Birkhäuser Boston, Inc., Boston, MA (1989). doi:10.1007/978-1-4615-9826-8.
Translated from the second Russian edition by Samuel Kotz.
1035707

structpyb



igl

Iglehart, D.L.:
Extreme values in the GI/G/1 queue.
Ann. Math. Stat. 43, 627–635
(1972).
doi=10.1214/aoms/1177692642, mr=305498


Iglehart, D.L.:
Extreme values in the GI/G/1 queue.
Ann. Math. Statist. 43, 627–635
(1972). doi:10.1214/aoms/1177692642. 305498

structpyb



kar1

Karlin, S.:
A First Course in Stochastic Processes, p. 502.
Academic Press, New York-London (1966).
mr=0208657


Karlin, S.:
A First Course in Stochastic Processes, p. 502.
Academic Press, New York-London (1966).
0208657

structpyb



kar2

Karlin, S.,
McGregor, J.:
The classification of birth and death processes.
Trans. Am. Math. Soc. 86, 366–400
(1957).
doi=10.2307/1993021, mr=94854


Karlin, S.,
McGregor, J.:
The classification of birth and death processes.
Trans. Amer. Math. Soc. 86, 366–400
(1957). doi:10.2307/1993021. 94854

structpyb



Klass1984

Klass, M.:
The minimal growth rate of partial maxima.
Ann. Probab. 12(2), 380–389
(1984)
mr=0735844


Klass, M.:
The minimal growth rate of partial maxima.
Ann. Probab. 12(2), 380–389
(1984)

structpyb



Klass1985

Klass, M.:
The Robbins–Siegmund series criterion for partial maxima.
Ann. Probab. 13(4), 1369–1370
(1985)
mr=0806233


Klass, M.:
The Robbins–Siegmund series criterion for partial maxima.
Ann. Probab. 13(4), 1369–1370
(1985)

structpyb



mi_19

Matsak, I.K.:
Limit theorem for extreme values
of discrete random variables and its application.
Teor. Imovir. Mat. Stat. 101,
189–202
(2019).


Matsak, I.K.: Limit theorem for extreme values
of discrete random variables and its application. Teor. Ĭmovīr.
Mat. Stat. In press

structpyb



Robbins+Siegmund:1972

Robbins, H.,
Siegmund, D.:
On the law of the iterated logarithm for maxima and minima. In:
Proc. 6th Berkeley Symp. Math. Stat. Prob, vol. 3,
pp. 51–70 (1972)
mr=0400364


Robbins, H.,
Siegmund, D.:
On the law of the iterated logarithm for maxima and minima. In:
Proc. 6th Berkeley Symp. Math. Stat. Prob, vol. 3,
pp. 51–70 (1972)

structpyb



serf

Serfozo, R.F.:
Extreme values of birth and death processes and queues.
Stoch. Process. Appl. 27(2),
291–306 (1988).
doi=10.1016/0304-
4149(87)90043-3,
mr=931033


Serfozo, R.F.:
Extreme values of birth and death processes and queues.
Stochastic Process. Appl. 27(2),
291–306 (1988). doi:10.1016/0304-4149(87)90043-3.
931033

structpyb



ks

Smith, W.L.:
Renewal theory and its ramifications.
J. R. Stat. Soc. Ser. B 20, 243–302
(1958).
mr=99090


Smith, W.L.:
Renewal theory and its ramifications.
J. Roy. Statist. Soc. Ser. B 20, 243–302
(1958). 99090

structpyb



ok_ik

Zakusilo, O.K.,
Matsak, I.K.:
On the extreme values of some regenerative processes.
Teor. Imovir. Mat. Stat. 97,
58–71
(2017).
doi=10.1090/tpms/1048, mr=3745999


Zakusilo, O.K.,
Matsak, I.K.: On the extreme values of some regenerative
processes. Teor. Ĭmovīr. Mat. Stat. (97), 58–71 (2017). doi:10.1090/tpms/1048.
3745999

structpyb





