MSTA Modern Stochastics: Theory and Applications 2351-6054 2351-6046 2351-6046 VTeXMokslininkų g. 2A, 08412 Vilnius, Lithuania MSTA147 10.15559/20-MSTA147 Research Article The laws of iterated and triple logarithms for extreme values of regenerative processes MarynychAlexandermarynych@unicyb.kiev.ua∗ MatsakIvanivanmatsak@univ.kiev.ua Taras Shevchenko National University of Kyiv, Faculty of Computer Science and Cybernetics, 01601 Kyiv, Ukraine Corresponding author. 2020 1722020716178 1112020 122020 122020 © 2020 The Author(s). Published by VTeX2020 Open access article under the CC BY license.

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 60G70 60F15 60K25 Introduction and main results

Various problems related to asymptotic behavior of extreme values of regenerative processes is of considerable practical interest and has attracted a lot of attention in probabilistic community. For example, extremes in queuing systems and of birth and death processes have been investigated in [2, 3, 6, 13, 20], 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 [3]. In recent paper [22] a slightly different approach to the asymptotic analysis of extreme values of regenerative 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. In this article instead, we are interested in almost sure (a.s.) behavior of general regenerative processes and in particular of regenerative processes appearing in queuing and birth–death systems. Our main results formulated in Theorems 1 and 2 below provide the laws of iterated and triple logarithms for the running maximum of 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 process over its regeneration cycle has an exponential tail, this type of behavior has already been observed in [11], see Proposition 3.2 therein. Our theorems provide a generalization of the aforementioned result and cover, for example, regenerative processes with Weibull-like tails of the maximum over a regeneration cycle. As in many other papers dealing with extremes of regenerative processes, 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 [16, 17, 19] dealing with a.s. growth rate of the running maximum, see Section 3.5 in [8] for a survey.

Before formulating the results we introduce necessary definitions. Let us recall, see [4], that a positive measurable function U defined in some neighbourhood of +∞ is called regularly varying at +∞ with index κ∈R if U(x)=xκV(x) , and the function V is slowly varying at +∞ , that is limt→+∞V(tx)V(t)=1for allx>0. 0.\]]]>

Given a function H:R→R we denote by H−1 its generalized inverse defined by H−1(y)=infx∈R:H(x)>y,y∈R. y\right\},\hspace{1em}y\in \mathbb{R}.\]]]>

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

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

limx→+∞H(x)=+∞ ;

the function H is eventually nondecreasing and differentiable;

the derivative h(x):=H′(x) is such that for some κ∈R the function hˆ(x)=(H−1(x))′=1h(H−1(x)),x∈R, is regularly varying at +∞ with index κ.

Note that the assumption of regular variation of hˆ implies that h is eventually positive. Thus, H is eventually strictly increasing and the generalized inverse H−1 defined by (1) eventually coincides with the usual inverse.

Let X=(X(t))t≥0 be a regenerative random process, that is, X(t)=ξk(t−Sk−1)fort∈[Sk−1,Sk),k∈N, where S0=0,Sk=T1+⋯+Tk,k∈N, and (Tk,ξk(·))k∈N is a sequence of independent copies of a pair (T,ξ(·)) , see, for example, [21, Part II, Chapter 2] and [9, Chapter 11, §8]. The points (Sk) are called regeneration epochs and the interval [Sk−1,Sk) is the k-th period of regeneration.

For t≥0 , put X¯(t)=sup0≤s<tX(s), and note that X¯(T1) is the maximum of the process X on the first period of regeneration. Let F be the distribution function of X¯(T1) , that is, F(x):=P(X¯(T1)≤x). Put R(x):=−log(1−F(x)),x∈R, and αT=ET1=ET. Note also that it is always possible to write a decomposition R(x)=R0(x)+R1(x),x∈R, where |R1(x)|≤C1<∞,x∈R. Here and hereafter we denote by C,C1,C2 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. Assume that there exists a decomposition (2) such that (3) holds and the function R0 satisfies condition (U) . Suppose further that αT<∞ . For large enough x∈R , let r0 be the derivative of R0 . Then lim supt→∞r0(A0(t))(X¯(t)−A0(t))L2(t)=1a.s., and lim inft→∞r0(A0(t))(X¯(t)−A0(t))L3(t)=−1a.s., where A0(t)=R0−1logtαT,L2(t)=loglogt,L3(t)=logloglogt.

Our next result is a counterpart of Theorem 1 for discrete processes taking values in some lattice in R . Such processes are important, among other fields, in the queuing theory. Assume that P(X(t)∈{0,1,2,3,…})=1,t≥0, and, for k=0,1,2,3,… , put Rk:=−logP(X¯(T1)>k). k).\]]]> Similarly to (2) and (3) we can write a decomposition Rk=R0(k)+R1(k),k=0,1,2,3,…, where R0:R→R and R1:R→R are real-valued functions and R1 is such that |R1(k)|≤C1<∞,k=0,1,2,3,….

Let (X(t))t≥0 be a regenerative random process such that (6) holds. Assume that there exists a decomposition (7) such that (8) is fulfilled and the function R0 satisfies condition (U) . Suppose also that αT<∞ .

The asymptotic relation r0(R0−1(x))=o(logx),x→∞, entails lim supt→∞r0(A0(t))(X¯(t)−A0(t))L2(t)=1a.s.

The asymptotic relation r0(R0−1(x))=o(loglogx),x→∞, entails lim inft→∞r0(A0(t))(X¯(t)−A0(t))L3(t)=−1a.s. The functions A0 and r0 were defined in Theorem 1.

In the discrete setting we assume that there exist extensions of the sequences (R0(k)) and (R1(k)) to functions defined on the whole real line with the extension of R0 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 U .

The article is organized as follows. In Section 2 we collect and prove some auxiliary results needed in the proofs of our main theorems. They are given in Section 3. In Section 4 we apply Theorems 1 and 2 to some queuing systems and birth–death processes.

 Preliminaries

Let us consider a sequence (ξk)k∈N of independent copies of a random variable ξ with the distribution function Fξ(x)=P(ξ≤x)=:1−exp(−Rξ(x)) . Put zn=max1≤i≤nξi.

The following result was proved in [1], see Theorem 1 therein.

Assume that the distribution of ξ is such that Rξ satisfies condition (U) . With a(n)=Rξ−1(logn) it holds lim supn→∞rξ(a(n))(zn−a(n))L2(n)=1a.s., and lim infn→∞rξ(a(n))(zn−a(n))L3(n)=−1a.s., where, for large enough x∈R , rξ(x):=Rξ′(x)=Fξ′(x)1−Fξ′(x).

The proof of Lemma 1, given in [1], consists of two steps. Firstly, the claim is established for the standard exponential distribution τe , that is, assuming P(ξ≤x)=P(τ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ξandRξ−1(zne)=dzn. Here and hereafter zne=max1≤i≤nτie and (τie)i∈N are independent copies of τe .

We need the following generalization of Lemma 1.

Assume that the law of ξ is such that the function Rξ possesses a decomposition (2) with R1 satisfying (3) and R0 satisfying condition (U) . Then lim supn→∞r0(a0(n))(zn−a0(n))L2(n)=1a.s., and lim infn→∞r0(a0(n))(zn−a0(n))L3(n)=−1a.s., where a0(n)=R0−1(logn) and r0(x)=R0′(x) .

To prove Lemma 2 we need the following simple result, see Theorem 3.1 in [5].

Let H be a function regularly varying at +∞ and let (cn)n∈N and (dn)n∈N be two sequences of real numbers such that limn→∞cn=+∞ , limn→∞cn/dn=1 . Then limn→∞H(cn)H(dn)=1.

Fix a sequence of standard exponential random variables (τie)i∈N and assume without loss of generality that the sequence (zn)n∈N is constructed from (τie)i∈N via formula (16). The subsequent proof is divided into two steps.

Step 1. Suppose additionally that the function R0 is everywhere nondecreasing, differentiable, and R0(−∞)=0 . Then F0(x):=1−exp(−R0(x)) is a distribution function. Put ξi′=R0−1(τie) for i∈N and let zn′=max1≤i≤nξi′ . From Lemma 1 we infer lim supn→∞r0(a0(n))(zn′−a0(n))L2(n)=1a.s. Let C1 be a constant such that (3) holds. From the definition of the function Rξ−1 and decomposition (2) we obtain R0−1(x−C1)≤Rξ−1(x)≤R0−1(x+C1),x∈R, and thereupon R0−1(zne−C1)≤Rξ−1(zne)≤R0−1(zne+C1). Hence, by monotonicity of R0−1 , we have |Rξ−1(zne)−R0−1(zne)|≤R0−1(zne+C1)−R0−1(zne−C1)=2C1rˆ0(zne+C1(2θn−1)), where the equality follows from the mean value theorem for differentiable functions, rˆ0(x)=(R0−1(x))′ and 0≤θn≤1 .

It is known, see [10, Chapter 4, Example 4.3.3], that limn→∞znelogn=1a.s. Thus, from Lemma 3 we deduce limn→∞rˆ0(zne+C1(2θn−1))rˆ0(logn)=1a.s. In conjunction with (20) this yields |Rξ−1(zne)−R0−1(zne)|≤2C1rˆ0(logn)(1+o(1))=2C1r0(a0(n))(1+o(1)). Taking together relations (19), (21) we arrive at (17).

Similarly, from Lemma 1 we have lim infn→∞r0(a0(n))(zn′−a0(n))L3(n)=−1a.s. Therefore, (18) follows from (22) and (21).

Step 2. Let us now turn to the general case where the function R0 is nondecreasing and differentiable on some interval [x0,∞) with x0>0 0$]]>. Recall decomposition (2). Let R˜0:R→R and R˜1:R→R be arbitrary nondecreasing differentiable functions such that R˜0(x)=R0(x)andR˜1(x)=R1(x)forx≥x0,R˜0(x)=R˜1(x)=0forx≤0. Put R˜(x):=R˜0(x)+R˜1(x),x∈R. The functions R˜0 , R˜1 and R˜ satisfy all the assumptions of Step 1. Thus, if we set ξ˜i=R˜−1(τie),z˜n=max1≤i≤nξ˜i, then the sequence (z˜n)n∈N satisfies (17) and (18) with the same normalizing functions r0(a0(n)) and a0(n) . The latter holds true since for sufficiently large x>0 0$]]> we have R˜0−1(x)=R0−1(x) .

It remains to note that the asymptotics of (z˜n) and (zn) are the same. Indeed, set n0:=min(i≥1:τie≥y0), where y0:=R(x0)=R˜(x0) . Then zn=z˜n for n≥n0 and we see that both (17) and (18) hold for (zn) as well. This finishes the proof of Lemma 3.  □

The next lemma is a counterpart of Lemma 2 for discrete distributions. Assume that ξ has distribution P(ξ=k)=pk, where pk≥0 and ∑k=0∞pk=1 . Put q(k)=∑i>kpi=exp(−Rξ,k). k}{p_{i}}=\exp (-{R_{\xi ,k}}).\]]]>

Let ξ be a random variable taking values in {0,1,2,3,…} and let Rξ,k be such that there exists a decomposition (7) with R1 satisfying (8) and R0 satisfying condition (U) .

if (9) holds, then (zn) satisfies equality (17);

if (11) holds, then (zn) also satisfies (18).

Similarly to Lemma 2 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′=R0−1(τie) for i∈N . Note that ξi′ are i.i.d. with the distribution function F0(x)=1−exp(−R0(x)) . Thus, for zn′=max1≤i≤nξi′ , equality (19) holds.

Let us consider ⌈Rξ,k−1(y)⌉=infk=0,1,2,3,…:Rξ,k≥y, then |Rξ,k−1(y)−⌈Rξ,k−1(y)⌉|≤1, for all y∈R , and therefore |Rξ,k−1(zne)−⌈Rξ,k−1(zne)⌉|≤1,|R0−1(zne)−⌈R0−1(zne)⌉|≤1. Further, condition (8) and monotonicity of the function ⌈·⌉ both imply ⌈R0−1(zne−C1)⌉≤⌈Rξ,k−1(zne)⌉≤⌈R0−1(zne+C1)⌉. Combining the above estimates, we derive R0−1(zne−C1)−2≤Rξ,k−1(zne)≤R0−1(zne+C1)+2. This means |Rξ,k−1(zne)−R0−1(zne)|≤R0−1(zne+C1)−R0−1(zne−C1)+4≤2C1r0(a0(n))(1+o(1))+4, see estimates (20), (21).

Assuming (9) we see that (17) holds. Similarly, condition (11) yields (18).  □

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

For arbitrary p>1 1$]]> and b∈R it holds Λn:= ∑k=1npkkb=pn+1(p−1)nb(1+o(1)),n→∞.

By the Stolz–Cesáro theorem we have limn→∞(p−1)nbΛnpn+1=limn→∞Λn−Λn−1pn+1(p−1)nb−pn(p−1)(n−1)b=limn→∞pnnbpn+1(p−1)nb−pn(p−1)(n−1)b=limn→∞p−1p−nb(n−1)b=1. The proof is complete.  □

 Proofs of Theorems <xref rid="j_vmsta147_stat_002">1</xref> and <xref rid="j_vmsta147_stat_003">2</xref>

Let us start with a proof of equality (4). To this end, we introduce the following notation Yk=supSk−1≤t<SkX(t),Zn=max1≤k≤nYk,k∈N. Since (Sk) are the moments of regeneration of the process (X(t))t≥0 , (Yk) are i.i.d. random variables. Furthermore, it is clear that the sequence (Yk) satisfies conditions of Lemma 2. Therefore, lim supn→∞r0(a0(n))(Zn−a0(n))L2(n)=1a.s. Denote by N the counting process for the sequence (Sk) , that is, N(t)=max{k≥0:Sk≤t},t≥0. Since limt→∞N(t)=+∞ a.s. and N(t) runs through all positive integers, from (25) we obtain lim supt→∞r0(R0−1(logN(t)))(ZN(t)−R0−1(logN(t)))L2(N(t))=1a.s. By the strong law of large numbers for N we have limt→∞N(t)t=1αTa.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 (26), we obtain lim supt→∞r0(R0−1(logtαT+o(1)))(ZN(t)−R0−1(logtαT+o(1)))L2(tαT(1+o(1)))=1a.s. Further, by the slow variation of L2 we can replace the denominator in (28) by L2(t) .

Let us recall that under the assumptions of Theorem 1, the function rˆ0(x)=(R0−1(x))′ is regularly varying at infinity. So using once again Lemma 3, we obtain the equalities rˆ0(logtαT+o(1))=rˆ0(logtαT)(1+o(1))=1+o(1)r0(R0−1(logtαT)),t→∞, and R0−1(logtαT+o(1))−R0−1(logtαT)=o(1)rˆ0(logtαT+o(1)),t→∞. Combining the above relations, from (28) we derive lim supt→∞r0(A0(t))(ZN(t)−A0(t))L2(t)=1a.s., with A0(t) and r0(t) as in Theorem 1. The same argument with N(t) replaced by N(t)+1 yields lim supt→∞r0(A0(t))(ZN(t)+1−A0(t))L2(t)=1a.s. It remains to note that ZN(t)≤X¯(t)≤ZN(t)+1a.s. Summarizing this gives equality (4). The proof of the relation (5) utilizes equality (18) of Lemma 2 and is similar. We omit the details.  □

The derivation of Theorem 2 is based on Lemma 4 and basically repeats the proof of Theorem 1. We leave the details to a reader.

Suppose that under the assumptions of Theorem 1 the parameter t runs over a countable set t∈T:={t0=0<t1<t2<⋯} such that limi→∞ti=+∞ as i→∞ . The set T can be random and the process X can depend on T . Assume that P(Si∈T)=1 for all i∈N .

Put Xi:=X(ti) and X¯n=max0≤i≤nXi . Assume that extreme values of the process X are attained at the points of the set T . More precisely, for all t≥0 , sup0≤s≤tX(s)=max0≤ti≤tXia.s.

In what follows the next proposition will be useful.

Under the assumptions of Theorem 1 suppose that there exists a set T such that condition (30) holds and, further, limn→∞tnn=αa.s. Then lim supt→∞r0(A(n))(X¯n−A(n))L2(n)=1a.s., and lim infn→∞r0(A(n))(X¯n−A(n))L3(n)=−1a.s., where A(n)=R0−1logαnαT.

A proof given below is similar to the proof of Theorem 1. From equations (27) and (31) we obtain, as n→∞ , N(tn)n=N(tn)tntnn→ααTa.s. Further, replacing n by N(tn) in equality (25), which is possible because N(tn) diverges to infinity through all positive integers, we get lim supn→∞r0(R0−1(logN(tn)))(ZN(tn)−R0−1(logN(tn)))L2(N(tn))=1a.s. Directly from (30) we derive ZN(tn)≤X¯n≤ZN(tn)+1a.s. These inequalities and relations (34), (35) yield equality (32). The same argument can be applied for proving (33).  □

 Applications (Queuing system <inline-formula id="j_vmsta147_ineq_154"><alternatives> <mml:math><mml:mi mathvariant="italic">G</mml:mi><mml:mi mathvariant="italic">I</mml:mi><mml:mo mathvariant="normal" stretchy="false">/</mml:mo><mml:mi mathvariant="italic">G</mml:mi><mml:mo mathvariant="normal" stretchy="false">/</mml:mo><mml:mn>1</mml:mn></mml:math> <tex-math><![CDATA[$GI/G/1$]]></tex-math></alternatives></inline-formula>).

Let us consider a single-channel queuing system with customers arriving at 0=t0<t1<t2<⋯<ti<⋯ . Let 0=W0,W1,W2,…,Wi,… 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=ti−ti−1 , for i∈N , the interarrival times between successive customers, and ηi , i∈N , is the service time of the i-th customer. Suppose that (ζi) and (ηi) are independent sequences of i.i.d. random variables. In the standard notation, this queuing system has the type GI/G/1 , see [12, 14].

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:tk≤t), and W(tn)=W(tn+)=Wn. Set W¯(t)=sup0≤s≤tW(s)=max0≤tk≤tWk, then W¯n=max1≤i≤nWi=W¯(tn). Denote Eζi=a , Eηi=b and assume that both expectations are finite. Further, we impose the following conditions on ζi and ηi : ρ:=ba<1 and for some γ>0 0$]]>, it holds Eexp(γ(ηi−ζi))=1,E(ηi−ζi)exp(γ(ηi−ζi))<∞. Under these assumptions the evolution of the queuing 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 (Sk) of the process W as follows: S0=0 and, for i∈N , Si is the arrival time of a new customer at the end of i-th idle period. Let Ti be the duration of the i-th regeneration cycle, and W¯(T1) be the maximum waiting time during the first regeneration cycle. It is known, see [3] and [13], that under conditions (36) and (37), we have P(W¯(T1)>x)=(C+o(1))exp(−γx),x→∞. x)=(C+o(1))\exp (-\gamma x),\hspace{1em}x\to \infty .\]]]> Condition (36) also guarantees that the average duration of the i-th regeneration cycle is finite, that is, αT=ETi<∞ , see [14, Chapter 14, §3, Theorem 3.2].

Thus, if we set X(t)=W(t) , R0(x)=γx , R1(x)=logC+o(1) and r0(x)=γ , then from Theorem 1 and Proposition 1 we derive the corollary.

Assume that the queuing system GI/G/1 satisfies conditions (36) and (37). Then lim supt→∞γW¯(t)−logtL2(t)=lim supn→∞γW¯n−lognL2(n)=1a.s., and lim inft→∞γW¯(t)−logtL3(t)=lim infn→∞γW¯n−lognL3(n)=−1a.s.

Suppose that P(ζi≤x)=1−exp(−λx),P(ηi≤x)=1−exp(−μx),x≥0, that is, we consider the queuing system M/M/1 . Assume further, that ρ:=λ/μ<1 . It is easy to check that conditions (36) and (37) are fulfilled, and therefore equalities (38) and (39) hold with γ=μ−λ=μ(1−ρ) .

Suppose that P(ζi≤x)=1−exp(−λx),x≥0, and P(ηi=const=d)=1 . Assume further, that ρ:=λd<1 . Then relations (36)–(39) hold with γ=xρ/d , with xρ>0 0$]]> being the unique positive root of the equation ex=1+xρ.

(Queuing system <inline-formula id="j_vmsta147_ineq_191"><alternatives> <mml:math><mml:mi mathvariant="italic">M</mml:mi><mml:mo mathvariant="normal" stretchy="false">/</mml:mo><mml:mi mathvariant="italic">M</mml:mi><mml:mo mathvariant="normal" stretchy="false">/</mml:mo><mml:mi mathvariant="italic">m</mml:mi></mml:math> <tex-math><![CDATA[$M/M/m$]]></tex-math></alternatives></inline-formula>).

Let us now consider a queuing 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 P(η≤x)=1−exp(−μx),x≥0. In the standard notation, this queuing system has the type M/M/m , see [12, 14].

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)=sup0≤s<tQ(s),t≥0. In the same way as in Example 1, one can introduce regeneration moments (Sk) for the process Q: S0:=0 and, for i∈N , Si is the arrival time of a new customer after the i-th busy period. Let Ti be the duration of the i-th regeneration cycle and Q¯(T1) be the maximum length of the queue in the first regeneration cycle. Put P(Q¯(T1)>x)=exp(−R(x)). x)=\exp (-R(x)).\]]]> In recent paper [7] the authors established that function R in (41) satisfies conditions (7) and (8) with R0(x)=−xlogρ,r0(x)=−logρ. Using Theorem 2 we infer

Assume that for a queuing system M/M/m , 1≤m<∞ , the condition (40) is fulfilled. Then lim supt→∞Q¯(t)log1ρ−logtL2(t)=1a.s., and lim inft→∞Q¯(t)log1ρ−logtL3(t)=−1,a.s.

Relations (42) and (43) have been proved in [7] by direct calculations. Let us note that in case m=∞ , which has also been treated in [7], the asymptotics of Q¯(t) is of completely different form, see also [18].

(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,…, 0,\hspace{2.5pt}n=0,1,2,\dots ,\]]]> see [14, Ch. 7, §6 ]. 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=1kλi−1μi,k∈N. It is not difficult to check that condition (45) ensures ∑k≥1θk<∞, and ∑k≥11λkθk=∞. Under conditions (46) and (47), see [14] and [15], there exists a stationary regime, that is, limt→∞P(X(t)=k)=pk, with pk=θkp0,k=0,1,2,3,…,wherep0=( ∑k=0∞θk)−1.

Further, X is a regenerative process with regeneration moments (Sk) , where S0=0 and Si , i∈N , is the moment of i-th return to state 0. It is known that ETk=1(λ0+μ0)p0=1ap0, where Tk=Sk−Sk−1 is the duration of the k-th regeneration cycle, see Eq. (32) in [22]. If (45) holds, then M(t):=EX(t)→aμ−λ,t→∞, see [14]. We are interested in the asymptotic behavior of extreme values X¯(t)=sup0≤s<tX(s),t≥0. Let us show how to apply Theorem 2 to the asymptotic analysis of X¯(t) . Firstly, we need to evaluate accurately the sequence (R(n)) defined by q(n):=P(X¯(T1)>n)=exp(−R(n)). n)=\exp (-R(n)).\]]]> It is known, see [3] or Eq. (34) in [22], that q(n)=1∑k=0nαk, where α0=1 and αk=∏i=1kμiλi for k∈N .

Using equalities (44) and (45) we can rewrite αk as follows: αk=βkρk,βk= ∏i=1k1−11+iλ/a. Further, using Taylor’s expansion log(1+x)=x−x22+x33−⋯,|x|<1, we have logβk= ∑i=1klog1−11+iλ/a=− ∑i=1k11+iλ/a+dk, where dk has a finite limit, as k→∞ . Combining the relation ∑i=1k11+iλ/a− ∑i=1k1iλ/a= ∑i=1kaλi(1+iλ/a)=C1+o(1),k→∞, and the fact limn→∞ ∑i=1n1i−logn=γ, with γ=0.577… being the Euler–Mascheroni constant, we conclude ∑i=1klog1−11+iλ/a=−aλlogk+C2+o(1),k→∞. Therefore, βk=Ck−a/λ(1+o(1)), where C=eC2:=limn→∞na/λ ∏i=1n(1−11+iλ/a). Now we can apply Lemma 5 to obtain Λn= ∑k=1nρ−kka/λ=ρ−n−1(1ρ−1)na/λ(1+o(1)),n→∞. Taking into account equality (54), we obtain ∑k=0nαk=Cρ−n−1(1/ρ−1)na/λ(1+o(1)),n→∞. Thus, q(n)=1/ρ−1Cρn+1na/λ(1+o(1)),n→∞, and we have the following representation R(n)=−logq(n)=R0(n)+R1(n), where R0(n)=−nlogρ−aλlogn,R1(n)=−log1/ρ−1C−logρ+o(1),n→∞. The function R0(x)=−xlogρ−aλlogx is increasing for x≥x0=−aλlogρ and, furthermore, satisfies condition (U) .

Since r0(x)=−logρ−aλx , conditions (9), (11) of Theorem 2 hold.

It remains to find a simple formula for the function A0 in (10) and (12). To this end, let us write logtαT=R0(A0(t))=−A0(t)logρ−aλlogA0(t)=A0(t)−logρ+o(1), as t→∞ . Upon taking logarithms we get logA0(t)=loglogtαT+O(1),t→∞, and plugging this back into the initial equality yields A0(t)=logt+aλL2(t)+O(1)−logρ. Thus, from Theorem 2 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 0$]]>, n=0,1,2,3,… . Suppose also that (45) holds. Then lim supt→∞X¯(t)log1ρ−logtL2(t)=1+aλ,a.s., and lim inft→∞X¯(t)log1ρ−logt−aλL2(t)L3(t)=−1,a.s.

It is clear from the above calculations that the condition X(0)=0 can be removed, that is, equations (57) and (58) 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 (48), (56) and Theorem 2 in [22].

Let (X(t))t≥0 be the birth and death process that satisfies all conditions of Corollary 3. Then limn→∞P(X¯(tn∗)≥n)=1−exp(−ap0x),x>0, 0,\]]]> where tn∗=Cρ−nn−a/λx/(1/ρ−1) , while p0 and C are defined by (48) and (55). This relation can also be recast in a more transparent way as follows: limn→∞P(C−1(1/ρ−1)ρnna/λX−1(n)>x)=exp(−ap0x), x)=\exp (-a{p_{0}}x),\]]]> where X−1(n)=inf{t∈R:X(t)=n} is the first time when (X(t))t≥0 visits state n∈N , that is, the distribution of ρnna/λX−1(n) converges to an exponential law.

 Acknowledgments

We thank anonymous referees for a number of useful suggestions and remarks.

 References 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). MR3104866. https://doi.org/10.1007/s11253-013-0716-7 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). MR256441. https://doi.org/10.1017/s0021900200026978 Asmussen, S.: Extreme value theory for queues via cycle maxima. Extremes 1(2), 137–168 (1998). MR1814621. https://doi.org/10.1023/A:1009970005784 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). MR1015093 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). MR1952816. https://doi.org/10.1023/A:1020178327423 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). MR0232466 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). MR3927561 Embrechts, P., Klüppelberg, C., Mikosch, T.: Modelling Extremal Events: for Insurance and Finance. Springer (2013) MR1458613. https://doi.org/10.1007/978-3-642-33483-2 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). MR0270403 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. MR489334 Glasserman, P., Kou, S.-G.: Limits of first passage times to rare sets in regenerative processes. Ann. Appl. Probab. 5(2), 424–445 (1995). MR1336877 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). https://doi.org/10.1007/978-1-4615-9826-8. Translated from the second Russian edition by Samuel Kotz. MR1035707 Iglehart, D.L.: Extreme values in the GI/G/1 queue. Ann. Math. Stat. 43, 627–635 (1972). MR305498. https://doi.org/10.1214/aoms/1177692642 Karlin, S.: A First Course in Stochastic Processes, p. 502. Academic Press, New York-London (1966). MR0208657 Karlin, S., McGregor, J.: The classification of birth and death processes. Trans. Am. Math. Soc. 86, 366–400 (1957). MR94854. https://doi.org/10.2307/1993021 Klass, M.: The minimal growth rate of partial maxima. Ann. Probab. 12(2), 380–389 (1984) MR0735844 Klass, M.: The Robbins–Siegmund series criterion for partial maxima. Ann. Probab. 13(4), 1369–1370 (1985) MR0806233 Matsak, I.K.: Limit theorem for extreme values of discrete random variables and its application. Teor. Imovir. Mat. Stat. 101, 189–202 (2019). 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) MR0400364 Serfozo, R.F.: Extreme values of birth and death processes and queues. Stoch. Process. Appl. 27(2), 291–306 (1988). MR931033. https://doi.org/10.1016/0304-4149(87)90043-3 Smith, W.L.: Renewal theory and its ramifications. J. R. Stat. Soc. Ser. B 20, 243–302 (1958). MR99090 Zakusilo, O.K., Matsak, I.K.: On the extreme values of some regenerative processes. Teor. Imovir. Mat. Stat. 97, 58–71 (2017). MR3745999. https://doi.org/10.1090/tpms/1048