# Several Types of Convergence Rates of the M/G/1 Queueing System

Authors: Xiaohua Li; Jungang Li
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

We study the workload process of the M/G/1 queueing system. Firstly, we give the explicit criteria for the geometric rate of convergence and the geometric
decay of stationary tail. And the parametersε0 and s0 for the geometric rate of convergence and the geometric decay of the stationary tail are obtained, respectively. Then, we give the explicit criteria for the rate of convergence and decay of stationary tail for three specific types of subgeometric cases. And we give the parameters ε1 and s1 of the rate of convergence and the decay of the stationary tail, respectively, for the subgeometric rate r(n)=exp(sn1/(1+α)), s>0, α>0.


---

## Body

## 1. Introduction

We consider several types of convergence rates of theM/G/1 queueing system by using drift conditions. The M/G/1 queueing system discussed here is that the arrivals form a Poisson process with parameter λ. The service times ν1,ν2,… for the customers are independently identically distributed random variables with a common distribution function B(x). Let
(1)1μ≡∫0∞xdB(x),ρ≡λμ,
where μ>0 is a constant, and ρ is called the service intensity. Denote the workload process of the M/G/1 queueing system by W(t); then, {W(t),t≥0} is a Markov process.Ergodicity, specially ordinary ergodicity, has been well studied for Markov processes. There are a large volume of references devoted to the geometric case (or exponential case) and the subgeometric case (e.g., see [1–3]). Hou and Liu [4, 5] discussed ergodicity of embedded M/G/1 and GI/M/n queues, polynomial and geometric ergodicity for M/G/1-type Markov chain, and processes by generating function of the first return probability. Hou and Li [6, 7] obtained the explicit necessary and sufficient conditions for polynomial ergodicity and geometric ergodicity for the class of quasi-birth-and-death processes by using matrix geometric solutions.There is much work on decay of the tail in the stationary distribution. Li and Zhao [8, 9] studied heavy-tailed asymptotic and light-tailed asymptotic of stationary probability vectors of Markov chains of GI/G/1 type. Jarner and Roberts [10] discussed Foster-Lyapounov-type drift conditions for Markov chains which imply polynomial rate convergence to stationarity in appropriate V-norms. Jarner and Tweedie [11] proved that the geometric decay of the tail in the stationary distribution is a necessary condition for the geometric-ergodicity for random walk-type Markov chains. We will discuss several types of ergodicity and the tail asymptotic behavior of the stationary distribution by Foster-Lyapounov- drift conditions. We give the relationship of ergodicity and the decay of the tail in the stationary distribution for h-skeleton chain in M/G/1 queueing system, which is different from the former; ergodicity and the decay of the tail are discussed, respectively. We shall give the bounded interval in which geometric and subexponential parameter s lies and prove that it is determined by the tail of the service distribution. The parameters ε0 and s0 for geometric rate of convergence and the geometric decay of the stationary tail are obtained, respectively. We shall also give explicit criteria for the rate of convergence and decay of stationary tail for three specific types of subgeometric cases (Case 1: the rate function r(n)=exp(sn1/(1+α)),α>0,s>0; Case 2: polynomial rate function r(n)=nα,α>0; Case 3: logarithmic rate function r(n)=logαn,α>0). And we give the parameters ε1 and s1 of the rate of convergence and the decay of the stationary tail, respectively, for the subgeometric rate in Case 1.We organize the paper as follows. In Section2, we shall introduce basic definitions and theorems, including the main result, Theorem 6. In Section 3, we shall prove the geometric rates of convergence in Theorem 6. In Section 4, we shall prove the rates of convergence for the subgeometric Cases 1–3 in Theorem 6.


## 2. Basic Definitions and the Main Results

Let{Xn,n≥0} be a discrete time Markov chain on the state space (E,ℰ) with transition kernel P. Assume that it is ψ-irreducible, aperiodic, and positive recurrent. Now, we discuss the convergence in f-norm of the iterates Pn of the kernel to the stationary distribution π at rate r:=(r(n),n≥0); that is, for all A∈ℰ,
(2)limn→∞r(n)∥P(n)(x,A)-π(A)∥f=0,π-a.e.,
where f:E→[1,+∞) satisfies π(f)<+∞, and for all signed measures σ, the f-norm ||σ||f is defined as sup|g|≤f|σ(g)|.Geometric Rate Function. That is, the function r satisfies
(3)0<liminflogr(n)n≤limsuplogr(n)n<+∞.Subgeometric Rate Function. That is, the function r satisfies
(4)limn→∞logr(n)n=0.
The class of subgeometric rates function includes polynomial rates functions; that is, r(n)=nα,α>0, and rate functions which increase faster than the polynomial ones; r(n)=exp(sn1/(1+α)),α>0,s>0.We shall discuss geometric rates of convergencer(n)=exp(sn),s>0, subgeometric rate of convergence r(n)=exp(sn1/(1+α)),α>0,s>0, polynomial rate of convergence r(n)=nα,α>0, and logarithmic rate of convergence r(n)=logαn,α>0.Condition
D
(
ϕ
,
V
,
C
)
.There exist a function V:E→[1,∞), a concave monotone nondecreasing differentiable function ϕ:[1,∞]→(0,∞], a measurable set C, and a finite constant b such that
(5)ΔV(x)=PV(x)-V(x)≤ϕ∘V+bIC,
where IC is the indicator function of the set C.Now we shall give Theorems1 and 2 which we will use in this paper.Theorem 1 (Theorem  14.0.1 in [1]).
IfD(ϕ,V,C) holds for some petite set C and there exists x0∈E such that V(x0)<∞, then there exists a unique invariant distribution π, π(ϕ∘V)<∞ and
(6)limn→∞∥P(n)(x,A)-π(A)∥ϕ∘V=0,π-a.e.,
where ϕ∘V(x)≥1,x∈E.Theorem 2 (Proposition 2.5 in Douc et al. [12]).
LetP be a ψ-irreducible and aperiodic kernel. Assume that D(ϕ,V,C) holds for function ϕ with limt→+∞ϕ′(t)=0, a petite set C, and a function V with {V<+∞}≠∅. Then, there exists an invariant probability measure π, and for all x in the full and absorbing set {V<∞},
(7)limn→∞rϕ(n)∥P(n)(x,A)-π(A)∥=0,
where (rϕ(n))=ϕ∘Hϕ-1(n), Hϕ(v):=∫1v‍(1/ϕ(x))dx.Sinceϕ is a concave monotone nondecreasing differentiable function, ϕ′ is nonincreasing. Then, there exists c∈[0,1), such that limt→+∞ϕ′(t)=c. In Theorem 2, for the case c∈(0,1), condition D(ϕ,V,C) implies that the chain is geometric ergodic, but the rate in the geometric convergence property cannot be achieved under the condition that limt→+∞ϕ′(t)=c>0.The workload process{W(t),t≥0} of the M/G/1 queueing system is a Markov process on the state space {R+,ℬ(R+)}. {W(nh)} is an h-skeleton of {W(t),t≥0}. We choose h=1, and denote {W(nh)}h=1 by {Xn}. Suppose that the workload can be decreased by min{1,Xn} during the time interval [n,n+1]. And suppose that the transition kernel of {Xn} is P(x,·). For convenience, let σk=ν1+ν2+⋯+νk. Then,
(8)Xn+1=∑k=1+∞‍I{ξ=k}σk+min{Xn-1,0},n=1,2,…,
where ξ is the number of arrivals in a time interval of unit length.Lemma 3.
{
X
n
} is irreducible and aperiodic.Proof.
Letφ be a measure on R+ with φ({0})=1,φ({0}c)=0. For all x∈R+, there exists a k satisfying k-1<t≤k, such that
(9)Pk(x,{0})≥exp(-λk)>0.
Hence, {Xn} is irreducible. From
(10)Pn(x,{0})>0,n≥1,
we know that {Xn} is also aperiodic.Lemma 4.
C
=
[
0
,
c
] is petite set, where c(c≥0) is a real number.Proof.
Let[c] be the maximum integer no more than c. Since
(11)P[c]+1(x,{0})≥exp{-λ([c]+1)}>0,∀x∈C,
and C is a closed set, we know that minx∈CP[c]+1(x,{0})>0. Let ν2 be a measure on R+ satisfying, for all B∈ℬ(R+),
(12)ν2(B)={0,{0}∉B,minx∈CP[c]+1(x,{0}),{0}∈B.
Obviously, for all x∈C,
(13)P[c]+1(x,B)≥ν2(B),∀ℬ(R+).
Thus, we get that C is a petite set.Lemma 5.
The Markov chain{Xn} is stochastically monotonic.Proof.
For every fixedy, from
(14)P{Xn+1≤y∣Xn=x}=P{∑k=1+∞‍I{ξ=k}σk≤y},∀x∈[0,1],P{Xn+1≤y∣Xn=x}=P{∑k=1+∞‍I{ξ=k}σk+x-1≤y},=P{∑k=1+∞‍I{ξ=k}σk-y-1≤-x},∀x∈[1,+∞),
we obtain that P{Xn+1≤y∣Xn=x} is nonincreasing in x. That is, {Xn} is stochastically monotonic.For two sequencesun and vn, we write un≍vn, if there exist positive constants c1 and c2 such that, for large n, c1un≤vn≤c2un.Let us say that the distribution functionG of a random variable ξ is in 𝒢+(r) if
(15)Eesξ=∫0+∞‍esxG(dx)<+∞,0<s≤r;
the distribution function G of a random variable ξ is in 𝒮+(r,α) if
(16)Eesξ1/(1+α)=∫0+∞‍esx1/(1+α)G(dx)<+∞,0<s≤r,
where r>0, and α>0.Now, we give the main result.Theorem 6.
Suppose thatρ<1 and π is the stationary distribution of {Xn}.
(
1
) If B∈𝒢+(r), then one has
(17)∫1+∞‍exp(sx)π(dx)<+∞,∀0<s<s0,
where s0 is the minimum positive root of the equation Eesν1=1+(s/λ). Moreover, {Xn} is geometrically ergodic,
(18)limn→∞eε0n∥P(n)(x,A)-π(A)∥=0,
where ε0=λ+s--λEes-ν1, and s-∈(0,s0) is a root of the equation Eν1esν1=1/λ.
(
2
) If B∈𝒮+(r,α), then one has
(19)∫1+∞‍x-α/(1+α)exp(sx1/(1+α))π(dx)<∞,0<s<s1,
where s1 is the minimal positive solution of β(s)=0(β(s)=xα/(1+α){1-∑k=0∞(λke-λ/k!)Eexp{s(σk-1+x)1/(1+α)-sx1/(1+α)}}). And
(20)limn→∞n(-α/(1+α))exp(ε1n1/(1+α))∥P(n)(x,·)-π(·)∥=0,
where ε1=maxs∈(0,s1)[(α+1)β(s)]1/(α+1).
(
3
) If there exists a constant α>1, such that Eν1α=∫0+∞‍xαB(dx)<+∞, then
(21)limn→∞nα-1∥P(n)(x,·)-π(·)∥=0,∫1+∞‍xα-1π(dx)<+∞.
(
4
) If there exists an integer number α>0, such that Eν1logα(ν1+1)=∫0+∞‍xlogα(x+1)B(dx)<+∞, then
(22)limn→∞logαn∥P(n)(x,·)-π(·)∥=0,∫1+∞‍logαxπ(dx)<+∞.We shall prove Theorem6 in Sections 3 and 4.


## 3. Geometric Rate of Convergence

The Markov chain{Xn} is geometrically ergodic if (2) holds with r(n)=esn for some s>0. By Theorem  15.0.1 in [1], an equivalent condition of geometric ergodicity is that there exist a petite set C, constants β>0 and b<∞, and a function V≥1 finite for at least one x0∈E satisfying
(23)ΔV(x)<-βV(x)+bIC,x∈E.
By using the drift previous condition, we usually obtain the geometric ergodicity, but we could not get the parameters for the geometric rate of convergence. Now, we will study the geometric decay of the stationary tail and geometric rate of convergence to the stationary distribution.LetVs(x)=exp(sx),0<s≤r,x∈R+. Taking the petite set C=[0,1], for all x∈[0,1],
(24)ΔVs(x)=PVs(x)-Vs(x)<∑k=0∞‍λke-λk!Eexp{s(ν1+⋯+νk+x)}≤∑k=0∞‍λkk!(Eesν1)kex=exp(λEesν1)ex.
Since B∈𝒢+(r)(i.e., Eesν1<∞,0<s≤r), we know that
(25)ΔVs(x)<exp(λEesν1)ex<∞,∀x∈[0,1].
For all x>1 (i.e., x∈CC),
(26)ΔVs(x)=PVs(x)-Vs(x)=-exp(sx)+exp(sx)∑k=0∞‍λke-λk!Eexp{s(σk-1)}=-exp(sx){1-exp(-λ-s)∑k=0∞‍λkk!(Eesν1)k}=-exp(sx){1-exp(-λ-s+λEesν1)}.
Let β(s)=1-exp(-λ-s+λEesν1). Now, we prove that there exists an s′>0 such that β(s′)>0. By the stated condition B∈𝒢+(r), we know that β(s) is a finite differentiable function for s∈[0,r). Furthermore,
(27)β(0)={1-exp(-λ-s+λEesν1)}s=0=0,β′(s)∣s=0={-(-1+λEν1esν1)exp(-λ-s+λEesν1)}s=0=1-ρ>0.Proposition 7.
Suppose thatρ<1 and π is the stationary distribution of {Xn}. If B∈𝒢+(r); then,
(28)∫1+∞‍exp(sx)π(dx)<+∞,∀0<s<s0,
where s0 is the minimum positive root of the equation Eesν1=1+(s/λ).Proof.
By (27), we know that β(0)=0 and β′(0)>0. So, there exists an s′∈(0,r) such that β(s′)>0. The function β(s) is continuous in the interval [s′,r], and it is easy to see that β(r)<0,β(s′)>0. By the zero theorem, we know that there exists at least one root of the equation β(s)=0 (i.e., Eesν1=1+(s/λ)). Let s0 be the minimum positive root; then, β(s)>0, for all 0<s<s0.
Letb=sups∈(0,s0)exp(λEesν1)<∞; then, we have
(29)ΔVs(x)≤-β(s)Vs(x)+bI[0,1]=-ϕ∘Vs(x)+bI[0,1],0<s<s0,x∈R+,
where ϕ(x)=β(s)x (i.e., condition D(ϕ,Vs,C) holds). By Theorem 1, we know that π(ϕ∘Vs)<∞; that is,
(30)∫1+∞‍exp(sx)π(dx)<∞,0<s<s0.Proposition 8.
Suppose thatρ<1 and π is the stationary distribution of {Xn}. If B∈𝒢+(r); then,
(31)limn→∞eε0n∥P(n)(x,A)-π(A)∥=0,
where ε0=α(s-), α(s)=λ+s-λEesν1, and s-∈(0,s0) is the root of the equation 1-λEν1esν1=0.Proof.
From (29),
(32)ΔVs(x)≤-β(s)Vs(x)+bI[0,1],0<s<s0,x∈R,
where β(s)=1-exp(-λ-s+λEesν1), and s0 is the minimum positive root of the equation Eesν1=1+(s/λ). We have
(33)PVs(x)≤exp(-λ-s+λEesν1)Vs(x)+bI[0,1],0<s<s0,x∈R+.
From Lemma 5, we know that {Xn} is a stochastically monotonic Markov chain. By using Theorem  1.1 in [13], we have
(34)limn→∞exp{(λ+s-λEesν1)n}∥P(n)(x,·)-π(·)∥=0,0<s<s0.
Let α(s)=λ+s-λEesν1. From α′′(s)=-λEν12esν1<0, we know that α(x) is a concave function. Together with α(0)=0,α(s0)=0, there exists a unique point s-∈(0,s0), such that α′(s-)=1-λEν1es-ν1=0, and α(s) has a maximum α(s-) at the point s- in the interval (0,s0). So,
(35)limn→∞eε0n∥P(n)(x,A)-π(A)∥=0,
where ε0=α(s-). The proof is completed.


## 4. Subgeometric Rates of Convergence for Cases1–3

Case 1 (The Rate Functionr(n)=exp(sn1/(1+α))).
The rate functionr(n)=exp(sn1/(1+α)), which increases to infinity faster than the polynomial one, and slower than the geometrical one, has been discussed only recently in the literature.Proposition 9.
Suppose thatρ<1 and π is the stationary distribution of {Xn}. If B∈𝒮+(r,α), then one has
(36)∫1+∞‍x-α/(1+α)exp(sx1/(1+α))π(dx)<∞,0<s<s1,
where s1 is the minimal positive solution of β(s)=0  (β(s)=xα/(1+α){1-∑k=0∞(λke-λ/k!)Eexp{s(σk-1+x)1/(1+α)-sx1/(1+α)}}). And
(37)limn→∞n-α/(1+α)exp(ε1n1/(1+α))∥P(n)(x,·)-π(·)∥=0,
where ε1=maxs∈(0,s1)[(α+1)β(s)](1/(1+α)).Proof.
LetVs(x)=exp(sx1/(1+α)),0<s≤r,x∈R+. For all x∈C,
(38)ΔVs(x)=PVs(x)-Vs(x)≤-exp(sx1/(1+α))+∑k=0∞‍λke-λk!Eexp{s(σk+x)1/(1+α)}≤-exp(sx1/(1+α))+exp(sx1/(1+α))·∑k=0∞‍λke-λk!Eexp{s(ν11/(1+α)+ν21/(1+α)+⋯+νk1/(1+α))}=-exp(sx1/(1+α))+exp(sx1/(1+α))·∑k=0∞‍λke-λk![Eexp(sν11/(1+α))]k=-exp(sx1/(1+α))+exp(sx1/(1+α))exp{λEexp(sν11/(1+α))},
where the second inequality holds by using the condition that f(x)=x1/(1+α) is concave. Let α(s)=-exp(sx1/(1+α))+exp(sx1/(1+α))exp{λEexp(sν11/(1+α))}. Since Eexp(sν11/(1+α))<∞, we know that
(39)ΔVs(x)≤α(s)<∞,x∈C.
For all x∈CC,
(40)ΔVs(x)=PVs(x)-Vs(x)=-exp(sx1/(1+α))+∑k=0∞‍λke-λk!Eexp{s(σk-1+x)1/(1+α)}=-exp(sx1/(1+α))·{1-∑k=0∞‍λke-λk!Eexp{s(σk-1+x)1/(1+α)-sx1/(1+α)}∑k=0∞‍}=-exp(sx1/(1+α))x1/(1+α)xα/(1+α)·{1-∑k=0∞‍λke-λk!Eexp{s(σk-1+x)1/(1+α)-sx1/(1+α)}∑k=0∞‍}.
Let
(41)β(s)=xα/(1+α)·{1-∑k=0∞‍λke-λk!Eexp{s(σk-1+x)1/(1+α)-sx1/(1+α)}}.
Now, we prove that there exists an s1>0 such that β(s)>0 for all s∈(0,s1). Similar to the proof of the case x∈C, we know that β(s) is a finite function for s∈[0,r). Furthermore,
(42)β(0)=xα/(1+α)(1-∑k=0∞‍λke-λk!)=0,β′(s)∣s=0=-xα/(1+α)∑k=0∞‍λke-λk!E{(σk-1+x)1/(1+α)-x1/(1+α)}=x[1-∑k=0∞‍λke-λk!E(1+σk-1x)1/(1+α)]≥x[1-∑k=0∞‍λke-λk!(1+(k/μ)-1x)1/(1+α)]≥x[1-(1+ρ-1x)1/(1+α)]>0.
Let s1 be the minimum positive root of the equation β(s)=0; then, we have β(s)>0 for all 0<s<s1.
LetVs(x)=exp(sx1/(1+α)), for all s∈(0,s1), and let b=maxs∈(0,s1){α(s)}<∞; then, we have
(43)ΔVs(x)≤-β(s)exp(sx1/(1+α))xα/(1+α)+bIC,=-ϕ∘Vs(x)+bIC,x∈R+,
where ϕ(x)=β(s)(x/logα(x)), (i.e., Condition D(ϕ,Vs,C) holds). By Theorem 1, we know that there exists a unique invariant distribution π, π(ϕ∘V)<∞, that is
(44)∫1+∞‍x-α/(1+α)exp(sx1/(1+α))π(dx)<∞.
From
(45)Hϕ(x)=∫1x‍dxϕ(x)=∫1x‍logα(x)dxβ(s)x=log1+α(x)(α+1)β(s),
we have Hϕ-1(x)=exp[((α+1)β(s)x)1/(1+α)]. So,
(46)rϕ(n)=ϕ∘Hϕ-1(n)=β(s)exp[((α+1)β(s)n)1/(1+α)]((α+1)β(s)n)α/(1+α)=β(s)1/(1+α)[(α+1)n]-α/(1+α)·exp[((α+1)β(s)n)1/(1+α)]≍n-α/(1+α)exp[((α+1)β(s)n)1/(1+α)].
Let ε1=maxs∈(0,s1){[(α+1)β(s)]1/(1+α)}; then we have,
(47)limn→∞n-α/(1+α)exp(ε1n1/(1+α))∥P(n)(x,·)-π(·)∥=0.
The proof is completed.Case 2 (Polynomial Rate of Convergence).
Consider the following.Proposition 10.
Ifρ<1 and there exists a constant α>1 such that
(48)Eν1α=∫0+∞‍xαB(dx)<+∞,
then
(49)limn→∞nα-1∥P(n)(x,·)-π(·)∥=0,∫1+∞‍xα-1π(dx)<+∞.Proof.
LetV(x)=(x+1)α≥1,x∈R+, and let mα be the αth moment of the poisson distribution with parameter λ. From (a+b)α≤2α(aα+bα), where a>0,b>0, we have, for all x∈C (where C is the petite [0,c]),
(50)ΔV(x)=PV(x)-V(x)≤-(x+1)α+∑k=0∞‍λke-λk!E(ν1+ν2+⋯+νk+x+1)α≤-(x+1)α+∑k=0∞‍λke-λk!2αE((σk)α+(x+1)α)≤-(x+1)α+2α(x+1)α+2α∑k=0∞‍λke-λk!kαEν1α=-(x+1)α+2α(x+1)α+2αmαEν1α.
Let b=-(c+1)α+2α(c+1)α+2αmαEν1α. Since Eν1α<∞, we know that
(51)ΔV(x)≤b<∞,x∈C.
Let Cni denote the binomial coefficient, and let n=⌊α⌋,θ=α-n; then; α=n+θ. For all x∈CC,
(52)ΔV(x)=PV(x)-V(x)=-(x+1)α+∑k=0∞‍λke-λk!E(σk-1+x+1)α=-(x+1)α+∑k=0∞‍λke-λk!E(σk-1+x+1)n+θ=-(x+1)α+∑k=0∞‍λke-λk!·E{[∑i=2n‍(x+1)n+Cn1(x+1)n-1(σk-1)+∑i=2n‍Cni(x+1)n-i(σk-1)i](σk+x)θ}=∑k=0∞‍λke-λk!E{(x+1)n(σk+x)θ-(x+1)α}+∑k=0∞‍λke-λk!E{Cn1(x+1)n-1(σk-1)(σk+x)θ}+∑k=0∞‍λke-λk!·E{∑i=2n‍[Cni(x+1)n-i(σk-1)i](σk+x)θ}.
Since f1(ξ)=ξθ is a concave function, we know that
(53)E(ξ+x)θ≤(Eξ+x)θ.
Thus, the first part of (52) is
(54)∑k=0∞‍λke-λk!E{(x+1)n(σk+x)θ-(x+1)α}≤(x+1)n(ρ+x)θ-(x+1)α<0.
If α is integer (i.e., θ=0), then the second part of (52) is
(55)∑k=0∞‍λke-λk!E{Cn1(x+1)n-1(σk-1)}=Cn1(ρ-1)(x+1)α-1.
If α is not integer (i.e., θ≠0), then the second part of (52) is
(56)∑k=0∞‍λke-λk!E{Cn1(x+1)n-1(σk-1)(σk+x)θ}=Cn1(x+1)n-1∑k=0∞‍λke-λk!E[(σk-1)(x+1)θ]+Cn1(x+1)n-1∑k=0∞‍λke-λk!·E{(σk-1)[(σk+x)θ-(x+1)θ]}≤Cn1(ρ-1)(x+1)α-1+Cn1(x+1)n-1∑k=0∞‍λke-λk!E{1{σk>1}σkθ+1}+E{1{σk<1}((x+1)θ-xθ)}≤Cn1(ρ-1)(x+1)α-1+Cn1(x+1)n-1mθ+1(Eν1θ+1+1)=Cn1(ρ-1)(x+1)α-1+a1(x+1)n-1,
where a1=Cn1mθ+1(Eν1θ+1+1). From (55) and (56), we obtain that the second part of (52) is
(57)∑k=0∞‍λke-λk!E{Cn1(x+1)n-1(σk-1)(σk+x)θ}=Cn1(ρ-1)(x+1)α-1+a1(x+1)n-1,
where a1=0 if α is integer. The third part of (52) is
(58)∑k=0∞‍λke-λk!∑i=2n‍Cni(x+1)n-iE[(σk-1)i(σk+x)θ]≤∑k=0∞‍λke-λk!∑i=2n‍Cni(x+1)n-i·E{(((σk)i+1)(σk)θ+(x+1)θ)}≤∑k=0∞‍λke-λk!∑i=2n‍Cni(x+1)n-i·E{(σk)i+θ+(σk)i(x+1)θ+(σk)θ+(x+1)θ}=∑i=2n‍Cni(x+1)n-i·{mi+θEν1i+θ+miEν1i(x+1)θ+mθEν1θ+(x+1)θ}≤∑i=2n‍Cni(mi+θEν1i+θ+miEν1i+mθEν1θ+1)(x+1)n-i+θ=∑i=2n‍ai(x+1)α-i,
where ai=Cni(mi+θEν1i+θ+miEν1i+mθEν1θ+1)<∞,1≤i≤n (by Eν1α<∞). Combining (52), (54), (57), and (58), we have
(59)ΔV(x)≤Cn1(ρ-1)(x+1)α-1+a1(x+1)n-1+∑i=2n‍ai(x+1)α-i,
where a1=0 if α is integer. Choose c large enough such that, for all x>c (i.e., x∈Cc,C=[0,c]),
(60)a1(x+1)n-1+∑i=2n‍ai(x+1)α-i<-12Cn1(ρ-1)(x+1)α-1.
Thus
(61)ΔV(x)≤12Cn1(ρ-1)(x+1)α-1,∀x∈Cc.
Together with (51), we have
(62)ΔV(x)≤-β(x+1)α-1+bIC,=-ϕ∘V(x+1)+bIC,∀x∈R+,
where β=(1/2)Cn1(1-ρ)>0, ϕ(z)=βz(α-1)/α (i.e., condition D(ϕ,V,C) holds). By Theorem 1, we know that there exists a unique invariant distribution π, π(ϕ∘V)<∞ (i.e., ∫1+∞‍xα-1π(dx)<∞) and
(63)limn→∞∥P(n)(x,A)-π(A)∥ϕ∘V=0,π-a.e..
From
(64)Hϕ(x)=∫1x‍dzϕ(z)=1β∫1x‍z(1-α)/αdz=αβ(x1/α-1),
we have Hϕ-1(x)=((β/α)x+1)α. So,
(65)rϕ(n)=ϕ∘Hϕ-1(n)=β[(βαn+1)α](α-1)/α=β(βαn+1)α-1≍nα-1.
That is,
(66)limn→∞nα-1∥P(n)(x,·)-π(·)∥=0.Case 3 (Logarithmic Rate of Convergence).
Now, we consider the logarithmic case which is slower than that for any polynomial.Proposition 11.
Ifρ<1 and there exists a positive integer α such that
(67)E(ν1logα(ν1+1))=∫0+∞‍xlogα(x+1)B(dx)<+∞,
then
(68)limn→∞logαn∥P(n)(x,·)-π(·)∥=0,(69)∫1+∞‍logαxπ(dx)<∞.Proof.
For allx∈R+, let V(x)=(x+e)logα(x+e); then, we have V(x)>e,x∈R+. Let c>eα, and choose C=[0,c]. For all x∈E,
(70)ΔV(x)=PV(x)-V(x)=∑k=0∞‍λke-λk!E(σk-1+x+e)logα(σk-1+x+e)-(x+e)logα(x+e)=∑k=0∞‍λke-λk!E(σk-1)logα(x+e)+∑k=0∞‍λke-λk!E(σk-1+x+e)·[logα(σk-1+x+e)-logα(x+e)]=(ρ-1)logα(x+e)+∑k=0∞‍λke-λk!·E{((x+e)(1+σk-1x+e))(σk-1+x+e)·[logα((x+e)(1+σk-1x+e))-logα(x+e)]}≤(ρ-1)logα(x+e)+∑k=0∞‍λke-λk!E{∑i=1α‍Cαilogα-i(x+e)logi(1+σk-1x+e)1{σk>1}(σk-1+x+e)·∑i=1α‍Cαilogα-i(x+e)logi(1+σk-1x+e)}≤(ρ-1)logα(x+e)+∑k=0∞‍λke-λk!E{∑i=1α‍1{1<σk≤x+e}2(x+e)·∑i=1α‍Cαilogα-i(x+e)logi(1+σk-1x+e)}+∑k=0∞‍λke-λk!E{1{σk>x+e}2σk∑i=1α‍Cαilogα-i·(x+e)logi(1+σk-1x+e)∑i=1α‍}≤(ρ-1)logα(x+e)+∑k=0∞‍λke-λk!E{1{1≤σk≤x+e}2(σk-1)∑i=1α‍Cαilogα-i(x+e)}+∑k=0∞‍λke-λk!E{∑i=1α‍1{σk>x+e}2σk·∑i=1α‍Cαilogα-i(x+e)logiσk}≤(ρ-1)logα(x+e)+∑k=0∞‍λke-λk!E{1{1≤σk≤x+e}2α+1σklogα-1(x+e)}+∑k=0∞‍λke-λk!E{1{σk>x+e}2α+1σk·logα-1(x+e)logασk}≤(ρ-1)logα(x+e)+2α+1logα-1(x+e)·[ρ+∑k=0∞‍λke-λk!E{1{σk>x+e}σklogασk}]≤(ρ-1)logα(x+e)+2α+1logα-1(x+e)·[ρ+∑k=0∞‍λke-λk!E{1{σk>x+e}σk2α·(logαk+logα(ν1+1))1{σk>x+e}σk2α}∑k=0∞‍]≤(ρ-1)logα(x+e)+2α+1logα-1(x+e)·[ρ+2α(m2Eν1+m1E(ν1logα(ν1+1)))]=(ρ-1)logα(x+e)+a0logα-1(x+e),
where a0=2α+1[ρ+2α(m2Eν1+m1E(ν1logα(ν1+1)))]. Since E(ν1logα(ν1+1))<∞, we get that a0<+∞. Let b=a0logα-1(c+e); then, we have
(71)ΔV(x)≤b<∞,x∈C.
Choose c large enough such that, if x>c (i.e., x∈[0,c]c),
(72)a0logα-1(x+e)<12(1-ρ)logα(x+e).
Thus,
(73)ΔV(x)≤-12(1-ρ)logα(x+e),∀x∈Cc.
Together with (71), we have
(74)ΔV(x)≤-βlogα(x+e)+bIC,=-ϕ∘V(x)+bIC,∀x∈R+,
where β=(1/2)(1-ρ)>0, ϕ(z)=βlogαz (i.e., condition D(ϕ,V,C) holds). A straightforward calculation shows that
(75)rϕ(n)≍logαn.
That is,
(76)limn→∞logαn∥P(n)(x,·)-π(·)∥=0.
By Theorem 1, we know that there exists a unique invariant distribution π, π(ϕ∘V)<∞ (i.e., ∫1+∞‍logαxπ(dx)<∞) and
(77)limn→∞∥P(n)(x,A)-π(A)∥ϕ∘V=0,π-a.e..


### 4.1. Conclusion and Future Research

We studied the M/G/1 queueing system, and the waiting time process of the queueing system is a Markov process. For the workload process of the M/G/1 queueing system, we got anh-skeleton process and discussed its properties of the irreducible and aperiodic and the property of stochastic monotone. Then, we got the parameters ε0 and s0 for geometric rate of convergence and the geometric decay of the stationary tail, respectively. For three specific types of subgeometric cases: Case 1: the rate function r(n)=exp(sn1/(1+α)),α>0,s>0; Case 2: polynomial rate function r(n)=nα,α>0; Case 3: logarithmic rate function r(n)=logαn,α>0, we gave explicit criteria for the rate of convergence and decay of stationary tail. We gave the parameters ε1 and s1 of the rate of convergence and the decay of the stationary tail, respectively, for the subgeometric rate r(n)=exp(sn1/(1+α)),α>0,s>0. These results are important in the study of the stability of M/G/1 queueing system.For future research, much could be done. Our work could be used to the convergence analysis of Markov chain Monte Carlo (MCMC) theory. It could also be used to further discuss queue length, congestion, and so forth. Using similar techniques, these results may be extended to storage models, nonlinear autoregressive model, stochastic unit root models, multidimensional random walk, and other queueing systems.


## 4.1. Conclusion and Future Research

We studied the M/G/1 queueing system, and the waiting time process of the queueing system is a Markov process. For the workload process of the M/G/1 queueing system, we got anh-skeleton process and discussed its properties of the irreducible and aperiodic and the property of stochastic monotone. Then, we got the parameters ε0 and s0 for geometric rate of convergence and the geometric decay of the stationary tail, respectively. For three specific types of subgeometric cases: Case 1: the rate function r(n)=exp(sn1/(1+α)),α>0,s>0; Case 2: polynomial rate function r(n)=nα,α>0; Case 3: logarithmic rate function r(n)=logαn,α>0, we gave explicit criteria for the rate of convergence and decay of stationary tail. We gave the parameters ε1 and s1 of the rate of convergence and the decay of the stationary tail, respectively, for the subgeometric rate r(n)=exp(sn1/(1+α)),α>0,s>0. These results are important in the study of the stability of M/G/1 queueing system.For future research, much could be done. Our work could be used to the convergence analysis of Markov chain Monte Carlo (MCMC) theory. It could also be used to further discuss queue length, congestion, and so forth. Using similar techniques, these results may be extended to storage models, nonlinear autoregressive model, stochastic unit root models, multidimensional random walk, and other queueing systems.



---

*Source: 809460-2013-02-14.xml*