# Stochastic Approximations and Monotonicity of a Single Server Feedback Retrial Queue

Authors: Mohamed Boualem; Natalia Djellab; Djamil Aïssani
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

This paper focuses on stochastic comparison of the Markov chains to derive some qualitative approximations for anM/G/1 retrial queue with a Bernoulli feedback. The main objective is to use stochastic ordering techniques to establish various monotonicity results with respect to arrival rates, service time distributions, and retrial parameters.


---

## Body

## 1. Introduction

Retrial queueing systems are described by the feature that the arriving customers (or calls) who find the server busy join the orbit to try again for their requests in a random order and at random time intervals. Retrial queues are widely and successfully used as mathematical models of several computer systems and telecommunication networks. For excellent and recent bibliographies on retrial queues, the reader is referred to [1–3].Most of the queueing systems with repeated attempts assume that each customer in the retrial group seeks service independently of each other after a random time exponentially distributed with rateθ so that the probability of repeated attempt during the interval (t,t+Δt) given that there were n customers in orbit at time t is nθΔt+∘(Δt). This discipline for access to the server from the retrial group is called classical retrial policy [4, 5].Several papers on retrial queues have analyzed the systems without customer feedback. A more practical retrial queue with the Bernoulli feedback of the customers occurs in many real world situations: for instance, in communication networks where data transmissions need to be guaranteed to be error free within some specified probability, feedback schemes are used to request retransmission of packets that are lost or received in a corrupted form.Because of complexity of retrial queueing models, analytic results are generally difficult to obtain. In contrast, there are a great number of numerical and approximation methods which are of practical importance. One important approach is monotonicity which allow to establish some stochastic bounds helpful in understanding complicated models by more simpler models for which an evaluation can be made using the stochastic comparison method based on the general theory of stochastic orderings [6].Stochastic orders represent an important tool for many problems in probability and statistics. They lead to powerful approximation methods and bounds in situations where realistic stochastic models are too complex for rigorous treatment. They are also helpful in situations where fundamental model distributions are only known partially. Further details and applications about these stochastic orders may be found in [6–8].There exists a flourishing literature on stochastic comparison methods and monotonicity of queues. Oukid and Aissani [9] obtain lower bound and new upper bound for the mean busy period of GI/GI/1 queue with breakdowns and FIFO discipline. Boualem et al. [10] investigate some monotonicity properties of an M/G/1 queue with constant retrial policy in which the server operates under a general exhaustive service and multiple vacation policy relative to strong stochastic ordering and convex ordering. These results imply in particular simple insensitive bounds for the stationary queue length distribution. More recently, Taleb and Aissani [11] investigate some monotonicity properties of an unreliable M/G/1 retrial queue relative to strong stochastic ordering and increasing convex ordering.In this work, we use the tools of the qualitative analysis to investigate various monotonicity properties for anM/G/1 retrial queue with classical retrial policy and Bernoulli feedback relative to strong stochastic ordering, increasing convex ordering and the Laplace ordering. Instead of studying a performance measure in a quantitative fashion, this approach attempts to reveal the relationship between the performance measures and the parameters of the system.The rest of the paper is organized as follows. In Section2, we describe the mathematical model in detail and derive the generating function of the stationary distribution. In Section 3, we present some useful lemmas that will be used in what follows. Section 4 focusses on stochastic monotonicity of the transition operator of the embedded Markov chain and gives comparability conditions of two transition operators. Stochastic bounds for the stationary number of customers in the system are discussed in Section 5. In Section 6, we obtain approximations for the conditional distribution of the stationary queue given that the server is idle.


## 2. Description and Analysis of the Queueing System

We consider a single server retrial queue with the Bernoulli feedback at which customers arrive from outside the system according to a Poisson process with rateλ. An arriving customer receives immediate service if the server is idle, otherwise he leaves the service area temporarily to join the retrial group. Any orbiting customer produces a Poisson stream of repeated calls with intensity θ until the time at which he finds the server idle and starts his service. The service times follow a general probability law with distribution function B(x) having finite mean β1 and Laplace-Stieltjes transform β̃(s). After the customer is completely served, he will decide either to join the retrial group again for another service with probability p (0<p<1) or to leave the system forever with probability p¯(=1-p).We finally assume that the input flow of primary arrivals, intervals between repeated attempts and service times, are mutually independent.The state of the system at timet can be described by the Markov process R(t)={C(t),N(t),ζ(t)}(t≥0), where C(t) is the indicator function of the server state: C(t) is equal to 0 or 1 depending on whether the server is free or busy at time t and N(t) is the number of customers occupying the orbit. If C(t)=1, then ζ(t) corresponds to the elapsed time of the customer being served at time t.Note that the stationary distribution of the system state (the stationary joint distribution of the server state and the number of customers in the orbit) was found in [12], using the supplementary variables method. In this section, we are interested in the embedded Markov chain. To this end, we describe the structure of the latter, determine its ergodicity condition, and obtain its stationary distribution.


### 2.1. Embedded Markov Chain

Letτn be the time of the nth departure and Dn the number of customers in the orbit just after the time τn, then C(τn+)=0 and N(τn+)=Dn, ∀n≥1. We have the following fundamental recursive equation: (2.1)Dn+1=Dn+vn+1-δDn+1+η,
where (i) vn+1 is the number of primary customers arriving at the system during the service time which ends at τn+1. It does not depend on events which have occurred before the beginning of the (n+1)st service. Its distribution is given by: (2.2)kj=P(vn+1=j)=∫0∞(λx)jj!e-λxdB(x),j≥0,
with generating function K(z)=∑j≥0kjzj=β̃(λ(1-z)),(ii) the Bernoulli random variableδDn+1 is equal to 1 or 0 depending on whether the customer who leaves the service area at time τn+1 proceeds from the orbit or otherwise. Its conditional distribution is given by (2.3)P(δDn+1=1/Dn=l)=lθλ+lθ,P(δDn+1=0/Dn=l)=λλ+lθ,(iii) the random variableη is 0 or 1 depending on whether the served customer leaves the system or goes to orbit. We have also that P[η=1]=p and P[η=0]=p¯(=1-p).The sequence{Dn,n≥1} forms an embedded Markov chain with transition probability matrix P=(pij)i,j≥0, where pij=P(Dn+1=j/Dn=i), defined by(2.4)pij=λp¯λ+iθkj-i+iθp¯λ+iθkj-i+1+λpλ+iθkj-i-1+iθpλ+iθkj-i.
Note that pij≠0 only for i=0,1,…,j+1.Theorem 2.1.
The embedded Markov chain{Dn,n≥1} is ergodic if and only if ρ=λβ1+p<1.Proof.
It is not difficult to see that{Dn,n≥1} is irreducible and aperiodic. To find a sufficient condition, we use Foster's criterion which consists to show the existence of a nonnegative function f(s), s∈𝒮, and ϵ>0 such that the mean drift xs=E[f(Dn+1)-f(Dn)/Dn=s] is finite for all s∈𝒮 and xs≤-ϵ for all s∈𝒮 except perhaps a finite number. In our case, we consider the function f(s)=s for all s∈𝒮. Then, the mean drift is given by
(2.5)xs=E[f(Dn+1)-f(Dn)/Dn=s]=E[vn+1-δDn+1+η/Dn=s]=λβ1-sθλ+sθ+p.
Let x=lim⁡s→∞xs. Then x=λβ1-1+p<0. Therefore, the sufficient condition is λβ1+P<1.
To prove that the previous condition is also a necessary condition for ergodicity of our embedded Markov chain, we apply Kaplan's condition:xi<∞, for all i≥0, and there is an i0 such that xi≥0, for i≥i0. In our case, this condition is verified because pij=0 for j<i-1 and i>0 (see (2.4)).


### 2.2. Generating Function of the Stationary Distribution

Now, under the conditionρ<1, we find the stationary distribution πm=lim⁡n→∞P(Dn=m). Using (2.4), one can obtain Kolmogorov equations for the distribution πm(2.6)πm=∑n=0mλp¯λ+nθπnkm-n+∑n=1m+1nθp¯λ+nθπnkm-n+1+∑n=0m-1λpλ+nθπnkm-n-1+∑n=0mnθpλ+nθπnkm-n.
Because of presence of convolutions, these equations can be transformed with the help of the generating functions π(z)=∑m≥0πmzmandL(z)=∑m≥0(πm/λ+mθ)zm to(2.7)π(z)=β̃(λ-λz)[λp¯L(z)+θzpL′(z)+θp¯L′(z)+λpzL(z)]=β̃(λ-λz)(p¯+pz)[λL(z)+θL′(z)].
Since(2.8)π(z)=λπmλ+mθzm+mθπmλ+mθzm=λL(z)+θzL′(z),
from (2.7) and (2.8), we have(2.9)θL′(z)[(p¯+pz)β̃(λ-λz)-z]=λL(z)[1-(p¯+pz)β̃(λ-λz)].
We consider now the function f(z)=(p¯+pz)β̃(λ-λz)-z.It is easy to show that(2.10)f(1)=β̃(0)-1=1-1=0,f′(z)=-λ(p¯+pz)β̃′(λ-λz)+pβ̃(λ-λz)-1,f′(1)=-λβ̃′(0)+pβ̃(0)-1=ρ-1<0,f′′(z)=λ2(p¯+pz)β̃′′(λ-λz)≥0.
Therefore the function f(z) is decreasing on the interval [0,1], z=1 is the only zero there and for z∈[0,1) the function is positive, that is, (as ρ<1) for z∈[0,1) we have: z<(p¯+pz)β̃(λ-λz)≤1.Besides,(2.11)1-(p¯+pz)β̃(λ-λz)(p¯+pz)β̃(λ-λz)-z=ρ1-ρ<∞,
that is, the function 1-(p¯+pz)β̃(λ-λz)/(p¯+pz)β̃(λ-λz)-z can be defined at the point z=1 as ρ/1-ρ.This means that forz∈[0,1] we can rewrite (2.9) as follows:(2.12)L′(z)=λθ1-(p¯+pz)β̃(λ-λz)(p¯+pz)β̃(λ-λz)-zL(z).
The solution of the differential equation (2.12) is given by (2.13)L(z)=L(1)exp⁡⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu).
From (2.8), we have (2.14)π(z)=λ(p¯+pz)β̃(λ-λz)(1-z)(p¯+pz)β̃(λ-λz)-zL(1)exp⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu).
We obtain from the normalization condition π(1)=1 that L(1)=(1-ρ)/λ.Finally we get the following formula for the generating function of the steady state queue size distribution at departure epochs (which is known in the literature as the stochastic decomposition property):(2.15)π(z)=[(1-ρ)β̃(λ-λz)(1-z)(p¯+pz)β̃(λ-λz)-z][(p¯+pz)exp⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu)].
It is easy to see that the right hand part of expression (2.15) can be decomposed into two factors. The first factor is the generating function for the number of customers in M/G/1 queueing system with Bernoulli feedback (see [13]); the remaining one is the generating function for the number of customers in the retrial queue with feedback given that the server is idle [12]. One can see that formula (2.15) is cumbersome (it includes integrals of Laplace transform, solutions of functional equations). It is why we use, in the rest of the paper, the general theory of stochastic orderings to investigate the monotonicity properties of the system relative to the strong stochastic ordering, convex ordering, and Laplace ordering.


## 2.1. Embedded Markov Chain

Letτn be the time of the nth departure and Dn the number of customers in the orbit just after the time τn, then C(τn+)=0 and N(τn+)=Dn, ∀n≥1. We have the following fundamental recursive equation: (2.1)Dn+1=Dn+vn+1-δDn+1+η,
where (i) vn+1 is the number of primary customers arriving at the system during the service time which ends at τn+1. It does not depend on events which have occurred before the beginning of the (n+1)st service. Its distribution is given by: (2.2)kj=P(vn+1=j)=∫0∞(λx)jj!e-λxdB(x),j≥0,
with generating function K(z)=∑j≥0kjzj=β̃(λ(1-z)),(ii) the Bernoulli random variableδDn+1 is equal to 1 or 0 depending on whether the customer who leaves the service area at time τn+1 proceeds from the orbit or otherwise. Its conditional distribution is given by (2.3)P(δDn+1=1/Dn=l)=lθλ+lθ,P(δDn+1=0/Dn=l)=λλ+lθ,(iii) the random variableη is 0 or 1 depending on whether the served customer leaves the system or goes to orbit. We have also that P[η=1]=p and P[η=0]=p¯(=1-p).The sequence{Dn,n≥1} forms an embedded Markov chain with transition probability matrix P=(pij)i,j≥0, where pij=P(Dn+1=j/Dn=i), defined by(2.4)pij=λp¯λ+iθkj-i+iθp¯λ+iθkj-i+1+λpλ+iθkj-i-1+iθpλ+iθkj-i.
Note that pij≠0 only for i=0,1,…,j+1.Theorem 2.1.
The embedded Markov chain{Dn,n≥1} is ergodic if and only if ρ=λβ1+p<1.Proof.
It is not difficult to see that{Dn,n≥1} is irreducible and aperiodic. To find a sufficient condition, we use Foster's criterion which consists to show the existence of a nonnegative function f(s), s∈𝒮, and ϵ>0 such that the mean drift xs=E[f(Dn+1)-f(Dn)/Dn=s] is finite for all s∈𝒮 and xs≤-ϵ for all s∈𝒮 except perhaps a finite number. In our case, we consider the function f(s)=s for all s∈𝒮. Then, the mean drift is given by
(2.5)xs=E[f(Dn+1)-f(Dn)/Dn=s]=E[vn+1-δDn+1+η/Dn=s]=λβ1-sθλ+sθ+p.
Let x=lim⁡s→∞xs. Then x=λβ1-1+p<0. Therefore, the sufficient condition is λβ1+P<1.
To prove that the previous condition is also a necessary condition for ergodicity of our embedded Markov chain, we apply Kaplan's condition:xi<∞, for all i≥0, and there is an i0 such that xi≥0, for i≥i0. In our case, this condition is verified because pij=0 for j<i-1 and i>0 (see (2.4)).


## 2.2. Generating Function of the Stationary Distribution

Now, under the conditionρ<1, we find the stationary distribution πm=lim⁡n→∞P(Dn=m). Using (2.4), one can obtain Kolmogorov equations for the distribution πm(2.6)πm=∑n=0mλp¯λ+nθπnkm-n+∑n=1m+1nθp¯λ+nθπnkm-n+1+∑n=0m-1λpλ+nθπnkm-n-1+∑n=0mnθpλ+nθπnkm-n.
Because of presence of convolutions, these equations can be transformed with the help of the generating functions π(z)=∑m≥0πmzmandL(z)=∑m≥0(πm/λ+mθ)zm to(2.7)π(z)=β̃(λ-λz)[λp¯L(z)+θzpL′(z)+θp¯L′(z)+λpzL(z)]=β̃(λ-λz)(p¯+pz)[λL(z)+θL′(z)].
Since(2.8)π(z)=λπmλ+mθzm+mθπmλ+mθzm=λL(z)+θzL′(z),
from (2.7) and (2.8), we have(2.9)θL′(z)[(p¯+pz)β̃(λ-λz)-z]=λL(z)[1-(p¯+pz)β̃(λ-λz)].
We consider now the function f(z)=(p¯+pz)β̃(λ-λz)-z.It is easy to show that(2.10)f(1)=β̃(0)-1=1-1=0,f′(z)=-λ(p¯+pz)β̃′(λ-λz)+pβ̃(λ-λz)-1,f′(1)=-λβ̃′(0)+pβ̃(0)-1=ρ-1<0,f′′(z)=λ2(p¯+pz)β̃′′(λ-λz)≥0.
Therefore the function f(z) is decreasing on the interval [0,1], z=1 is the only zero there and for z∈[0,1) the function is positive, that is, (as ρ<1) for z∈[0,1) we have: z<(p¯+pz)β̃(λ-λz)≤1.Besides,(2.11)1-(p¯+pz)β̃(λ-λz)(p¯+pz)β̃(λ-λz)-z=ρ1-ρ<∞,
that is, the function 1-(p¯+pz)β̃(λ-λz)/(p¯+pz)β̃(λ-λz)-z can be defined at the point z=1 as ρ/1-ρ.This means that forz∈[0,1] we can rewrite (2.9) as follows:(2.12)L′(z)=λθ1-(p¯+pz)β̃(λ-λz)(p¯+pz)β̃(λ-λz)-zL(z).
The solution of the differential equation (2.12) is given by (2.13)L(z)=L(1)exp⁡⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu).
From (2.8), we have (2.14)π(z)=λ(p¯+pz)β̃(λ-λz)(1-z)(p¯+pz)β̃(λ-λz)-zL(1)exp⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu).
We obtain from the normalization condition π(1)=1 that L(1)=(1-ρ)/λ.Finally we get the following formula for the generating function of the steady state queue size distribution at departure epochs (which is known in the literature as the stochastic decomposition property):(2.15)π(z)=[(1-ρ)β̃(λ-λz)(1-z)(p¯+pz)β̃(λ-λz)-z][(p¯+pz)exp⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu)].
It is easy to see that the right hand part of expression (2.15) can be decomposed into two factors. The first factor is the generating function for the number of customers in M/G/1 queueing system with Bernoulli feedback (see [13]); the remaining one is the generating function for the number of customers in the retrial queue with feedback given that the server is idle [12]. One can see that formula (2.15) is cumbersome (it includes integrals of Laplace transform, solutions of functional equations). It is why we use, in the rest of the paper, the general theory of stochastic orderings to investigate the monotonicity properties of the system relative to the strong stochastic ordering, convex ordering, and Laplace ordering.


## 3. Preliminaries

### 3.1. Stochastic Orders and Ageing Notions

First, let us recall some stochastic orders and ageing notions which are most pertinent to the main results to be developed in the subsequent section.Definition 3.1.
For two random variablesX and Y with densities f and g and cumulative distribution functions F and G, respectively, let F¯=1-F and G¯=1-G be the survival functions. As the ratios in the statements below are well defined, X is said to be smaller than Y in: (a)
stochastic ordering (denoted byX≤stY) if and only if F¯(x)≤G¯(x), ∀x≥0,(b)
increasing convex ordering (denoted byX≤icxY) if and only if ∫x+∞F¯(u)d(u)≤∫x+∞G¯(u)d(u),∀x≥0,(c)
Laplace ordering (denoted byX≤LY) if and only if ∫0+∞exp⁡(-sx)dF(x)≥∫0+∞exp⁡(-sx)dG(x),∀s≥0. If the random variables of interest are of discrete type and ω=(ωn)n≥0, β=(βn)n≥0 are the corresponding distributions, then the definitions above can be given in the following forms:  (a)
ω≤stβ if and only if ω¯m=∑n≥mωn≤β¯m=∑n≥mβn, for all m,(b)
ω≤icxβ if and only if ω¯¯m=∑n≥m∑k≥nωk≤β¯¯m=∑n≥m∑k≥nβk, for all m,(c)
ω≤Lβ if and only if ∑n≥0ωnzn≥∑n≥0βnzn, for all z∈[0,1].For a comprehensive discussion on these stochastic orders see [6–8].Definition 3.2.
LetX be a positive random variable with distribution function F:  (a)
F is HNBUE (harmonically new better than used in expectation) if and only if F≤icxF*,(b)
F is HNWUE (harmonically new worse than used in expectation) if and only if F≥icxF*,(c)
F is of class ℒ if and only if F≥sF*,where F* is the exponential distribution function with the same mean as F.


### 3.2. Some Useful Lemmas

Consider twoM/G/1 retrial queues with classical retrial policy and Bernoulli feedback with parameters λ(i) and B(i), i=1,2. Let kj(i)=∫0+∞((λ(i)x)j/j!)e-λ(i)xdB(i)(x) be the distribution of the number of primary calls which arrive during the service time of a call in the ith system.The following lemma turns out to be a useful tool for showing the monotonicity properties of the embedded Markov chain.Lemma 3.3.
Ifλ(1)≤λ(2) and B(1)≤sB(2), then {kn(1)}≤s{kn(2)}, where ≤s is either ≤st or ≤icx.Proof.
To prove that{kn(1)}≤s{kn(2)}, we have to establish the usual numerical inequalities:
(3.1)k¯n(1)=km(1)≤k¯n(2),(for≤s=≤st-ordering),k¯¯n(1)=k¯m(1)≤k¯¯n(2),(for≤s=≤icx-ordering).
The rest of the proof is known in the more general setting of a random summation.The next lemma is key to proving the main result in Section6.Lemma 3.4.
Ifλ(1)≤λ(2) and B(1)≤LB(2), then {kn(1)}≤L{kn(2)}.Proof.
We have,K(i)(z)=∑n≥0kn(i)zn=β̃(i)(λ(i)(1-z)),i=1,2, where K(1)(z), K(2)(z) are the corresponding distributions of the number of new arrivals during a service time.
Letλ(1)≤λ(2), B(1)≤LB(2). To prove that {kn(1)}≤L{kn(2)}, we have to establish that
(3.2)β̃(1)(λ(1)(1-z))≥β̃(2)(λ(2)(1-z)).
The inequality B(1)≤LB(2) means that β̃(1)(s)≥β̃(2)(s) for all s≥0.
In particular, fors=λ(1)(1-z) we have
(3.3)β̃(1)(λ(1)(1-z))≥β̃(2)(λ(1)(1-z)).
Since any Laplace transform is a decreasing function, λ(1)≤λ(2) implies that
(3.4)β̃(2)(λ(1)(1-z))≥β̃(2)(λ(2)(1-z)).
By transitivity, (3.3) and (3.4) give (3.2).


## 3.1. Stochastic Orders and Ageing Notions

First, let us recall some stochastic orders and ageing notions which are most pertinent to the main results to be developed in the subsequent section.Definition 3.1.
For two random variablesX and Y with densities f and g and cumulative distribution functions F and G, respectively, let F¯=1-F and G¯=1-G be the survival functions. As the ratios in the statements below are well defined, X is said to be smaller than Y in: (a)
stochastic ordering (denoted byX≤stY) if and only if F¯(x)≤G¯(x), ∀x≥0,(b)
increasing convex ordering (denoted byX≤icxY) if and only if ∫x+∞F¯(u)d(u)≤∫x+∞G¯(u)d(u),∀x≥0,(c)
Laplace ordering (denoted byX≤LY) if and only if ∫0+∞exp⁡(-sx)dF(x)≥∫0+∞exp⁡(-sx)dG(x),∀s≥0. If the random variables of interest are of discrete type and ω=(ωn)n≥0, β=(βn)n≥0 are the corresponding distributions, then the definitions above can be given in the following forms:  (a)
ω≤stβ if and only if ω¯m=∑n≥mωn≤β¯m=∑n≥mβn, for all m,(b)
ω≤icxβ if and only if ω¯¯m=∑n≥m∑k≥nωk≤β¯¯m=∑n≥m∑k≥nβk, for all m,(c)
ω≤Lβ if and only if ∑n≥0ωnzn≥∑n≥0βnzn, for all z∈[0,1].For a comprehensive discussion on these stochastic orders see [6–8].Definition 3.2.
LetX be a positive random variable with distribution function F:  (a)
F is HNBUE (harmonically new better than used in expectation) if and only if F≤icxF*,(b)
F is HNWUE (harmonically new worse than used in expectation) if and only if F≥icxF*,(c)
F is of class ℒ if and only if F≥sF*,where F* is the exponential distribution function with the same mean as F.


## 3.2. Some Useful Lemmas

Consider twoM/G/1 retrial queues with classical retrial policy and Bernoulli feedback with parameters λ(i) and B(i), i=1,2. Let kj(i)=∫0+∞((λ(i)x)j/j!)e-λ(i)xdB(i)(x) be the distribution of the number of primary calls which arrive during the service time of a call in the ith system.The following lemma turns out to be a useful tool for showing the monotonicity properties of the embedded Markov chain.Lemma 3.3.
Ifλ(1)≤λ(2) and B(1)≤sB(2), then {kn(1)}≤s{kn(2)}, where ≤s is either ≤st or ≤icx.Proof.
To prove that{kn(1)}≤s{kn(2)}, we have to establish the usual numerical inequalities:
(3.1)k¯n(1)=km(1)≤k¯n(2),(for≤s=≤st-ordering),k¯¯n(1)=k¯m(1)≤k¯¯n(2),(for≤s=≤icx-ordering).
The rest of the proof is known in the more general setting of a random summation.The next lemma is key to proving the main result in Section6.Lemma 3.4.
Ifλ(1)≤λ(2) and B(1)≤LB(2), then {kn(1)}≤L{kn(2)}.Proof.
We have,K(i)(z)=∑n≥0kn(i)zn=β̃(i)(λ(i)(1-z)),i=1,2, where K(1)(z), K(2)(z) are the corresponding distributions of the number of new arrivals during a service time.
Letλ(1)≤λ(2), B(1)≤LB(2). To prove that {kn(1)}≤L{kn(2)}, we have to establish that
(3.2)β̃(1)(λ(1)(1-z))≥β̃(2)(λ(2)(1-z)).
The inequality B(1)≤LB(2) means that β̃(1)(s)≥β̃(2)(s) for all s≥0.
In particular, fors=λ(1)(1-z) we have
(3.3)β̃(1)(λ(1)(1-z))≥β̃(2)(λ(1)(1-z)).
Since any Laplace transform is a decreasing function, λ(1)≤λ(2) implies that
(3.4)β̃(2)(λ(1)(1-z))≥β̃(2)(λ(2)(1-z)).
By transitivity, (3.3) and (3.4) give (3.2).


## 4. Stochastic Monotonicity of Transition Operator

LetQ be the transition operator of an embedded Markov chain, which associates to every distribution ω={pi}i≥0, a distribution Qω={qj}j≥0 such that qj=∑ipipij.Corollary 4.1 (see [6]).
The operatorQ is monotone with respect to ≤st if and only if p¯nm-p¯n-1m≥0, and is monotone with respect to ≤icx if and only if p¯¯n-1m+p¯¯n+1m-2p¯¯nm≥0,∀n,m. Here, p¯nm=∑l=m∞pnl and p¯¯nm=∑l=m∞p¯nl.Theorem 4.2.
The transition operatorQ of the embedded chain {Dn,n≥1} is monotone with respect to the orders ≤st and ≤icx.Proof.
We have(4.1)p¯nm=pnk=k¯m-n+λpλ+nθkm-n-1-nθp¯λ+nθkm-n,p¯¯nm=r¯nk=k¯¯m-n+λpλ+nθk¯m-n-1-nθp¯λ+nθk¯m-n.
Thus
(4.2)p¯nm-p¯n-1m=λ2p¯+(n-1)λθ+n(n-1)θ2p(λ+nθ)(λ+(n-1)θ)km-n+(n-1)θp¯λ+(n-1)θkm-n+1+λpλ+nθkm-n-1≥0,p¯¯n-1m+p¯¯n+1m-2p¯¯nm=λpλ+(n+1)θkm-n-2+(n-1)θp¯λ+(n-1)θkm-n+λ2p¯+(n-p)λθ+n(n+1)θ2p(λ+nθ)(λ+(n+1)θ)km-n-1+2θ2(λ+nθ)(λ+(n-1)θ)(λ+(n+1)θ)k¯m-n≥0.
Based on Corollary 4.1 we obtain the stated result.In Theorem4.3, we give comparability conditions of two transition operators. Consider two M/G/1 retrial queues with classical retrial policy and feedback with parameters λ(1),θ(1),p(1),B(1), and λ(2),θ(2),p(2),B(2), respectively. Let Q1, Q2 be the transition operators of the corresponding embedded Markov chains.Theorem 4.3.
Ifλ(1)≤λ(2),θ(1)≥θ(2),p(1)≤p(2),B(1)≤sB(2), where ≤s is either ≤st or ≤icx, then Q1≤sQ2, that is, for any distribution ω, one has Q1ω≤sQ2ω.Proof.
From Stoyan [6], we wish to establish that
(4.3)p¯nm(1)≤p¯nm(2),∀n,m,(for≤s=≤st-ordering),(4.4)p¯¯nm(1)≤p¯¯nm(2),∀n,m,(for≤s=≤icx-ordering).
To prove inequality (4.3), we have (for i=1,2)
(4.5)p¯nm(i)=k¯m-n(i)+λ(i)p(i)λ(i)+nθ(i)km-n-1(i)-nθ(i)p¯(i)λ(i)+nθ(i)km-n(i).
By hypothesis, we have that
(4.6)λ(1)≤λ(2),θ(1)≥θ(2)⟹{λ(1)θ(1)≤λ(2)θ(2),orθ(1)λ(1)≥θ(2)λ(2).
Since the function G(x)=x/(x+n) is increasing, we have
(4.7)G(λ(1)θ(1))=λ(1)λ(1)+nθ(1)≤G(λ(2)θ(2))=λ(2)λ(2)+nθ(2).
Moreover, p(1)≤p(2). Then
(4.8)λ(1)λ(1)+nθ(1)p(1)≤λ(2)λ(2)+nθ(2)p(2).
Similarly, the function H(x)=x/(1+x) is increasing, we have
(4.9)H(nθ(1)λ(1))=nθ(1)λ(1)+nθ(1)≥H(nθ(2)λ(2))=nθ(2)λ(2)+nθ(2).
Besides, p(1)≤p(2) implies that p¯(1)≥p¯(2). Hence
(4.10)-nθ(1)λ(1)+nθ(1)p¯(1)≤-nθ(2)λ(2)+nθ(2)p¯(2).
Using inequalities (4.8)–(4.10) and Lemma 3.3 (for  ≤s=≤st-ordering) we get
(4.11)p¯nm(1)=k¯m-n(1)+λ(1)p(1)λ(1)+nθ(1)km-n-1(1)-nθ(1)p¯(1)λ(1)+nθ(1)km-n(1)≤k¯m-n(1)+λ(2)p(2)λ(2)+nθ(2)km-n-1(1)-nθ(2)p¯(2)λ(2)+nθ(2)km-n(1)=λ(2)p¯(2)λ(2)+nθ(2)k¯m-n(1)+nθ(2)p¯(2)λ(2)+nθ(2)k¯m-n+1(1)+λ(2)p(2)λ(2)+nθ(2)k¯m-n-1(1)+nθ(2)p(2)λ(2)+nθ(2)k¯m-n(1)≤p¯nm(2).
Following the technique above and using Lemma 3.3 (for  ≤s=≤icx-ordering), we establish inequality (4.4).


## 5. Stochastic Bounds for the Stationary Distribution

Consider twoM/G/1 retrial queues with classical retrial policy and feedback with parameters λ(1),θ(1),p(1),B(1) and λ(2),θ(2),p(2),B(2), respectively, and let πn(1), πn(2) be the corresponding stationary distributions of the number of customers in the system.Theorem 5.1.
Ifλ(1)≤λ(2),θ(1)≥θ(2),p(1)≤p(2),B(1)≤sB(2), then {πn(1)}≤s{πn(2)}, where ≤s is one of the symbols ≤st or ≤icx.Proof.
Using Theorems4.2 and 4.3 which state, respectively, that Qi are monotone with respect to the order ≤s and Q1≤sQ2, we have by induction Q1,nω≤sQ2,nω for any distribution ω, where Qi,n=Qi(Qi,n-1ω). Taking the limit, we obtain the stated result.Based on Theorem5.1 we can establish insensitive stochastic bounds for the generating function of the stationary distribution of the embedded Markov chain defined in (2.15).Theorem 5.2.
For anyM/G/1 retrial queue with classical retrial policy and Bernoulli feedback the distribution πn is greater relative to the increasing convex ordering than the distribution with the generating function
(5.1)π*(z)=[(1-ρ)eλβ1(z-1)(1-z)(p¯+pz)eλβ1(z-1)-z][(p¯+pz)exp⁡⁡(λθ∫1z1-(p¯+pu)eλβ1(u-1)(p¯+pu)eλβ1(u-1)-udu)].Proof.
Consider an auxiliaryM/D/1 retrial queue with classical retrial policy and feedback having the same arrival rate λ, retrial rate θ, mean service time β1, and probability p, as those of the M/G/1 retrial queue with classical retrial policy and Bernoulli feedback. The service times follow a deterministic low with distribution function:
(5.2)B⋆(x)={0,ifx≤β1,1,ifx>β1.
From Stoyan [6], it is known that B⋆(x)≤icxB(x). Therefore, the required result follows from Theorem 5.1.Theorem 5.3.
If in theM/G/1 retrial queue with classical retrial policy and feedback the service time distribution B(x) is HNBUE (or HNWUE), then {πn}≤icx{πn*} (or {πn*}≤icx{πn}), where {πn*} is the stationary distribution of the number of customers in the M/M/1 retrial queue with classical retrial policy and Bernoulli feedback with the same parameters as those of the M/G/1 retrial queue with classical retrial policy and Bernoulli feedback.Proof.
Consider an auxiliaryM/M/1 retrial queue with classical retrial policy and Bernoulli feedback with the same arrival rate λ, probability p, retrial rate θ, and mean service time β1 as in the M/G/1 retrial queue with classical retrial policy and Bernoulli feedback, but with exponentially distributed service time B*(x)=1-exp⁡(-(x/β1)). If B(x) is HNBUE, then B(x)≤icxB*(x) (if B(x) is HNWUE, then B*(x)≤icxB(x)). Therefore, by using Theorem 5.1, we deduce the statement of this theorem.


## 6. Stochastic Approximations for the Conditional Distribution

We consider the conditional distributionφn of the stationary queue given that the server is idle. This distribution has also appeared in the stochastic decomposition law for the stationary queue length, see equation (2.15). As we saw its generating function ϕ(z)=∑n≥0φnzn was given by (6.1)ϕ(z)=(p¯+pz)exp⁡(-λθ∫z11-(p¯+pu)β̃(λ-λu)(p¯+pu)β̃(λ-λu)-udu).Theorem 6.1.
Suppose we have twoM/G/1 retrial queues with classical retrial policy and Bernoulli feedback with parameters λ(1),θ(1),p(1),B(1) and λ(2),θ(2),p(2),B(2), respectively. If λ(1)≤λ(2),θ(1)≥θ(2),p(1)≤p(2),B(1)(x)≤LB(2)(x), then φn(1)≤Lφn(2).Proof.
By Lemma3.4, we have β̃(1)(λ(1)(1-z))≥β̃(2)(λ(2)(1-z)).
Moreover, one hasp(1)≤p(2)⇒p¯(1)+p(1)z≥p¯(2)+p(2)z,forallz∈[0,1].
This implies that(6.2)1-(p¯(1)+p(1)u)β̃(1)(λ(1)-λ(1)u)(p¯(1)+p(1)u)β̃(1)(λ(1)-λ(1)u)-u≤1-(p¯(2)+p(2)u)β̃(2)(λ(2)-λ(2)u)(p¯(2)+p(2)u)β̃(2)(λ(2)-λ(2)u)-u.
Besides, λ(1)≤λ(2) and θ(1)≥θ(2)⇒(λ(1)/θ(1))≤(λ(2)/θ(2)) and thus
(6.3)λ(1)θ(1)∫z11-(p¯(1)+p(1)u)β̃(1)(λ(1)-λ(1)u)(p¯(1)+p(1)u)β̃(1)(λ(1)-λ(1)u)-udu≤λ(2)θ(2)∫z11-(p¯(2)+p(2)u)β̃(2)(λ(2)-λ(2)u)(p¯(2)+p(2)u)β̃(2)(λ(2)-λ(2)u)-udu.
Therefore
(6.4)exp⁡(-λ(1)θ(1)∫z11-(p¯(1)+p(1)u)β̃(1)(λ(1)-λ(1)u)(p¯(1)+p(1)u)β̃(1)(λ(1)-λ(1)u)-udu)≥exp⁡(-λ(2)θ(2)∫z11-(p¯(2)+p(2)u)β̃(2)(λ(2)-λ(2)u)(p¯(2)+p(2)u)β̃(2)(λ(2)-λ(2)u)-udu).
By combining this latter inequality with the inequality: p¯(1)+p(1)z≥p¯(2)+p(2)z, we get ϕ(1)(z)≥ϕ(2)(z)forallz∈[0,1], which means the stochastic inequality {φn(1)}≤L{φn(2)}.Theorem 6.2.
For anyM/G/1 retrial queue with classical retrial policy and Bernoulli feedback the distribution φn is less relative to the Laplace ordering than the distribution with the generating function
(6.5)(p¯+pz)exp⁡(-λθ∫z11-(p¯+pu)eλβ1(u-1)(p¯+pu)eλβ1(u-1)-udu),
and if B(x) is of class ℒ then the distribution φn is greater relative to the ordering ≤L than the corresponding distribution in the M/M/1 queue with classical retrial policy and Bernoulli feedback.Proof.
Consider an auxiliaryM/D/1 and M/M/1 retrial queues with classical retrial policy and Bernoulli feedback with the same arrival rates λ, probability p, retrial rates θ, and mean service times β1.
SinceB(x) is always less, relative to the ordering ≤L, than a deterministic distribution with the same mean value, based on Theorem 6.1 we obtain the stated result.
IfB(x) is of class ℒ then B(x) is greater relative to the ordering ≤L than the exponential distribution with the same mean, based on Theorem 6.1 we can guarantee the second inequality.


## 7. Conclusion and Further Research

In this paper, we prove the monotonicity of the transition operator of the embedded Markov chain relative to strong stochastic ordering and increasing convex ordering. We obtain comparability conditions for the distribution of the number of customers in the system. Inequalities are derived for conditional distribution of the stationary queue given that the server is idle. The obtained results allow us to place in a prominent position the insensitive bounds for both the stationary distribution and the conditional distribution of the stationary queue of the considered model.Monotonicity results are of importance in robustness analysis: if there is insecurity on the input of the model, then our order results provide information on what kind of deviation from the nominal model to expect. Moreover, in gradient estimation one has to control the growth of the cycle length as function of a change of the model. More precisely, the results established in this paper allow to bound the measure-valued derivative of the stationary distribution where the derivative can be translated into unbiased (higher order) derivative estimators with respect to some parameter (e.g., arrival rate (λ) or retrial rate (θ) parameter). Such bounds can be used to derive information on the speed of convergence of the gradient estimator. Finally, under some conditions (order holds in the strong sense), those results imply a fast convergence of the gradient estimator of the stationary distribution [14–16].



---

*Source: 536982-2012-03-25.xml*