Abstract
Stochastic networks with complex structures are key modelling tools for many important applications. In this paper, we consider a specific type of network: retrial queueing systems with priority. This type of queueing system is important in various applications, including telecommunication and computer management networks with big data. The system considered here receives two types of customers, of which Type-1 customers (in a queue) have non-pre-emptive priority to receive service over Type-2 customers (in an orbit). For this type of system, we propose an exhaustive version of the stochastic decomposition approach, which is one of the main contributions made in this paper, for the purpose of studying asymptotic behaviour of the tail probability of the number of customers in the steady state for this retrial queue with two types of customers. Under the assumption that the service times of Type-1 customers have a regularly varying tail and the service times of Type-2 customers have a tail lighter than Type-1 customers, we obtain tail asymptotic properties for the numbers of customers in the queue and in the orbit, respectively, conditioning on the server’s status, in terms of the exhaustive stochastic decomposition results. These tail asymptotic results are new, which is another main contribution made in this paper. Tail asymptotic properties are very important, not only on their own merits but also often as key tools for approximating performance metrics and constructing numerical algorithms.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Rapid advances in the fields of computer and communication technologies, with fast increasing internet, big data and smartphone applications, have significantly changed every aspect of our life. These accelerated developments have continuously raised new challenges in modelling, performance analysis, system control and optimization, such as those for queueing systems, including priority retrial queues (see, for example, Sutton and Jordan [33], Dimitriou [9], Phung-Duc [32], Walraevens, Claeys and Phung-Duc [34] among others). As a consequence of these challenges, the resulting stochastic models become progressively more complex, due to, for example, dependence structures, dimensions and the size of the data involved. For such networks, non-transformation exact solutions are hardly seen, whereas asymptotic behaviours and properties are among the key candidates that we search for.
In this paper, we consider a single-server retrial queue with two types of customers (Type-1 and Type-2), denoted by \(M_1,M_2/G_1,G_2/1\). This model was studied by Falin, Artalejo and Martin in [14]. In this model, customers arrive according to a Poisson process at rate \(\lambda >0\) and with probabilities \(q\in (0,1)\) and \(p=1-q\) to be Type-1 and Type-2, respectively. In other words, Type-1 and Type-2 customers form two independent Poisson arrival processes with rates \(\lambda _1\equiv \lambda q\) and \(\lambda _2\equiv \lambda p\), respectively. If the server is idle upon the arrival of a Type-1 or Type-2 customer, the customer receives the service immediately and leaves the system after the completion of the service. If an arriving Type-1 customer finds the server busy, it joins the priority queue with an infinite waiting capacity. If a Type-2 customer finds the server busy upon arrival, it enters the orbit and makes retrial attempts later for receiving a service. Each of the Type-2 customers in the orbit repeatedly tries, independently, to receive service according to a Poisson process with a common retrial rate \(\mu \) until it finds the server idle, and receives its service immediately. Type-1 customers have non-preemptive priority to receive service over Type-2 customers. Thus, as long as the priority queue is not empty, all retrials by Type-2 customers from the orbit are blocked (or failed), and all blocked Type-2 customers return to the orbit with probability one. Each Type-i customer, \(i=1,2\), has service time \(T_{\beta _i}\), whose common probability distribution is \(F_{\beta _i}(x)\) with \(F_{\beta _i}(0)=0\), and all service times are independent, and are assumed to be independent of the arrivals. \(T_{\beta _i}\) is assumed to have a finite mean \(\beta _{i,1}\), \(i=1,2\), where the second subscript is used to indicate the first moment of the service time. The Laplace–Stieltjes transforms (LST) of the distribution function \(F_{\beta _i}(x)\) is denoted by \(\beta _i(s)\), \(i=1,2\). Let \(\rho _1=\lambda _1\beta _{1,1}\), \(\rho _2=\lambda _2\beta _{2,1}\) and \(\rho =\rho _1+\rho _2=\lambda (q\beta _{1,1}+p\beta _{2,1})\). It follows from [14] that this system is stable if and only if \(\rho <1\). We assume that \(\rho <1\) throughout this paper. For the service times \(T_{\beta _i}\) of Type-i customers, \(i=1,2\), we make the following assumptions:
- A1.:
-
\(T_{\beta _1}\) has tail probability \(P\{T_{\beta _1}>t\} \sim t^{-a_1}L(t)\) as \(t\rightarrow \infty \), where \(a_1>1\);
- A2.:
-
\(T_{\beta _2}\) has tail probability \(P\{T_{\beta _2}>t\} \sim e^{-r t} t^{-a_2} L(t)\) as \(t\rightarrow \infty \), where \(-\infty<a_2<\infty \) if \(r > 0\), or \(a_2>a_1\) if \(r=0\).
Here, L(t) represents a slowly varying function at \(\infty \) (see Definition A.1).
There are many references in the literature for asymptotic analysis for queues without retrials, for example, Asmussen, Klüppelberg and Sigman [3], Boxma and Denisov [6], and more references can be found in two excellent surveys: Borst et al. [5] and Boxma and Zwart [7]. Concerning retrial queues, we refer readers to the following books or review articles for an updated status of studies and for more references therein: Falin [13], Artalejo and Gómez-Corral [2], Kim and Kim [21] and Phung-Duc [32]. We also mention here the following two references, which are closely related to the study in this paper: Kim, Kim and Ko [23] and Kim, Kim and Kim [22]. Priority retrial queueing systems are a type of very important retrial queues, which find many applications, for example, in computer network management and telecommunication systems. In such systems, there are usually two or more types of customers. A survey of studies on single-server retrial queues with priority calls (or customers), published in 1999, can be found in Choi and Chang [8]. Since then, more publications on priority retrial queues became available, such as Artalejo, Dudin and Klimenok [1], Lee [24], Gómea-Corral [19], Wang [35], Dimitriou [9], Wu and Lian [36], Wu, Wang and Liu [37], Gao [18], Dudin et al. [11], Walraevens, Claeys and Phung-Duc [34] (who, assuming \(F_{\beta _1}(x)=F_{\beta _2}(x)\), considered special situations of the model studied in this paper using a different method), among possible others. Readers may refer to [9, 37] for more detailed reviews of the above-mentioned studies.
Different from the above-mentioned studies, our focus in this paper is on the heavy-tailed behaviour of stationary (conditional) probabilities. Specifically, under the assumptions that the tail probability of the service time for Type-1 customers is regularly varying and the tail probability of the service time for Type-2 customers is lighter than that for Type-1 customers (see Assumptions A1 and A2), we characterize the tail asymptotic behaviour for the following key system performance metrics:
- PO-0:
-
Conditional tail probability of the number of customers in the orbit given that the server is idle;
- PO-1:
-
Conditional tail probability of the number of customers in the orbit given that the server is serving a Type-1 customer;
- PO-2:
-
Conditional tail probability of the number of customers in the orbit given that the server is serving a Type-2 customer;
- PQ-1:
-
Conditional tail probability of the number of customers in the queue given that the server is serving a Type-1 customer;
- PQ-2:
-
Conditional tail probability of the number of customers in the queue given that the server is serving a Type-2 customer.
We did not include the conditional probability of the number of customers in the queue given that the server is idle, since the queue is obviously empty when the server is idle. The tail asymptotic behaviour is one of the key subjects in applied probability. It is also very useful in approximations and computations, such as providing performance metrics and developing numerical algorithms (see Liu and Zhao [26] for some of its applications).
The main contributions made in this paper are twofold:
(1) The proposal of an exhaustive stochastic decomposition approach for complicated probability generating functions (PGFs), or transformations in general, of a probability distribution. This approach decomposes a complicated PGF into a product of PGFs, or equivalently decomposes a r.v. into a sum of independent r.v.s, called independent components, to which detailed probabilistic interpretations are provided. We refer to this extended version of stochastic decompositions as the exhaustive stochastic decomposition approach. This exhaustive version of the stochastic decomposition is an extension of the idea presented in the literature; for example, see Liu, Wang and Zhao [29]. This paper is one of the sister papers (see Liu, Min and Zhao [25] and Liu and Zhao [27, 28]) demonstrating the usefulness of the exhaustive decomposition approach to different types of queueing models.
Stochastic decomposition has been widely used in queueing system analysis. For example, it is well known that for the M/G/1 retrial queue, one can stochastically decompose the total number of customers in the system as the independent sum of the total number of customers in the corresponding standard M/G/1 queueing system (without retrials) and another random variable (r.v.). The exhaustive version of the stochastic decomposition approach is also to decompose a r.v. into independent components, but in a more systematic way, applied to more complicated PGFs (or transformations), such that detailed probabilistic interpretations for each decomposed component can be provided. We expect that this extended version of decompositions can be applied to other queueing models and used in other applied probability areas.
(2) Tail asymptotic results for the conditional probabilities, specified in PO-i (\(i=0,1, 2\)) and PQ-i (\(i=1, 2\)) for the \(M_1,M_2/G_1,G_2/1\) priority retrial queueing model. These tail asymptotic results are new. Tail probability behaviour is an important topic, which was not touched in [14]. The stochastic decompositions of these generating functions allow us to analyse tail asymptotic behaviour for each independent component in the decompositions, which lead to our final tail asymptotic results, stated in detail in the following theorem. For the purpose of stating this theorem, let \(R_{\mathrm{que}}\) be the number of Type-1 customers in the queue, excluding the possible one in the service, let \(R_{\mathrm{orb}}\) be the number of Type-2 customers in the orbit, and let \(I_{\mathrm{ser}}=0,1, \text{ or } 2\) according to the status of the server: idle, busy with a Type-1 customer, or busy with a Type-2 customer, respectively. To stay consistent with the literature notation, let \(R_0\) be a r.v.whose distribution coincides with the conditional distribution of \(R_{\mathrm{orb}}\) given that \(I_{\mathrm{ser}}=0\), or
where the symbol \(``{\mathop {=}\limits ^\mathrm{d}}\)” stands for equality in probability distribution. Similarly, for \(i=1, 2\), we define the two-dimensional r.v. \((R_{i1},R_{i2})\) as
We can now state the main results on tail asymptotics.
Theorem 1
For the \(M_1,M_2/G_1,G_2/1\) priority retrial queueing model, studied in [14], under assumptions A1 and A2, we have, as \(j \rightarrow \infty \),
(1)
(2)
Recalling the assumptions made on the service times, we notice that all above conditional probabilities are also regularly varying with a dominant influence by the service time distribution for Type-1 customers, except for the case \(r >0\), for which the tail is dominated by the service time for Type-2 customers.
To guide readers to detailed analysis for our main contributions, we provide a step by step presentation in the following sections:
- Step 1::
-
Preliminaries. In this step, we present three PGFs, all obtained from [14], one for the tail behaviour in Theorem 1(1), and the other two for Theorem 1(2). We rewrite these generating functions in a preferable form for making decompositions. We also provide probabilistic interpretations for the functions g and h contained in these three PGFs.
- Step 2::
-
Stochastic decompositions. In this step, in terms of the exhaustive stochastic decomposition approach, we provide stochastic decompositions for the generating functions (or part of the generating function for the case of the r.v. \(R_0\)) provided in Step 1. Equivalently, we show that each of the these functions can be viewed as the generating function for the sum of some well-constructed independent r.v.s, each with a detailed probabilistic interpretation.
- Step 3::
-
Tail asymptotics. In this step, we first specify tail asymptotic properties for each decomposed component obtained in Step 2 and then identify the dominant contributions to derive the results stated in Theorem 1.
The rest of the paper is organized as follows: Sect. 2 is our Step 1, in which we express the probability generating functions of interest, obtained in [14], in the forms in favour of making stochastic decompositions, which are our starting point. Section 3 is devoted to Step 2, in which the proposed exhaustive stochastic decompositions are performed on the three key generating functions. Our Step 3, presented in Sect. 4, is to derive the tail asymptotic properties, based on the results obtained in previous sections. Most of the detailed analysis is organized in Appendices B and C following the concluding section, Sect. 5.
2 Preliminaries—step 1
For the \(M_1,M_2/G_1,G_2/1\) priority retrial queueing model, according to the definitions of the r.v.s \(R_0\) and \((R_{i1},R_{i2})\) for \(i=1,2\) (given in the Introduction), we have that \(R_0\) has the PGF \(R_0(z_2){\mathop {=}\limits ^\mathrm{def}}E(z_2^{R_0})=E(z_2^{R_{\mathrm{orb}}}|I_{\mathrm{ser}}=0)\), and \((R_{i1},R_{i2})\) has the PGF \(R_i(z_1,z_2){\mathop {=}\limits ^\mathrm{def}}E(z_1^{R_{i1}}z_2^{R_{i2}})=E(z_1^{R_{\mathrm{que}}}z_2^{R_{\mathrm{orb}}}|I_{\mathrm{ser}}=i)\) for \(i=1,2\). These three generating functions are key probability quantities of the queueing model. In [14], the authors obtained expressions for \(R_0(z_2)\), \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\), together with the facts that \(P\{I_{\mathrm{ser}}=0\}=1-\rho \), \(P\{I_{\mathrm{ser}}=1\}=\rho _1\) and \(P\{I_{\mathrm{ser}}=2\}=\rho _2\).
In this section, we first rewrite these three generating functions into forms favourable for making stochastic decompositions and also provide probabilistic interpretations for two important functions h and g (in Sects. 2.1.1 and 2.1.2, respectively) contained in the generating functions.
2.1 Generating function \(R_0(z_2)\)
First, we denote
where the function \(h(z_2)\) is uniquely determined by the equation
Then, the PGF \(R_0(z_2)\), obtained in [14], can be rewritten as
where
with
\(R_0(z_2)\) will be used for us to obtain the tail asymptotic properties in Theorem 1(1). In Step 2, we will show that all \(K_a(u)\), \(K_b(u)\) and \(K_c(u)\) can be viewed as the PGFs of three independent r.v.s., with detailed probabilistic interpretations, and therefore K(u) is also a PGF.
It is worth mentioning that (i) \(\beta (s)\) in (2.1) is the LST of the mixed distribution \(F_{\beta }(x){\mathop {=}\limits ^\mathrm{def}}q F_{\beta _1}(x)+p F_{\beta _2}(x)\); and (ii) both \(h(z_2)\) in (2.3) and \(g(z_2)\) in (2.2) can be regarded as the PGFs of r.v.s, which will be verified in the next subsections.
2.1.1 Probabilistic interpretations of \(h(z_2)\)
\(h(z_2)\) is a function in the expression of function \(g(z_2)\) (see (2.2)), which appears in all \(K_a(u)\), \(K_b(u)\) and \(K_c(u)\) (see (2.7), (2.8) and (2.9)). Therefore, as will be seen, the probabilistic interpretations of both \(h(z_2)\) and \(g(z_2)\) are crucial for the stochastic decomposition of \(K(z_2)\).
In this section, we show that \(h(z_2)\) is closely related to the busy period \(T_{\alpha }\) of the standard M/G/1 queue with arrival rate \(\lambda _1\) and the service time \(T_{\beta _1}\). By \(F_{\alpha }(x)\), we denote the probability distribution function of \(T_{\alpha }\) and by \(\alpha (s)\) the LST of \(F_{\alpha }(x)\). The following are well-known results about this standard M/G/1 queue:
Throughout this paper, we use the notation \(N_b(t)\) to represent the number of Poisson arrivals with rate b within the time interval (0, t]. Now, let us consider \(N_{\lambda _2}(T_{\alpha })\), the number of arrivals of a Poisson process at rate \(\lambda _2\) within an independent random time \(T_{\alpha }\). The PGF of \(N_{\lambda _2}(T_{\alpha })\) is easily obtained as follows:
It then follows from (2.10) that
By comparing (2.3) and (2.13) and noticing the uniqueness of \(h(z_2)\), we immediately have
which, together with (2.12), implies that \(h(z_2)=E(z_2^{N_{\lambda _2}(T_{\alpha })})\) is the PGF of the non-negative integer-valued r.v. \(N_{\lambda _2}(T_{\alpha })\).
2.1.2 Probabilistic interpretations of \(g(z_2)\)
For \(g(z_2)\) defined in (2.2), we show that it is also the PGF of a non-negative integer-valued r.v., denoted by \(X_g\), i.e., \(g(z_2)=E(z_2^{X_g})\). In fact, it follows from (2.2) that
Also, it is easy to obtain that \(E(N_{\lambda _2}(T_{\alpha }))=\lambda _2\beta _{1,1}/(1-\rho _1)\) and
2.2 Generating functions \(R_i(z_1,z_2)\) for \(i=1,2\)
In this section, we rewrite the generating functions \(R_i(z_1,z_2)\), \(i=1,2\), obtained in [14], in a different form preferred for stochastic decompositions.
To this direction, for \(i=1,2\), let \(F_{\beta _i}^{(e)}(x)\) be the so-called equilibrium distribution of the service distributions \(F_{\beta _i}(x)\), which is defined as \(F_{\beta _i}^{(e)}(x) {\mathop {=}\limits ^\mathrm{def}} \beta _{i,1}^{-1}\int _0^{x}(1-F_{\beta _i}(t))\mathrm{d}t\). The LST of \(F_{\beta _i}^{(e)}(x)\) can be written as \(\beta _i^{(e)}(s)=(1-\beta _i(s))/(\beta _{i,1} s)\). Let \(T_{\beta }^{(e)}\) be a r.v. having the distribution \(F_{\beta }^{(e)}(x)\).
Similarly, let \(F_{\beta }^{(e)}(x) {\mathop {=}\limits ^\mathrm{def}} (q\beta _{1,1}+p\beta _{2,1})^{-1}\int _0^{x}(1-F_{\beta }(t))\mathrm{d}t\) be the equilibrium distribution of the mixed distribution \(F_{\beta }(t)\) (see the last paragraph in Sect. 2.1) of the service times. The LST of \(F_{\beta }^{(e)}(x)\) can be written as \(\beta ^{(e)}(s)=(1-\beta (s))/((q\beta _{1,1}+p\beta _{2,1}) s)\). For \(i=1,2\), let \(T_{\beta _i}^{(e)}\) be a r.v. having the distribution \(F_{\beta _i}^{(e)}(x)\). Moreover, let \(F_{\alpha }^{(e)}(x)= \alpha _1^{-1}\int _0^{x}(1-F_{\alpha }(t))\mathrm{d}t\) be the equilibrium distribution of \(F_{\alpha }(x)\), which is the busy period function defined in Sect. 2.1.1. The LST of \(F_{\alpha }^{(e)}(x)\) can be written as \(\alpha ^{(e)}(s)=(1-\alpha (s))/(\alpha _1 s)\). Let \(T_{\alpha }^{(e)}\) be a r.v., having the distribution \(F_{\alpha }^{(e)}(x)\). This notation is introduced here for convenience, but will not be used until Sect. 3.
Then, the PGFs \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\), obtained in [14], can be rewritten as
where \(K_a(z_2)\), \(K_c(z_2)\) and \(R_0(z_2)\) are given in (2.7), (2.9) and (2.4), respectively, and
\(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\) will be used for us to obtain the tail asymptotic properties in Theorem 1(2). In Step 2, we will show that all factors in the expressions of \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\) can be viewed as the PGFs of some r.v.s., with detailed probabilistic interpretations.
3 Stochastic decompositions—step 2
In this section, we show that all three factors \(K_a(u)\), \(K_b(u)\) and \(K_c(u)\) in the expression of K(u) [see (2.6)] are PGFs. Therefore, the integrand function K(u) in the PGF \(R_0(z_2)\) is also a PGF. Furthermore, we show that all factors in the PGFs \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\) [see (2.17) and (2.18)] are PGFs. These decomposition results are needed in Step 3 for deriving the tail asymptotic results stated in Theorem 1.
3.1 Stochastic decomposition of K(u)
Denote
where the inequality follows from the stability condition \(\rho =\rho _1+\rho _2<1\).
The decomposition result for K(u) can be stated in the following proposition.
Proposition 3.1
All factors \(K_a(u)\), \(K_b(u)\) and \(K_c(u)\) in the expression of K(u), given in (2.6), are PGFs. Therefore, K(u) itself is also a PGF. Furthermore, if K is a r.v. having the PGF K(u), and \(K_a\), \(K_b\) and \(K_c\) are independent r.v.s having the PGFs \(K_a(u)\), \(K_b(u)\) and \(K_c(u)\), respectively, then K can be stochastically decomposed as
where \(K_a\), \(K_b\) and \(K_c\) can be specifically constructed by
and
In the above expressions, \(\vartheta \) is defined by (3.1); \(N_{\lambda _2}(T_{\alpha }^{(e)})\) is the number of arrivals for the Poisson process with rate \(\lambda _2\) within the time interval \((0,T_{\alpha }^{(e)}]\); \(N_{\lambda ,X_g}(T_{\beta }^{(e)})\) represents the number of the batched Poisson arrivals, with rate \(\lambda \) and batch size \(X_g\), within the time interval \((0,T_{\beta }^{(e)}]\), where \(X_g\) has the PGF g(z) given in (2.2); and \(\{X_c^{(i)}\}_{i=1}^{\infty }\) is a sequence of i.i.d. non-negative integer-valued r.v.s., each with the same PGF \(K_a(z)\cdot \beta _2^{(e)}(\lambda - \lambda g(z))\), namely, \(X_c^{(i)}{\mathop {=}\limits ^\mathrm{d}}K_a+N_{\lambda ,X_g}(T_{\beta _2}^{(e)})\), where the two components are assumed to be independent, and \(P(J=i)=(1-\vartheta )\vartheta ^{i-1}\), \(i\ge 1\), independent of \(\{X_c^{(i)}\}_{i=1}^{\infty }\).
We defer the proof of Proposition 3.1 to Appendix B.
3.2 Stochastic decompositions of \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\)
It was proved in [14] and in Sect. 3.1, respectively, that \(R_0(z_2)\), \(K_a(z_2)\) and \(K_c(z_2)\) are PGFs. In this section, we show that all four remaining factors \(M_i(z_1,z_2)\) and \(S_{\beta _i}(z_1,z_2)\), for \(i=1,2\), in the expressions of \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\) (given in (2.17) and (2.18), respectively) are also PGFs. Compared to the effort for the exhaustive stochastic decomposition for \(K(z_2)\), it is more demanding here to get decompositions for \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\).
For stating the decomposition result, we need some preparations. First, for the probabilistic interpretations of the functions \(S_{\beta _i}(z_1,z_2)\), \(i=1,2\), we introduce the concept of splitting.
Definition 3.1
Let N be a non-negative integer-valued r.v., and let \(\{X_k\}_{k=1}^{\infty }\) be a sequence of i.i.d. Bernoulli r.v.s, which is independent of N, having the common 0-1 distribution \(P\{X_k=1\}=c\) and \(P\{X_k=0\}=1-c\) with \(0<c<1\). The two-dimensional r.v. \((\sum _{k=1}^N X_k,N-\sum _{k=1}^N X_k)\), where \(\sum _{1}^0\equiv 0\), is called an independent \((c,1-c)\)-splitting of N, denoted by \({\mathrm{split} (}N;c,1-c)\).
For probabilistic interpretations of \(M_i(z_1,z_2)\), \(i=1,2\), we introduce the following r.v.s. Let \(\{(Y_{n,1},Y_{n,2})\}_{n=1}^{\infty }\) be a sequence of independent two-dimensional r.v.s, each with the common PGF \(q z_1+p z_2\), and let \(\{Z_m\}_{m=1}^{\infty }\) be a sequence of independent r.v.s, each with the common PGF \(g(z_2)\). Assume that these two sequences are independent. In terms of the above two sequences, we construct, for \(k \ge 1\),
and then, in terms of \((D_{k,1},D_{k,2})\), we construct
where
and
Here, it is worthwhile to mention that \((q/\rho _1)\sum _{k=1}^{\infty }kb_{\beta _1,k}=1\) (see (B.13) for a proof), and \((p/\rho _2)\sum _{k=1}^{\infty }kb_{\beta _2,k}=1\) (its proof is similar).
We can now state the decomposition results for \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\).
Proposition 3.2
Besides \(R_0(z_2)\), \(K_a(z_2)\) and \(K_c(z_2)\), all the other four factors \(M_i(z_1,z_2)\) and \(S_{\beta _i}(z_1,z_2)\), \(i=1,2\), in the expressions of \(R_1(z_1,z_2)\) and \(R_2(z_1,z_2)\), given in (2.17) and (2.18), respectively, are also PGFs. Furthermore, for \(i=1,2\), if \((M_{i1},M_{i2})\) and \((S_{\beta _i,1},S_{\beta _i,2})\) are two-dimensional r.v.s having the PGF \(M_i(z_1,z_2)\) and \(S_{\beta _i}(z_1,z_2)\), respectively, then the r.v.s \((R_{i1},R_{i2})\) for \(i=1,2\) can be stochastically decomposed as
where, for \(i=1,2\),
with \(N_{\lambda }(T_{\beta _i}^{(e)})\) being the number of Poisson arrivals with rate \(\lambda \) within the time interval \((0,T_{\beta _i}^{(e)}]\);
where J is independent of \((H_{\beta _1,1}^{(i)},H_{\beta _1,2}^{(i)})\) (\(i\ge 1\)), having the distribution \(P(J=i)=(1-\rho _1)\rho _1^{i-1}\), \(i\ge 1\);
and the probabilistic structures for \(K_a\), \(K_c\) and \(R_0\) have been provided in previous sections.
4 Tail asymptotics—step 3
In this section, based on the stochastic decomposition results obtained in the previous section, we prove the tail asymptotic results presented in Theorem 1. Before that, we provide some comments on the assumptions in A1 and A2. The service time \(T_{\beta _1}\) has a so-called regularly varying tail at \(\infty \). It is well known that for a distribution F on \((0,\infty )\), if \(\overline{F}\) is regularly varying with index \(-\sigma \), \(\sigma \ge 0\) (see Definition A.1) or \(\overline{F}\in {\mathcal {R}}_{-\sigma }\), then F is subexponential (see Definition A.2) or \(F\in {\mathcal {S}}\) (see, for example Embrechts et al. [12]).
Clearly, under the assumptions in A1 and A2, the service time \(T_{\beta _1}\) of Type-1 customers has a tail probability heavier than the service time \(T_{\beta _2}\) of Type-2 customers. If \(r>0\), \(T_{\beta _2}\) has a light tail, i.e., \(E(e^{\varepsilon T_{\beta _2}})<\infty \) for some \(\varepsilon >0\). If \(r=0\), then \(T_{\beta _2}\) has a regularly varying tail with index \(-a_2\). We also notice that since \(T_{\alpha }\), introduced in Sect. 2.1.1, is the busy period of the standard M/G/1 queue with arrival rate \(\lambda _1\) and service time \(T_{\beta _1}\), its asymptotic tail probability is regularly varying according to de Meyer and Teugels [10] (see Lemma A.1).
4.1 Tail asymptotics for \(R_0\)—Proof of Theorem 1(1)
In order to obtain the tail asymptotic property for \(R_0\) [or Theorem 1(1)], we first present tail asymptotic properties for the components \(K_a\), \(K_b\) and \(K_c\), respectively, and then the property for K. These results are summarized into the following lemma.
Lemma 4.1
As \(j \rightarrow \infty \), we have
-
(1)
$$\begin{aligned} P\{K_a>j\} \sim \&\frac{\lambda _1\lambda _2^{a_1-1}}{(a_1-1) (1-\rho _1)^{a_1}} \cdot j^{-a_1+1} L(j), \end{aligned}$$(4.1)$$\begin{aligned} P\{K_b>j\} \sim \&\frac{\lambda _1 \lambda _2^{a_1-1}}{\rho (a_1-1)(1-\rho _1)^{a_1-1}} \cdot j^{-a_1+1} L(j), \end{aligned}$$(4.2)$$\begin{aligned} P\{K_c>j\} \sim \&\frac{\vartheta }{1-\vartheta } P\{K_a>j\}; \end{aligned}$$(4.3)
-
(2)
$$\begin{aligned} P\{K>j\} \sim \frac{\lambda _1\lambda _2^{a_1-1}}{\rho (1-\rho )(a_1-1) (1-\rho _1)^{a_1-1}} \cdot j^{-a_1+1} L(j). \end{aligned}$$(4.4)
Refer to Appendix C for a proof of Lemma 4.1.
Proof of Theorem 1(1)
By (2.4), the PGF \(R_0(z)\) is expressed in terms of the PGF K(z). Therefore, the tail probability of \(R_0\) is determined by the tail probability of K. The following asymptotic result is a straightforward application of Theorem 5.1 in [25]:
where \(\psi \) is given in (2.5).
4.2 Tail asymptotics for \(R_{ik}\) (\(i, k=1,2\))—Proof of Theorem 1(2)
In order to obtain tail asymptotic properties for \(R_{ik}\), \(i,k=1,2\), based on the stochastic decompositions for \(R_{ik}\) in (3.11) and (3.12), we first present tail asymptotic properties for the components \(S_{\beta _i,k}\) and \(M_{ik}\) in (3.13), (3.14) and (3.15). These results are summarized into the following lemma.
Lemma 4.2
As \(j \rightarrow \infty \), we have
-
(1)
$$\begin{aligned} P\{S_{\beta _1,1}>j\} \sim&\ \frac{\lambda _1^{a_1}}{\rho _1 (a_1-1) } \cdot j^{-a_1+1} L(j), \end{aligned}$$(4.6)$$\begin{aligned} P\{S_{\beta _1,2}>j\} \sim&\ \frac{\lambda _1\lambda _2^{a_1-1}}{\rho _1 (a_1-1) } \cdot j^{-a_1+1} L(j), \end{aligned}$$(4.7)$$\begin{aligned} P\{S_{\beta _2,1}>j\} \sim&\ \left\{ \begin{array}{ll} \frac{\lambda _2\lambda _1^{a_2-1}}{\rho _2 (a_2-1)}\cdot j^{-a_2+1} L(j), &{} \text{ if } r=0,\\ \frac{\lambda _2\lambda _1 (\lambda _1+r)^{a_2-1}}{\rho _2 r} \cdot \left( \frac{\lambda _1}{\lambda _1+r}\right) ^j j^{-a_2} L(j), &{} \text{ if } r>0, \end{array} \right. \end{aligned}$$(4.8)$$\begin{aligned} P\{S_{\beta _2,2}>j\} \sim&\ \left\{ \begin{array}{ll} \frac{\lambda _2^{a_2}}{\rho _2 (a_2-1) }\cdot j^{-a_2+1} L(j), &{} \text{ if } r=0,\\ \frac{\lambda _2^2(\lambda _2+r)^{a_2-1}}{\rho _2 r}\cdot \left( \frac{\lambda _2}{\lambda _2+r}\right) ^j j^{-a_2} L(j), &{} \text{ if } r>0; \end{array} \right. \end{aligned}$$(4.9)
-
(2)
$$\begin{aligned} P\{M_{11}>j\} \sim&\ \frac{\rho _1}{1-\rho _1} P \{S_{\beta _1,1}>j \}, \end{aligned}$$(4.10)$$\begin{aligned} P\{M_{12}>j\} \sim&\ \left[ \frac{1}{(1-\rho _1)^{a_1}}-1\right] \cdot \frac{\lambda _1 \lambda _2^{a_1-1}}{\rho _1(a_1-1)}\cdot j^{-a_1+1}L(j), \end{aligned}$$(4.11)$$\begin{aligned} P\{M_{21}>j\} =&\ \vartheta P \{S_{\beta _2,1} >j \}, \end{aligned}$$(4.12)$$\begin{aligned} P\{M_{22}>j\} \sim&\ \vartheta \frac{\lambda _1\lambda _2^{a_1-1}}{(1-\rho ) (a_1-1) (1-\rho _1)^{a_1-1}} \cdot j^{-a_1+1} L(j). \end{aligned}$$(4.13)
Refer to Appendix C for a proof of Lemma 4.2.
Now, we are in the position to prove Theorem 1(2). Note that the tail asymptotic properties for \(K_a\), \(K_c\) and \(R_0\) have already been derived earlier. Based on Lemma 4.2 and by identifying dominant contributions made from the tail probabilities \(P\{M_{ik}>j\}\), \(P\{S_{\beta _i,k}>j\}\), \(P\{K_a+K_c>j\}\) and \(P\{R_0>j\}\) to \(P\{R_{ik} >j \}\), Theorem 1(2) can be proved as follows.
Proof of Theorem 1(2)
Recall (3.11). By (4.12), (4.8) and (1.1), \(M_{21}\) and \(R_0\) have tail probabilities lighter than \(j^{-a_1+1}L(j)\), and by (4.10), (4.13), (4.6) and (4.7), \(M_{11}\), \(M_{22}\), \(S_{\beta _1,1}\) and \(S_{\beta _1,2}\) have regularly varying tails with index \(-a_1+1\). By (3.11) and applying Lemma A.5, we obtain
By a similar argument, it follows from (3.12) that
where we have used the fact, by (4.9), that \(S_{\beta _2,2}\) has a tail probability lighter than \(j^{-a_1+1}L(j)\).
Recall the definition of \(R_{ik}\), \(i,k=1,2\), given in Sect. 1. We know that \(P\{R_{\mathrm{que}}>j|I_{\mathrm{ser}}=i\}=P\{R_{i1}>j\}\) and \(P\{R_{\mathrm{orb}}>j|I_{\mathrm{ser}}=i\}=P\{R_{i2}>j\}\), \(i=1,2\). This completes the proof of Theorem 1(2). \(\square \)
5 Concluding remarks
In this paper, we considered a priority retrial queueing model, which was first considered in [14]. This is a relatively complex queueing system with two types of arrivals, priority and non-priority, joining a regular queue and a retrial orbit, respectively, and served by a singer server. This model was considered in [14], and expressions of the generating functions for some key probability measures were obtained by the authors. However, tail probability behaviour, which is important on its own merits and also in applications, of these key probability measures was not touched in [14], which is the focus of this paper. We proposed an exhaustive stochastic decomposition approach to decompose a complicated generating function (or a transformation) into independent components with clear probabilistic interpretations. For each component in the decomposition, we provide tail asymptotic results for the associated probabilities, with which we successfully obtained tail asymptotic results (Theorem 1) for probabilities of the number of customers in the queue or in the orbit, under various conditions.
The proposed exhaustive stochastic decomposition approach is a generalization of the standard decomposition, frequently used in probability and also in queueing applications. We expect that this decomposition approach can be used for other queueing systems and in other areas of applied probability. In fact, this paper is one of the sister papers (see, for example, [25, 27, 28]) in exploring its potential usefulness and importance.
It is of interest to continue the research in this direction. One of the natural extensions is to apply this exhaustive stochastic decomposition approach to other queueing systems. Another interesting problem is to explore its potentials in the analysis of statistical queueing networks, defined through big data (see, for example, [33]).
To conclude the paper, we would like to provide intuition on the results in Theorem 1(2). First, let us recall a well-known result for the standard M/G/1 queue: If the service time is regularly varying with index \(-a_1\), then the stationary queue length is also regularly varying, but with index \(-a_1+1\). Such a conclusion can be made through a distributional Little’s law (see, for example [3]). For the model studied in this paper, the condition \(I_{\mathrm{ser}}=1\) means that the server is serving a Type-1 customer. Under this condition, both types of customers have to wait, customers of Type-1 in the queue and customers of Type-2 in the orbit. Therefore, both \(R_{\mathrm{que}}|I_{\mathrm{ser}}=1\) and \(R_{\mathrm{orb}}|I_{\mathrm{ser}}=1\) have an asymptotic tail of the form \(Const \cdot j^{-a_1+1}L(j)\) (given in (1.2) and (1.3), respectively), due to the regularly varying assumption for the service time of Type-1 customers in Assumption A1. Here, and throughout the appendices, Const stands for a (but not necessarily the same) constant. On the other hand, the condition \(I_{\mathrm{ser}}=2\) means that the server is serving a Type-2 (lower-priority) customer, which implies that no Type-1 customers were waiting in the queue at the beginning of service of this Type-2 customer. In other words, \(I_{\mathrm{ser}}=2\) implies that all Type-1 customers in the queue must be those who arrived after the beginning of the service time of this Type-2 customer. Therefore, \(R_{\mathrm{que}}|I_{\mathrm{ser}}=2\) has an asymptotic tail of the form given in (1.4), determined by the service time assumption (in Assumption A2) of Type-2 customers. However, \(R_{\mathrm{orb}}|I_{\mathrm{ser}}=2\) still has an asymptotic tail of the form \(Const \cdot j^{-a_1+1}L(j)\) (see (1.5), determined by the assumption on Type-1 customer’s service time), since the customers in the orbit could be those who arrived during the service times of Type-2 customers, and/or during the service times of Type-1 customers who were served before the current Type-2 customer in service, due to the priority discipline.
References
Artalejo, J.R., Dudin, A.N., Klimenok, V.I.: Stationary analysis of a retrial queue with preemptive repeated attempts. Oper. Res. Lett. 28, 173–180 (2001)
Artalejo, J.R., Gómez-Corral, A.: Retrial Queueing Systems. Springer, Berlin (2008)
Asmussen, S., Klüppelberg, C., Sigman, K.: Sampling at subexponential times, with queueing applications. Stoch. Process. Their Appl. 79(2), 265–286 (1999)
Bingham, N.H., Goldie, C.M., Teugels, J.L.: Regular Variation. Cambridge University Press, Cambridge (1989)
Borst, S.C., Boxma, O.J., Nunez-Queija, R., Zwart, A.P.: The impact of the service discipline on delay asymptotics. Perform. Eval. 54, 175–206 (2003)
Boxma, O., Denisov, D.: Sojourn time tails in the single server queue with heavy-tailed service times. Queue. Syst. 69, 101–119 (2011)
Boxma, O., Zwart, B.: Tails in scheduling. ACM Sigmetrics Perform. Eval. Rev. 34, 13–20 (2007)
Choi, B.D., Chang, Y.: Single server retrial queues with priority calls. Math. Comput. Model. 30, 7–32 (1999)
Dimitriou, I.: A mixed priority retrial queue with negative arrivals, unreliable server and multiple vacations. Appl. Math. Model. 37, 1295–1309 (2013)
de Meyer, A., Teugels, J.L.: On the asymptotic behavior of the distributions of the busy period and service time in \(M/G/1\). J. Appl. Probab. 17, 802–813 (1980)
Dudin, A.N., Lee, M.H., Dudina, O., Lee, S.K.: Analysis of priority retrial queue with many types of customers and servers reservation as a model of cognitive radio system. IEEE Trans. Commun. 65(1), 186–199 (2017)
Embrechts, P., Kluppelberg, C., Mikosch, T.: Modelling Extremal Events for Insurance and Finance. Springer, Heidelberg (1997)
Falin, G.I.: A survey of retrial queues. Queue. Syst. 7(2), 127–168 (1990)
Falin, G.I., Artalejo, J.R., Martin, M.: On the single server retrial queue with priority customers. Queue. Syst. 14(3–4), 439–455 (1993)
Feller, W.: An Introduction to Probability Theory and Its Applications, vol. II. Wiley, London (1971)
Foss, S., Korshunov, D.: Sampling at a random time with a heavy-tailed distribution. Markov Process. Relat. Fields 6(4), 543–568 (2000)
Foss, S., Korshunov, D., Zachary, S.: An Introduction to Heavy-Tailed and Subexponential Distributions. Springer, New York (2011)
Gao, S.: A preemptive priority retrial queue with two classes of customers and general retrial times. Oper. Res. Int. J. 15, 233–251 (2015)
Gómez-Corral, A.: Analysis of a single-server retrial queue with quasi-random input and nonpreemptive priority. Comput. Math. Appl. 43, 767–782 (2002)
Grandell, J.: Mixed Poisson Processes. Chapman & Hall, London (1997)
Kim, J., Kim, B.: A survey of retrial queueing systems. Ann. Oper. Res. 247(1), 3–36 (2016)
Kim, J., Kim, J., Kim, B.: Regularly varying tail of the waiting time distribution in \(M/G/1\) retrial queue. Queue. Syst. 65(4), 365–383 (2010c)
Kim, J., Kim, B., Ko, S.-S.: Tail asymptotics for the queue size distribution in an \(M/G/1\) retrial queue. J. Appl. Probab. 44(4), 1111–1118 (2007)
Lee, Y.: Discrete-time \(Geo^X/G/1\) queue with preemptive resume priority. Math. Comput. Model. 34, 243–250 (2001)
Liu, B., Min, J., Zhao, Y.Q.: Refined tail asymptotic properties for the \(M^X/G/1\) retrial queue. Submitted. (arXiv:1801.02525) (2017)
Liu, B., Zhao, Y.Q.: Analyzing retrial queues by censoring. Queue. Syst. 64(3), 203–225 (2010)
Liu, B., Zhao, Y.Q.: Second order asymptotic properties for the tail probability of the number of customers in the \(M/G/1\) retrial queue. Submitted. (arXiv:1801.09607) (2017)
Liu, B., Zhao, Y.Q.: Tail Asymptotics for a Retrial Queue with Bernoulli Schedule. Submitted. (arXiv:1804.00984) (2018)
Liu, B., Wang, J., Zhao, Y.Q.: Tail asymptotics of the waiting time and the busy period for the \(M/G/1/K\) queues with subexponential service times. Queue. Syst. 76(1), 1–19 (2014)
Liu, B., Wang, X., Zhao, Y.Q.: Tail asymptotics for \(M/M/c\) retrial queues with nonpersistent customers. Oper. Res. Int. J. 12(2), 173–188 (2012)
Müller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley, London (2002)
Phung-Duc, T.: Retrial Queueing Models: A survey on theory and applications, to appear In: Dohi T., Ano, K., Kasahara, S. (eds.) Stochastic Operations Research in Business and Industry, World Scientific Publisher. (http://infoshako.sk.tsukuba.ac.jp/tuan/papers/Tuan_chapter_ver3.pdf) (2017)
Sutton, C., Jordan, M.I.: Bayesian inference for queueing networks and modeling of internet services. Ann. Appl. Stat. 5(1), 254–282 (2011)
Walraevens, J., Claeys, D., Phung-Duc, T.: Asymptotics of queue length distributions in priority retrial queues. Perform. Eval. 127–128, 235–252 (2018)
Wang, J.: On the single server retrial queue with priority subscribers and server break-downs. J. Syst. Sci. Complex 21, 304–315 (2008)
Wu, J., Lian, Z.: A single-server retrial G-queue with priority and unreliable server under Bernoulli vacation schedule. Comput. Ind. Eng. 64, 84–93 (2013)
Wu, J., Wang, J., Liu, Z.: A discrete-time Geo/G/1 retrial queue with preferred and impatient customers. Appl. Math. Model. 37, 2552–2561 (2013)
Acknowledgements
We thank the anonymous reviewer for her/his constructive comments and suggestions, which significantly improved the quality of this paper. This work was supported in part by the National Natural Science Foundation of China (Grant No. 71571002), the Research Project of Anhui Jianzhu University and a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada (NSERC).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Definitions and useful results from the literature
Definition A.1
(for example, see Bingham, Goldie and Teugels [4]) A measurable function \(U:(0,\infty )\rightarrow (0,\infty )\) is regularly varying at \(\infty \) with index \(\sigma \in (-\infty ,\infty )\) (written \(U\in {\mathcal {R}}_{\sigma }\)) iff \(\lim _{t\rightarrow \infty }U(xt)/U(t)=x^{\sigma }\) for all \(x>0\). If \(\sigma =0\) we call U slowly varying, i.e., \(\lim _{t\rightarrow \infty }U(xt)/U(t)=1\) for all \(x>0\).
For a distribution function F, denote \(\bar{F}{\mathop {=}\limits ^\mathrm{def}}1-F\) for the remainder of the paper.
Definition A.2
(for example, see Foss, Korshunov and Zachary [17]) A distribution F on \((0,\infty )\) belongs to the class of subexponential distribution (written \(F\in {\mathcal {S}}\)) if \(\lim _{t\rightarrow \infty }\overline{F^{*2}}(t)/\overline{F}(t)=2\), where \(\overline{F}=1-F\) and \(F^{*2}\) denotes the second convolution of F.
Lemma A.1
(de Meyer and Teugels [10]) Under Assumption A1,
The result (A.1) is straightforward due to the main theorem in [10].
Lemma A.2
(pp.580–581 in [12]) Let N be a r.v. with \(P\{N=k\}=(1-\sigma )\sigma ^{k-1}\), \(0<\sigma <1\), \(k\ge 1\), and \(\{Y_k\}_{k=1}^{\infty }\) be a sequence of non-negative, i.i.d. r.v.s having a common subexponential distribution F. Define \(S_n=\sum _{k=1}^n Y_k\). Then, \(P\{S_N > t\} \sim (1-F(t))/(1-\sigma )\) as \(t\rightarrow \infty \).
Lemma A.3
(Proposition 3.1 in [3], or Theorem 3.1 in [16]) Let \(N_{\lambda }(t)\) be a Poisson process with rate \(\lambda \) and let T be a positive r.v. with distribution F, which is independent of \(N_{\lambda }(t)\). If \(\bar{F}(t)=P\{T>t\}\) is heavier than \(e^{-\sqrt{t}}\) as \(t\rightarrow \infty \), then \(P(N_{\lambda }(T)>j)\sim P\{T>j/\lambda \}\) as \(j\rightarrow \infty \).
Lemma A.3 holds for any distribution F with a regularly varying tail because it is heavier than \(e^{-\sqrt{t}}\) as \(t\rightarrow \infty \).
Lemma A.4
(p.181 in [20]) Let \(N_{\lambda }(t)\) be a Poisson process with rate \(\lambda \) and let T be a positive r.v. with distribution F, which is independent of \(N_{\lambda }(t)\). If \(\bar{F}(t) = P\{T>t\}\sim e^{-w t} t^{-h}L(t)\) as \(t\rightarrow \infty \) for \(w> 0\) and \(-\infty<h<\infty \), then
Lemma A.5
(p.48 in [17]) Let F, \(F_1\) and \(F_2\) be distribution functions. Suppose that \(F\in {\mathcal {S}}\). If \(\bar{F}_i(t)/\bar{F}(t)\rightarrow c_i\) as \(t\rightarrow \infty \) for some \(c_i\ge 0, \; i=1,2\), then \(\overline{F_1*F}_2(t)/\bar{F}(t)\rightarrow c_1+c_2\) as \(t\rightarrow \infty \), where the notation \(F_1*F_2\) stands for the convolution of \(F_1\) and \(F_2\).
Lemma A.6
(pp.162–163 in [20]) Let N be a discrete non-negative integer-valued r.v. with mean value \(\mu _N\), and let \(\{Y_k\}_{k=1}^{\infty }\) be a sequence of non-negative i.i.d. r.v.s with mean value \(\mu _Y\). Define \(S_0\equiv 0\) and \(S_n=\sum _{k=1}^n Y_k\). If \(P\{Y_k>x\}\sim c_Y x^{-h} L(x) \) as \(x\rightarrow \infty \) and \(P\{N>m\}\sim c_N m^{-h}L(m)\) as \(m\rightarrow \infty \), where \(h> 1\), \(c_Y\ge 0\) and \(c_N\ge 0\), then \(P\{S_N > x\}\sim (c_N\mu _Y^h + \mu _N c_Y) x^{-h}L(x)\) as \(x\rightarrow \infty .\)
Remark A.1
It is a convention that in Lemma A.6, \(c_Y=0\) and \(c_N=0\) means that \(\lim _{x\rightarrow \infty }P\{Y_k>x\}/(x^{-h} L(x))=0\) and \(\lim _{m\rightarrow \infty }P\{N>m\}/(m^{-h} L(m))=0\), respectively.
The following two criteria are from Feller (see p.441 in [15]), which are often used to verify that a function is completely monotone.
Criterion A.1 If \(\vartheta _1(\cdot )\) and \(\vartheta _2(\cdot )\) are completely monotone, so is their product \(\vartheta _1(\cdot )\vartheta _2(\cdot )\).
Criterion A.2 If \(\vartheta _3(\cdot )\) is completely monotone and \(\vartheta _4(\cdot )\) is a positive function with a completely monotone derivative \(\vartheta '_4(\cdot )\), then \(\vartheta _3(\vartheta _4(\cdot ))\) is completely monotone.
To prove Lemma C.2, let us list some notations and results which will be used. Let F(x) be any distribution on \([0,\infty )\) with the LST \(\phi (s)\). We denote the nth moment of F(x) by \(\phi _n\), \(n\ge 0\). It is well known that \(\phi _n<\infty \) iff
Based on (A.2), we introduce the notation \(\phi _n(s)\) and \(\widehat{\phi }_n(s)\), defined by
Lemma A.7
(pp.333–334 in [4]) Assume that \(n<d<n+1\), \(n\in \{0,1,2,\ldots \}\), then the following two statements are equivalent:
and
Lemma A.8
(Lemma 3.3 in [27]) Assume that \(n\in \{1,2,\ldots \}\), then the following two statements are equivalent:
and
In [27], Lemma A.8 was proved by applying Karamata’s theorem, the monotone density theorem and Theorem 3.9.1 presented in [4] (see, p.27, p.39 and pp.172–173, respectively).
Appendix B: Proofs for results in step 2
1.1 Proof of Proposition 3.1
By (2.14) and the definition of \(\alpha ^{(e)}(s)\), we can write \((1- h(u))/(1-u)= \lambda _2\alpha _1\cdot \alpha ^{(e)}(\lambda _2 - \lambda _2 u)\), from which, and by (2.7), (2.2) and (2.11), we have,
which leads to the stochastic decomposition given in (3.3) for the r.v. \(K_a\).
It follows from (2.8) that
which leads to the stochastic decomposition given in (3.4) for the r.v. \(K_b\).
It follows from (2.9) that
which leads to the stochastic decomposition given in (3.5) for the r.v. \(K_c\).
Finally, (3.2) follows immediately from (2.6).
1.2 Proof of Proposition 3.2
We divide the proof of Proposition 3.2 into three parts.
1.2.1 \(S_{\beta _i}(z_1,z_2)\) are PGFs with detailed probabilistic interpretations
Following Definition 3.1, for the \({\mathrm{split} (}N;c,1-c)\) it is easy to see that \((\sum _{k=1}^N X_k,N-\sum _{k=1}^N X_k)\) has the PGF
where \(\prod _{1}^0\equiv 1\).
Recalling (2.21), we can write, for \(i=1,2\),
which leads to (3.13) by setting \(N=N_{\lambda }(T_{\beta _i}^{(e)})\) and \(c=q\) in (B.4).
1.2.2 \(M_1(z_1,z_2)\) is a PGF with a detailed probabilistic interpretation
It follows from (2.19) that
where
Clearly, by (B.6), \((M_{11},M_{12})\) can be regarded as a random sum of two-dimensional r.v.s. provided that \(H_{\beta _1}(z_1,z_2)\) is the PGF of a two-dimensional r.v. To verify this, we rewrite (B.8) as a power series. Note that
where \(b_{\beta _1,k}\) is given in (3.9). By (2.3) and (B.9),
Substituting (B.9) and (B.10) into the numerator of the right-hand side of (B.8), we obtain
where
Note that \(q h(z_2)+p z_2=g(z_2)\) and \(q z_1+p z_2\) are the PGFs of (one or two-dimensional) r.v.s. It follows from (B.12) that for \(k\ge 1\), \(D_{k}(z_1,z_2)\) is the PGF of a two-dimensional r.v. \((D_{k,1},D_{k,2})\), which can be constructed according to (3.6).
In addition,
Namely, \((q/\rho _1)\sum _{k=1}^{\infty }kb_{\beta _1,k}=1\), which, together with (B.11), implies that \(H_{\beta _1}(z_1,z_2)\) is the PGF of a two-dimensional r.v. \((H_{\beta _1,1},H_{\beta _1,2})\), which can be constructed according to (3.7).
By (B.6), the two-dimensional r.v. \((M_{11},M_{12})\) can be constructed according to (3.14), which is a random sum of i.i.d. two-dimensional r.v.s \((H_{\beta _1,1}^{(i)},H_{\beta _1,2}^{(i)})\), \(i\ge 1\), each with the same PGF \(H_{\beta _1}(z_1,z_2)\).
1.2.3 \(M_2(z_1,z_2)\) is a PGF with a detailed probabilistic interpretation
Let
Using (B.14), (2.7) and (2.9), we can rewrite (2.20) as follows:
Similarly to (B.11), we can derive (details omitted) from (B.14) that
with \(b_{\beta _2,k}\) given in (3.10).
Similarly to (B.13), we can verify that \((p /\rho _2)\sum _{k=1}^{\infty }k b_{\beta _2,k}=1\), which, together with (B.16), implies that \(H_{\beta _2}(z_1,z_2)\) is the PGF of a two-dimensional r.v. \((H_{\beta _2,1},H_{\beta _2,2})\), which can be constructed according to (3.8).
By (B.15), the two-dimensional r.v. \((M_{21},M_{22})\) can be constructed according to (3.15).
Appendix C: Proofs of Lemmas 4.1 and 4.2 in step 3
In this section, we prove Lemma 4.1 and Lemma 4.2. Before proceeding, we provide the following facts, which will be used in our proof multiple times.
Applying Karamata’s theorem (for example, p.28 in [4]), and using Assumption A1 and Lemma A.1, respectively, gives, as \(t\rightarrow \infty \),
and
Applying Proposition 8.5 (p.181 in [20]) to the density \(\bar{F}_{\beta _2}(t)/\beta _{2,1}\) and using Assumption A2, give, as \(t\rightarrow \infty \),
Furthermore, since \(F_{\beta }(x)=q F_{\beta _1}(x)+p F_{\beta _2}(x)\) and based on Assumptions A1 and A2, we have \(P\{T_{\beta }>t\}=qP\{T_{\beta _1}>t\} +p P\{T_{\beta _2}>t\}\sim q t^{-a_1} L(t)\) as \(t\rightarrow \infty \), from which Karamata’s theorem implies that
1.1 Proof of Lemma 4.1
Recall (2.4), which relates the PGF of K to the PGF of \(R_0\). With this relationship, we first study the tail probability for K, which can be regarded as the sum of independent r.v.s \(K_a\), \(K_b\) and \(K_c\) (refer to (3.2)). By (3.3), (C.2) and applying Lemma A.3, we have
Recall (3.4), \(K_b=N_{\lambda , X_g}(T_{\beta }^{(e)}){\mathop {=}\limits ^\mathrm{d}}\sum _{i=1}^{N_{\lambda }(T_{\beta }^{(e)})} X_g^{(i)}\), where \(X_g^{(i)}\) has the common distribution \(X_g\). By (2.15), and then applying Lemma A.3 and using Lemma A.1, we know that
Similarly, applying Lemma A.3 and using (C.4), we have
based on which, by (2.16) and applying Lemma A.6, we have,
Next, we study \(P\{K_c>j\}\). By (3.5), we know that \(P\{K_c>j\}=\vartheta P\{\sum _{i=1}^{J}X_c^{(i)}>j\}\), where \(P(J=i)=(1-\vartheta )\vartheta ^{i-1}\), \(i\ge 1\), and \(X_c^{(i)}\) has the same distribution as that for \(X_c=K_a+N_{\lambda ,X_g}(T_{\beta _2}^{(e)})\). Note that \(N_{\lambda ,X_g}(T_{\beta _2}^{(e)}){\mathop {=}\limits ^\mathrm{d}}\sum _{i=1}^{N_{\lambda }(T_{\beta _2}^{(e)})} X_g^{(i)}\), where \(X_g^{(i)}\) has the common tail probability \(P\{X_g>j\}\sim Const\cdot j^{-a_1} L(j)\) and \(P\{N_{\lambda }(T_{\beta _2}^{(e)})>j\}\sim Const\cdot j^{-a_2+1}L(j)\). Therefore, by applying Lemma A.6 (and noticing that \(a_2 > a_1\) if \(r=0\) in Assumption A2), we have
By (C.5), (C.7), applying Lemma A.2 and Lemma A.5, we have, as \(j\rightarrow \infty \),
which, together with (C.5), (C.6) and (3.2), leads to
1.2 Proof of Lemma 4.2
By Proposition 3.2, \(S_{\beta _1,1}{\mathop {=}\limits ^\mathrm{d}}N_{\lambda _1}(T_{\beta _1}^{(e)})\), \(S_{\beta _1,2}{\mathop {=}\limits ^\mathrm{d}}N_{\lambda _2}(T_{\beta _1}^{(e)})\), \(S_{\beta _2,1}{\mathop {=}\limits ^\mathrm{d}}N_{\lambda _1}(T_{\beta _2}^{(e)})\) and \(S_{\beta _2,2}{\mathop {=}\limits ^\mathrm{d}}N_{\lambda _2}(T_{\beta _2}^{(e)})\). By (C.1) and applying Lemma A.3, we obtain
By (C.3) and applying Lemma A.3 and Lemma A.4, we obtain
Next, we will study the asymptotic tail probabilities of the r.v.s \(M_{ik},\ i,k=1,2\). By Proposition 3.2, we know that
To proceed further, we need to study the tail probabilities of the r.v.s \(H_{\beta _i,k}\) for \(i,k=1,2\).
1.2.1 Tail asymptotics for \(H_{\beta _1,1}\) and \(H_{\beta _2,1}\)
Taking \(z_2\rightarrow 1\) in (B.8) and (B.14), we can write
Therefore, \(H_{\beta _i,1}{\mathop {=}\limits ^\mathrm{d}}N_{\lambda _1}(T_{\beta _i}^{(e)}){\mathop {=}\limits ^\mathrm{d}}S_{\beta _i,1}\), \(i=1,2\), and
whose asymptotic tails are presented in (C.11) and (C.13), respectively.
1.2.2 Tail asymptotics for \(H_{\beta _1,2}\)
Unlike for the other r.v.s discussed earlier, more effort is required for the asymptotic tail behaviour for \(H_{\beta _1,2}\), which will be presented in Proposition C.1. Before doing that, we first present a nice bound on the tail probability of \(H_{\beta _1,2}\), which is very suggestive for an intuitive understanding of the tail property for \(H_{\beta _1,2}\).
Taking \(z_1\rightarrow 1\) in (B.12) and (B.11), we have,
It follows from (C.21) that, for \(k\ge 1\),
where \(\{Y_n\}_{n=1}^{\infty }\) and \(\{Z_n\}_{n=1}^{\infty }\) are sequences of independent r.v.s, which are independent of each other, with \(Y_n\) and \(Z_n\) having PGFs \(q +p z_2\) and \(q h(z_2)+p z_2\), respectively.
We say that Y is stochastically smaller than Z, written as \(Y\le _{st}Z\), if \(P\{Y>t\}\le P\{Z>t\}\) for all t. It is easy to see that \(Y_{n_1}\le _{st}Z_{n_2}\) for all \(n_1,n_2\ge 1\). Define
Then, by Theorem 1.2.17 (p.7 in [31]),
Furthermore, it follows from (C.22) that \(H_{\beta _1,2}{\mathop {=}\limits ^\mathrm{d}}D_{k,2}\), with probability \((q/\rho _1)k b_{\beta _1,k}\), for \(k\ge 1\).
Now, define the r.v.s \(H^L_{\beta _1,2}\) and \(H^U_{\beta _1,2}\) as follows:
Then, by (C.23),
Note that \(H_{\beta _1,2}^{L}\) and \(H_{\beta _1,2}^{U}\) have the following PGFs:
Next, we will study the asymptotic behaviour of \(P\{H_{\beta _1,2}^{L}>j\}\) and \(P\{H_{\beta _1,2}^{U}>j\}\), respectively. Let N be a r.v. with probability distribution \(P\{N=k\}=(q/\rho _1) k b_{\beta _1,k}\), \(k\ge 1\). Therefore, (C.25) and (C.26) can be written as
where N is independent of both \(Z_k\) and \(Y_k\), \(k\ge 1\).
Then, it is immediately clear that
where \(\overline{b}_{\beta _1,k}=\sum _{n=k}^{\infty } b_{\beta _1,n}\).
Using the definition of \(b_{\beta _1,n}\) in (3.9), and applying Lemma A.3, we know that \(\overline{b}_{\beta _1,k}=P\{N_{\lambda }(T_{\beta _1})>k-1\}\sim \lambda ^{a_1}k^{-a_1}L(k)\) as \(k\rightarrow \infty \), which, together with Proposition 1.5.10 in [4], implies that
Recall the following three facts: (i) \(Y_k\) is a \(0-1\) r.v., which implies that \(P\{Y_k>j\}\rightarrow 0\) as \(j\rightarrow \infty \); (ii) \(Z_k\) has the same probability distribution as \(X_g\) defined in (2.15), which implies that \(P\{Z_k>j\}=P \{X_g>j\}\sim Const\cdot j^{-a_1} L(j)\) as \(j\rightarrow \infty \); and (iii) \(E(Y_k)=p\) and \(E(Z_k)=E(X_g)=p/(1-\rho _1)<\infty \), given in (2.16). Then, by Lemma A.6, we know that
Remark C.1
It follows from (C.24) that \(P\{H_{\beta _1,2}^{L}>j\}\le P\{H_{\beta _1,2}>j\}\le P\{H_{\beta _1,2}^{U}>j\}\), whereas the asymptotic properties of \(P\{H_{\beta _1,2}^{L}>j\}\) and \(P\{H_{\beta _1,2}^{U}>j\}\) are given in (C.29) and (C.30), respectively. This suggests that \(P\{H_{\beta _1,2}>j\}\sim c\cdot \frac{\lambda _1 \lambda _2^{a_1-1}}{\rho _1(a_1-1)}\cdot j^{-a_1+1}L(j)\) as \(j\rightarrow \infty \) for some constant \(c\in \left( a_1, a_1/(1-\rho _1)^{a_1-1}\right) \). In Proposition C.1, we will verify that this assertion is true.
Proposition C.1
As \(j\rightarrow \infty \),
To prove this proposition, we need the following two lemmas (Lemma C.1 and Lemma C.2). Setting \(z_1=1\) in (B.7) and noting \(h(z_2)=\alpha (\lambda _2-\lambda _2 z_2)\), we obtain
where
Lemma C.1
\(\gamma (s)\) is the LST of a probability distribution on \([0,\infty )\).
Proof
By Theorem 1 in [15] (see p.439), the lemma is true iff \(\gamma (0)=1\) and \(\gamma (s)\) is completely monotone, i.e., \(\gamma (s)\) possesses derivatives of all orders such that \((-1)^{n}\frac{d^n}{ds^n}\gamma (s)\ge 0\) for \(s> 0\), \(n\ge 0\). It is easy to check by (C.33) that \(\tau (0)=1\). Next, we only need to verify that \(\gamma (s)\) is completely monotone. By (C.33) and (2.10) and using Taylor expansion, we have
where \(\beta _1^{(n)}(\cdot )\) represents the nth derivative of \(\beta _1(\cdot )\).
It is easy to check that, for \(n\ge 1\), both \((-1)^n\beta _1^{(n)}(s+\lambda _1)\) and \(1 +\alpha (s)+\cdots + (\alpha (s))^{n-1}\) are completely monotone, and so is their product (by Criterion A.1 in Appendix A). Therefore, \(\gamma (s)\) is completely monotone.\(\square \)
Remark C.2
Let \(T_{\gamma }\) be a r.v. whose the probability distribution has the LST \(\gamma (s)\). Then, the expression \(Ez_2^{H_{\beta _{1,2}}}=\gamma (\lambda _2-\lambda _2 z_2)\) in (C.32) implies that \(H_{\beta _{1,2}}{\mathop {=}\limits ^\mathrm{d}}N_{\lambda _2}(T_{\gamma })\).
Lemma C.2
As \(t\rightarrow \infty \),
Proof
First, let us rewrite (C.33) as
In the following, we divide the proof of Lemma C.2 into two parts, depending on whether \(a_1\) (\(>1\)) is an integer or not.
Case 1: Non-integer \(a_1 >1\). Suppose that \(n<a_1<n+1\), \(n\in \{1,2,\ldots \}\). Since \(P\{T_{\beta _1}>t\}\sim t^{-a_1}L(t)\) and \((1-\rho _1)^{a_1+1}P\{T_{\alpha }>t\}\sim t^{-a_1}L(t)\), we know that \(\beta _{1,n}<\infty \), \(\beta _{1,n+1}=\infty \), \(\alpha _{n}<\infty \) and \(\alpha _{n+1}=\infty \). Define \(\beta _{1,n}(s)\) and \(\alpha _{n}(s)\) in a manner similar to that in (A.3). Therefore,
By Lemma A.7,
Furthermore, it follows from (C.38) that
where \(u_1,u_2,\ldots ,u_{n-1}\) are constants. By (C.36), (C.37) and (C.40), we have
where \(e_1,e_2,\ldots ,e_{n-1}\) are constants. Based on the above, we define \(\gamma _{n-1}(s)\) in a manner similar to that in (A.3). Applying (C.39), we have
Then, making use of Lemma A.7, we complete the proof of Lemma C.2 for non-integer \(a_1>1\).
Case 2: Integer \(a_{1}>1\). Suppose that \(a_1=n\in \{2,3,\ldots \}\). Since \(P\{T_{\beta _1}>t\}\sim t^{-n}L(t)\) and \((1-\rho _1)^{n+1}P\{T_{\alpha }>t\}\sim t^{-n}L(t)\), we know that \(\alpha _{n-1}<\infty \) and \(\beta _{1,n-1}<\infty \), but whether \(\alpha _{n}\) or \(\beta _{1,n}\) is finite or not remains uncertain. This uncertainty is essentially determined by whether \(\int _x^{\infty }t^{-1}L(t)\mathrm{d}t\) is convergent or not. Define \(\widehat{\beta }_{1,n-1}(s)\) and \(\widehat{\alpha }_{n-1}(s)\) in a way similar to that in (A.4). Then,
By Lemma A.8, we obtain, for \(x>0\),
Furthermore, it follows from (C.44) that
where \(u'_1,u'_2,\ldots ,u'_{n-1}\) are constants. By (C.36), (C.43) and (C.46), we have
where \(e'_1,e'_2,\ldots ,e'_{n-1}\) are constants. Based on this, we define \(\widehat{\gamma }_{n-2}(s)\) in a way similar to that in (A.4). Then,
It follows from (C.47) and (C.45) that
Applying Lemma A.8, we complete the proof of Lemma C.2 for integer \(a_1=n\in \{2,3,\ldots \}\). \(\square \)
Proof of Proposition C.1
It follows directly from Remark C.2, Lemma C.2 and Lemma A.3. \(\square \)
Referring to Remark C.1, we know from (C.31) that \(c{=}(1{-}\rho _1) \rho _1^{{-}1} \left[ 1/(1{-}\rho _1)^{a_1}{-}1\right] \). Now let us confirm that \(a_1<c<a_1/(1-\rho _1)^{a_1-1}\), which is equivalent to checking that \(a_1\rho _1(1-\rho _1)^{a_1-1}+(1-\rho _1)^{a_1}<1\) and \(a_1\rho _1+(1-\rho _1)^{a_1}>1\). This is true because \(a_1\rho _1(1-\rho _1)^{a_1-1}+(1-\rho _1)^{a_1}\) is decreasing in \(\rho _1\in (0,1)\) and \(a_1\rho _1+(1-\rho _1)^{a_1}\) is increasing in \(\rho _1\in (0,1)\).
1.2.3 Tail asymptotics for \(H_{\beta _2,2}\)
As we shall see in the next subsection, our main results do not require a detailed asymptotic expression for \(P\{H_{\beta _2,2}>j\}\). It is enough to verify that it is \(o(1)\cdot j^{-a_1+1}L(j)\) as \(j\rightarrow \infty \).
Taking \(z_1\rightarrow 1\) in (B.16), we have
It follows from (C.50) that \(H_{\beta _2,2}{\mathop {=}\limits ^\mathrm{d}}D_{k,2}\), with probability \((p/\rho _2)k b_{\beta _2,k}\), for \(k\ge 1\). Define the r.v. \(H^U_{\beta _2,2}{\mathop {=}\limits ^\mathrm{d}}D^U_{k,2}\), with probability \((p/\rho _2)k b_{\beta _2,k}\), for \(k\ge 1\). Then, by (C.23), we have, \(H_{\beta _2,2}\le _{st}H_{\beta _2,2}^{U}\). Note that \(H_{\beta _2,2}^{U}\) has the PGF
Let \(N^*\) be a r.v. with probability distribution \(P\{N^*=k\}=(p/\rho _2) k b_{\beta _2,k}\), \(k\ge 1\). Therefore, (C.51) implies \(H_{\beta _2,2}^{U}{\mathop {=}\limits ^\mathrm{d}}\sum _{k=1}^{N^*-1} Z_k\), where \(N^*\) is independent of \(Z_k\), \(k\ge 1\). Similar to (C.27), we can write
where \(\overline{b}_{\beta _2,k}=\sum _{n=k}^{\infty } b_{\beta _2,n}\). By the definition of \(b_{\beta _2,n}\) given in (3.10) and applying Lemma A.3 and Lemma A.4, we know that \(\overline{b}_{\beta _2,k}=P\{N_{\lambda }(T_{\beta _2})>k-1\}=O(1)\cdot k^{-a_2}L(k)\) as \(k\rightarrow \infty \). Furthermore, by (C.52) and applying Proposition 1.5.10 in [4], we have
As pointed out in Sect. 2, \(P\{Z_k>j\}\sim Const\cdot j^{-a_1} L(j)\) as \(j\rightarrow \infty \). By Lemma A.6, we know \(P\{H_{\beta _2,2}^{U}>j\}= O(1)\cdot \max \left( j^{-a_2+1}L(j),j^{-a_1}L(j)\right) \) as \(j\rightarrow \infty \). Since \(P\{H_{\beta _2,2}>j\}\le P\{H_{\beta _2,2}^{U}>j\}\) and \(a_2>a_1\), we have
After the above preparations, we now return to the proof of the tail asymptotic properties for \(M_{ik},\ i,k=1,2\).
By (C.15) and applying Lemma A.2, together with (C.20), we have
Immediately, from (C.16) and (C.20),
By (C.17) and applying Lemma A.5, together with (C.54),
Rights and permissions
About this article
Cite this article
Liu, B., Zhao, Y.Q. Tail asymptotics for the \(M_1,M_2/G_1,G_2/1\) retrial queue with non-preemptive priority. Queueing Syst 96, 169–199 (2020). https://doi.org/10.1007/s11134-020-09666-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-020-09666-8
Keywords
- Exhaustive stochastic decomposition approach
- Tail asymptotics
- Retrial queue
- Priority queue
- Number of customers
- Stationary distribution
- Regularly varying distribution