DOI 10.1007/s11134-006-4353-9
Some universal limits for nonhomogeneous birth
and death processes
A. Zeifman· S. Leorato · E. Orsingher · Ya. Satin · G. Shilova
Received: 26 May 2004 / Accepted: 16 August 2005 C
Springer Science+ Business Media, Inc. 2006
Abstract In this paper we consider nonhomogeneous birth and death processes (BDP) with periodic rates. Two impor-tant parameters are studied, which are helpful to describe a nonhomogeneous BDP X = X(t), t ≥ 0: the limiting mean
value (namely, the mean length of the queue at a given time t)
and the double mean (i.e. the mean length of the queue for the whole duration of the BDP). We find conditions of existence of the means and determine bounds for their values, involving also the truncated BDP XN. Finally we present some exam-ples where these bounds are used in order to approximate the double mean.
Keywords Birth and death rates· Kolmogorov differential equations· Logarithmic norm · Exponential stability AMS Subject Classification: Primary: 60J27; Secondary: 60K25, 34A30
1. Introduction
Homogeneous and nonhomogeneous birth and death pro-cesses have a great importance for many fields of ap-A. Zeifman ()
Vologda State Pedagogical University, S. Orlova, 6, Vologda, Russia; Vologda Science Coordination Centre CEMI RAS. Vologda, Russia
e-mail: zai@uni-vologda.ac.ru Ya. Satin· G. Shilova
Vologda State Pedagogical University, S. Orlova, 6, Vologda, Russia
S. Leorato· E. Orsingher
University of Rome ‘La Sapienza’, P.le A. Moro, 5, Rome, Italy
plied probability. Nonhomogeneous versions of the birth and death process have an important role in queueing theory.
It is extremely difficult to obtain general results for arbitrary forms of the birth and death rates and therefore we must content ourselves in obtaining various types of approximations.
In the literature there exist some papers devoted to the problem of approximating BDP (see [2] for diffusions approximations and [6] and [8]). Estimates concerning the distance between truncated and infinite models for homogeneous BDP are presented in [9]. Some queueing applications of periodic BDP are given in [7].
In the case of rates with periodic behavior we study here two parameters, that is the limiting mean value and the “dou-ble mean”.
We can interpret the first parameter as the mean value, at arbitrary time t, of the number of customers queueing up before some device (e.g. bancomat counter).
The second characteristic represents the mean number of customers in the queue for the whole duration of the service. Our approach is based on the method introduced by Gne-denko and Makarov (see [3]) and successively worked out by one of the authors in [10] and [13].
The method based on the application of the logarith-mic norm of operators and the corresponding estimates is dealt with in Daletsky and Krein (see [1]). An im-portant aspect of the analysis is the choice of the suit-able transformation of the reduced matrix of the process rates.
This procedure in the simplest cases is accurately exam-ined in [4] and its description in the general case of nonho-mogeneous BDP and the related applications to the study of queueing systems is presented in [5].
2. Basic results
Let X = X(t), t ≥ 0 be a nonhomogeneous birth and death process (BDP) on the state space E = (0, 1, 2, . . .) and with birth ratesλn= λn(t), t ≥ 0 and death rates μn= μn(t), n∈ E. This means that
P{X(t + h) = j | X(t) = i} = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩
λi(t)· h + o(h, t, i), if j= i + 1 μi(t)· h + o(h, t, i), if j= i − 1 1− (λi(t)+ μi(t))· h + o(h), if j = i
o(h, t, i), if |i − j| > 1
(2.1)
for h > 0 and with limh↓0o(hh,t,i) = 0 uniformly with respect to i ∈ E. This condition plays an essential role in deriving the Kolmogorov differential system in the space l1.
The nonstationarity of X depends on the fact that the rates μi(t) andλi(t) are functions of time and depend on the current size of the queue.
Let
pi j(s, t) = Pr{X(t) = j | X(s) = i} for i, j ∈ E, 0 ≤ s ≤ t
be the transition probability function of the process X = X(t) and
pi(t)= Pr{X(t) = i} for i∈ E, t > 0 be the state probabilities.
We denote by p(t)= (p0(t), p1(t), p2(t), . . .)T, t> 0
the column vector of state probabilities and by A(t)= {ai j(t), t ≥ 0} the matrix related to (2.1) where
ai j(t)= ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ λi−1(t), if j = i − 1 μi+1(t), if j = i + 1 −(λi(t)+ μi(t)), if j = i 0, if otherwise. (2.2)
The probabilistic dynamics of the process is represented by the forward Kolmogorov differential system:
dp
dt = A(t)p, p = p(t), t ≥ 0. (2.3)
The Cauchy problem formed by (2.3) with the initial con-ditions p(s) has the following solution
U(t, s) = {pi j(t, s)}i∞, j=0 for t > s,
where pi, j(t, s) = Pr{X(t) = j|X(s) = i.}.
Throughout the whole paper we use the l1-norm for
vec-tors x that isx1= i∈E|xi| and B = sup j∈E i∈E |bi j| = sup j∈Ebj1 where x= (x0, x1, . . .)T and B= {bi j}∞i, j=0.
Let = {x : x ≥ 0, x1= 1}. We shall restrict
our-selves to birth and death processes whose rates have the following form:
λn(t)= νna(t), μn(t)= ηnb(t), t ≥ 0, n ∈ E, (2.4) with the assumptions that the rates are bounded, i.e. 0< ηn ≤ M, n > 0 and 0 ≤ νn≤ L, n ≥ 0 (2.5) and, obviously,η0= 0.
We clearly assume that the functions a= a(t) and b =
b(t) are non-negative, 1-periodic and bounded, with bounds
a(t)≤ a, b(t) ≤ b. (2.6)
Conditions (2.4)–(2.6) guarantee (see [1]) the bounded-ness and integrability of the operator function A(t) in the space of sequences1, where
A(t)1= 2 sup
i
(λi(t)+ μi(t))≤ 2(La + Mb).
We remark that conditions (2.4)–(2.6) are not used in the proofs of the results below. These conditions are introduced with the purpose of guaranteeing the integrability of the op-erator function A(t) and can be weakened. For example it is possible to replace (2.4) either with the condition that A(t) is itself integrable or with the alternative condition that the rates are linear combinations of a finite number of integrable functions.
In [1] it is shown that the Cauchy problem for linear dif-ferential equations in Banach spaces with bounded and inte-grable operator functions has unique solutions for arbitrary initial conditions. This means that, under our assumptions, the existence and uniqueness of the solution do not pose any problem.
We shall study the following mean values
Ep(0){X(t)} = k∈E
E{X(t) | X(0) = k}pk(0), (2.7)
and the conditional mean value
For our further analysis we need the following quantities. Let 1= d−1= d0≤ d1≤ · · · and define
αk(t)= λk(t)+ μk+1(t)− dk+1 dk λk+1 (t) −dk−1 dk μk (t), k ≥ 0, (2.9) and consequently α(t) = inf k≥0αk(t), α ∗= 1 0 α(t) dt, M0= sup |t−s|≤1 t s α(u) du, M = e M0+α∗, (2.10) W = inf k k−1 i=0di k
We remark that our aim here is the evaluation of estimates for the speed of convergence of the means. Therefore the conditions appearing in the next Theorem are not necessary but sufficient for the existence of the mean of the limiting regime.
The results of next theorems are formulated in terms of the auxiliary sequences di, i≥ 1, which do not possess any probabilistic meaning. A detailed analysis of their properties is given in [4]. We note that they are a sort of counterpart of the Lyapunov functions.
Theorem 1. Let a birth and death process with ratesλk(t)
and μk(t), k≥ 0 be given. Let us assume that there exists
a sequence {dj} such that the number α∗ defined above is strictly positive.
We also assume that the numbers djgrow sufficiently fast so that infk≥1dkk−1 = ω > 0.
Under all these conditions there exists the limit
lim
t→∞|E{X(t)|X(0) = k} − φ(t)| = 0
for all k and for some 1–periodic functionφ(t).
We claim also that, for k= 0, the following upper bound holds
|E{X(t) | X(0) = k} − φ(t)| ≤ aν0M2
Wα∗ e
−α∗t
. (2.11)
Proof. Equation (2.3) in explicit form reads ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ d p0 dt d p1 dt .. . d pn dt .. . ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ −(λ0+ μ0) μ1 0 0 · · · λ0 −(λ1+ μ1) μ2 0 · · · 0 λ1 −(λ2+ μ2)μ3 · · · .. . ... ... . .. ··· ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ × ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ p0 p1 .. . pn .. . ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (2.12) By introducing (see [10–13]), p0(t)= 1 − ∞ i=1pi(t), the second scalar equation
d p1 dt = λ0p0− (λ1+ μ1) p1+ μ2p2, becomes d p1 dt = λ0− λ0 ∞ i=1 pi− (λ1+ μ1) p1+ μ2p2
so that the system (2.12) writes
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ d p1 dt d p2 dt .. . d pn dt .. . ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ −(λ0+ λ1+ μ1) μ2− λ0 −λ0 −λ0· · · · λ1 −(λ2+ μ2) μ3 0 0 · · · 0 λ2 −(λ3+ μ3) μ4 0 · · · .. . ... ... ... ... . .. ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ × ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ p1 p2 .. . pn .. . ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ0 0 .. . 0 .. . ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (2.13)
or otherwise
dz(t)
dt = B(t)z(t) + f(t). (2.14)
This is a linear nonhomogeneous differential system the so-lution of which can be written as
z(t)= V (t, 0)z(0) + t
0
V (t, z)f(z) dz, (2.15)
where V (t, z) is the Cauchy operator of (2.14). The corre-sponding theory is treated in detail in the book by Daletsky and Krein. We furthermore remark that, if B does not depend on t, then the Cauchy operator possesses the explicit simple form V (t, s) = e(t−s)B.
There is the following simple relationship between pairs, z(i )= z(i )(t), t ≥ 0, i = 1, 2, of solutions of (2.14) and pairs
of solutions of (2.3), p(i )= p(i )(t), t ≥ 0, i = 1, 2: p(1)− p(2) 1 = p(1)0 − p(2)0 + i≥1 p(1) i − p (2) i = 1− i≥1 pi(1)− 1− i≥1 p(2)i +z(1)− z(2) 1= i≥1 p(2)i − p(1)i +z(1)− z(2)1≤ i≥1 p(2)i − p(1)i +z(1)− z(2)1= 2z(1)− z(2)1, t ≥ 0. Consequently, z(1)− z(2) 1≤ p(1)− p(2)1≤ 2z(1)− z(2)1, t ≥ 0, (2.16)
which will be used in the study of stability and ergodicity. Consider the matrix
D= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ d0 d0 d0 · · · 0 d1 d1 · · · 0 0 d2 · · · .. . ... . .. ... ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (2.17)
and the space of sequences
1D= {zT = (p1, p2, . . .) : z1D= Dz1< ∞}, (2.18) as in [13]. We have D−1= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ d0−1 −d1−1 0 . .. 0 d1−1 −d2−1 0 . .. . .. 0 . .. d2−1 . .. ... . .. . .. . .. ... . .. . .. ... ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ .
By applying this transformation to the matrix B(t) in (2.14), we arrive at the matrix D B(t)D−1
D B(t)D−1 = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ −(λ0+ μ1) d0· d1−1· μ1 0 . . . d1· d0−1· λ1 −(λ1+ μ2) d1· d2−1· μ2 0 0 d2· d1−1· λ2 . .. . .. . .. .. . 0 . .. . .. . .. . . . . .. . .. . .. ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (2.19)
We recall the definition of the logarithmic norm that was proposed for finite-dimensional spaces by Lozinskij and gen-eralized to Banach spaces by Daletsky and Krein, see for instance [13].
Definition 1. Let B(t), t ≥ 0 be a one-parameter family of
bounded linear operators on a Banach space B and let I denote the identity operator. For each t ≥ 0, the number
γ (B(t)) = lim h→+0
I + hB(t) − 1
h (2.20)
is called the logarithmic norm of the operator B(t).
The logarithmic norm of the matrix B(t)= {bi j(t)}, t ≥ 0 corresponding to a linear operator on the vector space B equipped with1-norm, is
γ (B(t)) = sup j bj j(t)+ i = j |bi j(t)| , t ≥ 0. (2.21)
Let B(t) be an operator function corresponding to Eq. (2.13). Then the logarithmic norm of the operator B(t) is related to
the Cauchy operator V (t, s), 0 ≤ s ≤ t of the system dx dt = B(t)x, t ≥ 0 (2.22) by γ (B(t)) = lim h→+0 V (t + h, t) − 1 h , t ≥ 0. (2.23)
From the latter one can deduce the following bounds on the B-norm of the Cauchy operator V (t, s), 0 ≤ s ≤ t:
e−stγ (−B(τ)) dτ≤ V (t, s) ≤ e
t
sγ (B(τ)) dτ, 0 ≤ s ≤ t.
(2.24) Moreover, for any solution x(t)∈ B, t ≥ 0 of (2.22) we have x(t) ≥ e−t
sγ (−B(τ)) dτx(s). (2.25)
We will also make use of the fact that ifB is a vector space with norm1and all diagonal elements of B are non-negative
then, by (2.21) γ (B(t)) = sup j i bi j(t), t ≥ 0,
and, a fortiori, for any solution x(t), t ≥ 0 of (2.22), s.t. x(s)≥ 0, we have
x(t) ≥ estinfjibi j(τ) dτx(s), 0 ≤ s ≤ t. (2.26)
IfB is endowed with norm 1D, from (2.24) we have that
V (t, s)1D≤ exp t s γ (B(τ))1Ddτ (2.27) and, by (2.26) γ (B(t))1D= γ (DB(t)D−1)= − inf k αk(t)= −α(t). (2.28) In view of (2.26) and having in mind (2.28) we obtain the following inequality p(1)(t)− p(2)(t) 1D ≤ e−t sα(u)dup(1)(s)− p(2)(s) 1D, 0 ≤ s ≤ t, (2.29) for all p(i )(s)∈
1D, i = 1, 2. Now, periodicity of α(t) and
estimate (2.29) imply the exponential stability of Eq. (2.14) and the existence of a 1-periodic solution of this equation
q(t)∈ 1D. Hence, the respective π(t)= (1−
i≥1qi(t)
q(t) )∈ 1D represents the limiting 1-periodic regime of X (t), where X (t) is the BDP considered.
Let1E be the space of sequences
1E = z= (p1, p2, . . .)T:z1E = n|pn|< ∞ . (2.30) We have for any vector z= (p1, p2, . . .)T ∈ l1D the
fol-lowing bound: z1E = n≥1 n|pn| = n≥1 n dn−1dn−1|pn| ≤ ω −1 n≥1 dn−1|pn| = ω−1 n≥1 dn−1 i≥n pi− i≥n+1 pi ≤ ω−1 n≥1 dn−1 i≥n pi + i≥n+1 pi ≤ 2ω−1 n≥0 dn i≥n pi ≤2ω−1z1D. (2.31)
Therefore, as q(t)∈ 1D, there exists the limit 1-periodic
meanφ(t) =nπn(t)< ∞.
Let p(0)= (p0(0), p1(0), . . . , pn(0), . . .)T = e0= (1, 0,
0, . . .)T, and put z(0)= (π1(0)− p1(0), . . .)T. Then z(0)≥
0, and if v(t)= Dz(t), then one has v(0) ≥ 0. We have that v(t) satisfies the homogeneous differential system
dv
dt = DB(t)D
−1v, t ≥ 0. (2.32)
All non-diagonal elements of the matrix D B(t)D−1are non-negative for all t≥ 0 according to (2.19). Then v(t) ≥ 0 for all t≥ 0.
Therefore,i≥kzi(t)≥ 0 for any t ≥ 0 and any k. Now, the following estimate holds:
z1D= ∞ k=0 dk i≥k+1 pi= ∞ i=1 i pi i−1 k=0dk i ≥ inf i≥1 i−1 k=0dk i ∞ h=1 h ph =Wz1E. (2.33)
Then, by (2.29) and (2.33) we obtain |E{X(t)|X(0) = 0} − φ(t)|
≤W−1exp − t 0 α(s) ds z(0)1D =W−1exp − t 0 α(s) ds π(0) − p(0)1D. (2.34) By writing t 0 α(s) ds = t 0 α(s) ds + t t α(s) ds (by periodicity) = t 1 0 α(s) ds + t t α(s) ds = t α∗+ t t α(s) ds = α ∗(t− t + t ) + t t α(s) ds (2.35) we get t 0 α(s) ds − α∗t = t t α(s) ds − α ∗(t− t ) ≤ α∗|t − t | + sup z:|t−z|≤1 t z α(s) ds ≤ M0+ α∗. (2.36)
From the above inequality we have −α∗− M 0+ α∗t ≤ t 0 α(s) ds ≤ α∗t+ α∗+ M 0, and − t 0 α(s) ds ≤ −α∗t+ α∗+ M 0.
We have finally the inequality
exp − t 0 α(s) ds ≤ e−α∗t eα∗+M0 = Me−α∗t. (2.37)
By taking into account that p(0)= (1, 0, 0, . . .)T and the form of the 1D-norm, where only elements of index equal or larger than 1 appear, we have that
π(0) − p(0)1D= π(0)1D≤ lim sup
t→∞ π(t)1D. (2.38) Moreover, by (2.15) we can write
π(t)1D= q(t)1D≤ V (t, 0) · q(0)1D + t 0 V (t, τ)f(τ)dτ 1D ≤ q(0)1DV (t, 0)1D + t 0 Df(τ)1V (t, τ)1Ddτ by (2.27) ≤ π(0)1De t 0γ (B(s))1Dds + d0aν0 t 0 eτtγ (B(u))1Ddudτ by (2.28) ≤ π(0)1De− t 0α(s)ds+ d 0aν0 t 0 e−τtα(u)dudτ ≤ Me−α∗t π(0)1D+Maν0 t 0 e−α∗(t−τ)dτ, (2.39) because of (2.37).
Passing to the limit as t→ ∞ we get
lim sup
t→∞ π(t)1D≤
Maν0
α∗ . (2.40)
Finally using (2.34), (2.37), (2.38) and (2.40), we obtain (2.11).
We now consider the family of truncated BDPs XN = XN(t), t > 0 on the state space EN = {0, 1, 2, . . . , N}, where birth rates areλn(t), n ∈ EN−1and death ratesμn(t),
n∈ EN (and with intensity matrix AN).
The truncated process has the vector of probabilities gov-erned by the forward Kolmogorov differential system
dpN
dt = AN(t)pN. (2.41)
We will identify below the finite vector with entries (a1, . . . , aN) and the infinite vector with the same first N
coordinates and the others equal to zero. The same identifi-cation will be assumed also for the rate matrix AN.
Theorem 2. Assume there exists a sequence{di} such that α∗ > 0. Then for any t ≥ 0
|E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| ≤ 3tMaν0(La+ Mb) WNα∗ , (2.42) where WN = inf k≥0 k i=0dN−1+i N+ k . (2.43)
Proof: Write the system (2.3) in the form dp dt = AN(t)p+ (A(t) − AN(t))p. (2.44) Then p(t)= UN(t, 0)p(0) + t 0 UN(t, τ)(A(τ) −AN(τ))p(τ) dτ. (2.45) Hence |E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| = p(t) − pN(t)1E ≤ t 0 UN(t, τ)(A(τ) −AN(τ))p(τ)1Edτ. (2.46) We have that UN = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ uN00 . . u0NN 0 0 · · · uN 10 . . u1NN 0 0 · · · · · · uN N 0 . . uNN N 0 0 · · · 0 . . 0 1 0 · · · 0 . . 0 0 1 · · · · · · ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , (2.47) and AN = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ −λ0 μ1 0 · · · 0 0 0 · · · λ0 −(λ1+ μ1) μ2 · · · 0 0 0 · · · · · · · · · 0 0 0 · · · λN−1 −μN 0 · · · 0 0 · · · 0 0 . .. .. . ... . .. ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . (2.48) Then ( A− AN)p= (0, . . . , 0, −λNpN + μN+1pN+1, λNpN −(λN+1+ μN+1) pN+1+ μN+2pN+2, . . .)T, (2.49) and UN( A− AN)p = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ uN 0N(−λNpN+ μN+1pN+1) uN 1N(−λNpN+ μN+1pN+1) .. . uN N N(−λNpN+ μN+1pN+1) λNpN− (λN+1+ μN+1) pN+1+ μN+2pN+2 .. . ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (2.50) Inequalities ui jN(t, τ) ≥ 0 for all i, j, t, τ and equalities
iui jN(t, τ) = 1 for all j, t, τ imply the bound
UN( A− AN)p1E = |−λNpN+ μN+1pN+1| n≤N nun NN + k≥N (k+ 1)|λkpk−(λk+1+μk+1) pk+1+μk+2pk+2| ≤ (LapN+ MbpN+1) × N−1 k=0 (k− (k + 1)) k i=0 uN i N+ N N i=0 uN i N + k≥N (k+ 1)(La(pk+ pk+1) +Mb( pk+1+ pk+2)) ≤ La(N pN + (N + 1)(pN+ pN+1)+ (N + 2)(pN+1 +pN+2)+ · · ·) + Mb(N pN+1+ (N + 1)(pN+1 +pN+2)+ (N + 2)(pN+2+ pN+3)+ · · ·) ≤ ≤ (La + Mb) k≥N (2k+ 1)pk≤ 3(La + Mb) k≥N kpk. (2.51)
By (2.39) (with π(t) replaced by z(t)) and assuming that z(0)= 0 we get
z(t)1D≤
Maν0
α∗ . (2.52)
On the other hand,
dN−1( pN + pN+1+ . . .) + dN( pN+1+ pN+2+ . . .) + . . . = pNdN−1+ pN+1(dN−1+ dN)+ pN+2(dN−1
= dN−1 N N pN+ dN−1+ dN N+ 1 (N+ 1)pN+1 + · · · ≥WN k≥N kpk. (2.53) Then k≥N kpk ≤ W−1N k≥N dk−1 i≥k pi ≤ W−1 N z1D ≤ Maν0 WNα∗ . (2.54)
Finally from (2.46), (2.51), (2.52) and (2.54) we obtain
(2.42).
As a consequence of Theorem 1 and Theorem 2 we obtain the following statement.
Corollary 1. Let{di} be a sequence such that α∗> 0. Then for any t ≥ 0 |φ(t) − E{XN(t)|X(0) = 0.}| ≤ M2aν0 Wα∗ e −α∗t +3tMaν0(La+Mb) WNα∗ . (2.55)
Remark 1. Here the first expression of the right-hand side
of (2.55) tends to zero as t → ∞, and the second expres-sion tends to zero as N → ∞ (for any fixed t, provided that
WN → ∞ as N → ∞). Hence, Theorem 2 gives us a tool for calculating the limiting mean, as shown in the examples below.
Let now introduce the following important characteristic of the nonhomogeneous BDP.
Definition 2. The double mean of the BDP X = X(t), t ≥ 0
is defined by E= lim t→∞ 1 t t 0 E{X(u)|X(0) = k} du, (2.56) provided that the limit exists and does not depend on k. Theorem 3. Let {di} be a sequence such that α∗> 0 and assume also that infk≥1dkk−1 = ω > 0. Then the double mean of the BDP X exists and the following inequalities hold:
E− t+1 t E{X(u)|X(0) = 0} du ≤ M2aν0 Wα∗ e −α∗t , (2.57) and E− t+1 t E{XN(u)|XN(0)= 0} du ≤ M2aν0 Wα∗ e −α∗t +3(t+ 1)Maν0(La+Mb) WNα∗ . (2.58)
Proof: The existence of the double mean follows from Theorem 1 which gives the bound
1 t t 0 (E{X(u)|X(0) = 0} − φ(u)) du ≤ M2aν0 tWα∗2. (2.59)
Convergence to zero of (2.59) and 1-periodicity ofφ, im-ply that E= lim t→∞ 1 t t 0 φ(u) du = 1 0 φ(u) du. (2.60)
By applying again Theorem 1, we obtain E− t+1 t E{X(u)|X(0) = 0} du = t+1 t (φ(u) −E{X(u)|X(0) = 0}) du≤ M2aν0 Wα∗ e −α∗t . (2.61) Corollary 1 gives (2.58): E− t+1 t E{XN(u)|XN(0)= 0} du = t+1 t
(φ(u) − E{XN(u)|XN(0)= 0}) du ≤ M 2aν 0 Wα∗ e −α∗t +3(t+ 1)Maν0(La+ Mb) WNα∗ . (2.62)
Remark 2. If the basic functions a(t), b(t) are T -periodic
with T = 1, then all the bounds of the theorems above must be changed according to α∗ = 1 T T 0 α(t) dt, M0= sup |t−s|≤T t s α(u) du, M= eM0+α∗T, (2.63) in place of (2.11).
3. Some examples
We consider the simplest nonhomogeneous queueing sys-tems, with periodic rates.
We show how the limiting mean length of the queue (a pe-riodic function of time t) is obtained. The same construction for the double mean is also presented.
In our examples we choose some values of the period
T corresponding to different situations: the case T = 1 is
related to the standard situation examined above, the case of a short period T = 0.01 corresponds to rapidly vary-ing processes and the case of a long period (T = 100) approximates the situation where the intensity of arrivals of customers and the duration of services significantly differ.
It is interesting to remark that the behaviour of the limiting averages in the models M(t)/M(t)/1 and M(t)/
M(t)/2 is simpler for small and intermediate values of the
period.
In these cases only negligible oscillations of the mean values are perceived during the period.
For large values of T in the arrival and service rates the oscillations in the limiting mean values are instead extremely significant.
The choice of the weights di considerably influences the different estimates of the speed of convergence.
The optimal choice of the sequence{di} in the general case is a difficult problem which will be examined in a separate paper.
The program used for the calculation of the limiting aver-ages and the limiting mean was written in Delphi 6, while the calculations have been carried out with a processor Celeron 2400.
Example 1. (Queue-length process for the M(t)/M(t)/1
queue). We present different examples of periodic
func-tions a(t) and b(t). (i) a(t)= 1 + sin 2πt and b(t) = 4+ 2 cos 2πt (period T = 1). We have νn = ηn= 1, L = M = 1 and a = 2, b = 6. Set dk= 2k, k ≥ 0. Then α(t) = 1 − sin 2πt + cos 2πt, α∗=01α(t) dt = 1,
M0= sup|t−s|≤1 t s α(u) du = 1 + 1 2π and M= eM0+α ∗ = e2+1 2π < 10. Moreover, W = infk k−1 i=0di k = 1 and WN = infk≥0 k i=02N−1+i N+k = 2 N−1 N .
Hence by Theorem 1, Theorem 2 and Corollary 1, we have that |E{X(t)|X(0) = 0} − φ(t)| ≤ 200e−t |E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| ≤ 480N t 2N−1 and |φ(t) − E{XN(t)|XN(0)= 0}| ≤ 200e−t+ 480N t 2N−1 .
Theorem 3 implies that|E −tt+1E{X(u)|X(0) = 0} du| ≤
200e−t, and |E −tt+1E{XN(u)|XN(0)= 0} du| ≤ 200 e−t+480N (t2N−1+1).
For t= 24, N = 50, the above inequality writes |E − 0.38305460| ≤ 10−8.
In figure 1 the mean E{XN(t)|XN(0)= 0} when t ranges from 24 to 25 is drawn.
(ii) a(t)= 1 + sin 200πt, b(t) = 4 + 2 cos 200πt (period
T = 0.01). νn= ηn= 1 = L = M, a = 2 and b = 6. For dk= 2k, k ≥ 0, α(t) = 1 − sin 200πt + 2 cos 200πt; α∗ = 10000.01α(t) dt = 1, M0= sup|t−s|≤0.01 t s α(u) du = 0.01 + 1 200π and M= e M0+T α∗= e0.02+2001π < 1.1. W = infk k−1 i=0di k = 1 and WN = infk≥0 k i=02N−1+i N+k =2 N−1 N . Fig. 1 E{XN(t)|XN(0)= 0}, for t∈ [24, 25].
Fig. 2 E{XN(t)|XN(0)= 0}, for t∈ [20, 20.01]. Hence |E{X(t)|X(0) = 0} − φ(t)| ≤ 3e−t |E{X(t)|X(0) = 0} −E{XN(t)|XN(0)= 0}| ≤ 53N t 2N−1, E− 100 t+0.01 t E{XN(u)|XN(0)= 0} du ≤ 3e−t +53N (t+ 1) 2N−1 .
Then, for t = 20, N = 45, we have that |E− 0.33354528| ≤ 10−8
In figure 2 the mean E{XN(t)|XN(0)= 0}, for t belonging to the interval [20, 20.01] is pictured.
(iii) a(t)= 1 + sin 0.02πt, b(t)= 4 + 2 cos 0.02πt.
With the same choice for {dk} we get the estimates |E{X(t)|X(0) = 0} − φ(t)| ≤ 2e432−t, |E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| ≤ 48·e 216N t 2N−1 , and |E − 0.01 t+100 t E{XN(u)|XN(0)= 0} du| ≤ 2e432−t+48·e
216N (t+1)
2N−1 . For t = 455, N = 365, the above yields |E− 0.60725144| ≤ 10−8.
Figure 3 represents the mean E{XN(t)|XN(0)= 0} for t ∈ [455, 555].
Example 2. (Queue-length process for the M(t)/M(t)/2
queue). We consider now the same periodic functions of Ex-ample 1.
(i) a(t)= 1 + sin 2πt, b(t) = 4 + 2 cos 2πt (1-periodic
functions). In this case we haveνn = η1= 1 (n ≥ 1), ηn =
Fig. 3 E{XN(t)|XN(0)= 0},
Fig. 4 E{XN(t)|XN(0)= 0},
for t∈ [11, 12].
2 (n≥ 2), hence L = 1, M = 2 and a = 2, b = 6. If
dk= 2k, k ≥ 0, then α(t) = 3 − sin 2πt + 2 cos 2πt, α∗= 1 0 α(t) dt = 3, M0= sup|t−s|≤1 t s α(u) du = 3 + 1 2π, M= eM0+α∗= e6+21π < 500, W = infk k−1 i=0di k = 1 and WN = infk≥0 k i=02N−1+i N+k =2 N−1
N . Hence by the results proved above we have that |E{X(t)|X(0) = 0} − φ(t)| ≤ 2 · 105e−3t |E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| ≤ 3· 104N t 4· 2N−2 , |φ(t) − E{XN(t)|XN(0)= 0}| ≤ 2 · 105e−3t+ 3· 104N t 4· 2N−2 , and, by Theorem 3 E− t+1 t E{X(u)|X(0) = 0} du| ≤ 2 · 105e−3t, E− t+1 t E{XN(u)|XN(0)= 0} du ≤ 2 · 105e−3t +3· 104N (t+ 1) 4· 2N−2 ,
Put t = 11, N = 54. The last bound then becomes |E − 0.29456925| ≤ 10−8. In figure 4 the function
E{XN(t)|XN(0)= 0} for t inside [11, 12] is drawn. (ii) a(t)= 1 + sin 200πt, b(t) = 4 + 2 cos 200πt. Then νn = η1= 1 (n ≥ 1), ηn = 2 (n ≥ 2), L = 1, M = 2, a = 2, b = 6. For dk= 2k, k ≥ 1, we obtain the following bounds |E{X(t)|X(0) = 0} − φ(t)| ≤ 6e−3t, |E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| ≤ 72N t 2N−1, E− 100 t+0.01 t E{XN(u)|XN(0)= 0} du| ≤ 6e−3t +72N (t+ 1) 2N−1 .
Set t = 7, N = 44. Then the last inequality becomes
|E− 0.25434930| ≤ 10−8
Figure 5 shows the mean E{XN(t)|XN(0)= 0} in the in-terval [7, 7.01].
(iii) a(t)= 1 + sin 0.02πt, b(t) = 4 + 2 cos 0.02πt (period T = 100). In this case we obtain (for the same sequence dk= 2k) the bounds: |E{X(t)|X(0) = 0} − φ(t)| ≤ e1232−3t, |E{X(t)|X(0) = 0} − E{XN(t)|XN(0)= 0}| ≤ 40N te616 2N−1 , E− 0.01 t+100 t E{XN(u)|XN(0)= 0} du ≤ e1232−3t +40N (t+ 1)e616 2N−1 ,
which, for t = 418 and N = 945 yields
Fig. 5 E{XN(t)|XN(0)= 0},
for t∈ [7, 7.01].
Fig. 6 E{XN(t)|XN(0)= 0},
for t∈ [418, 518].
The function E{XN(t)|XN(0)= 0}, for t ∈ [418, 518], is represented in figure 6.
Acknowledgments The paper was begun in summer 2003 during the
visit of Prof. A.I. Zeifman to the Dipartimento di Statistica, Probabilit`a e Statistiche Applicate of University of Rome “La Sapienza”, to which he wants to express his thanks for the financial support received. We want to thank the Referee and the Associate Editor for very useful remarks.
References
1. Y. Daletsky and M.G. Krein, Stability of solutions of differential equations in Banach spaces, Ann. Math. Soc. Transl. 43 (1974) 386. American Mathematical Society, Providence, R.I.
2. A. Di Crescenzo and A.G. Nobile, Diffusion approximation to a queueing system with time dependent arrival and
ser-vice rates, Queueing Systems Theory Appl. 19 (1995) 41– 62.
3. B.V. Gnedenko and I.P. Makarov, Properties of a problem with losses in the case of periodic intensities, Diff. Equations 7 (1971) 1696–1698 (in Russian).
4. B. Granovsky and A. Zeifman, The N -limit of spectral gap of a class of birth-death Markov chains, Appl. Stoch. Models in Business and Industry 16 (2000) 235–248.
5. B. Granovsky and A. Zeifman, Nonstationary queues: Estimation of the rate of convergence, Queueing Systems 46 (2004) 363– 388.
6. A. Mandelbaum and W. Massey, Strong approximations for time-dependent queues, Math. Oper. Res. 20 (1995) 33–64.
7. B. Margolius, A sample path analysis of the Mt/Mt/c queue,
Queueing Systems Theory Appl. 31(1–2) (1999) 59–93.
8. W.A. Massey and W. Whitt, On analysis of the modified offered-load approximation for the nonstationary Erlang loss model. Ann. Appl. Probab. 4 (1994) 1145–1160.
9. F. Simonot, Sur l’approximation de la distribution stationnaire d’une chaˆine de Markov stochastiquement monotone, Stoch. Proc. Appl. 56(1) (1995) 137–149.
10. A.I. Zeifman, Stability for continuous-time nonhomogeneous Markov chains, Lect. Notes Mathem. 1155 (1985) 401–414. 11. A.I. Zeifman, Truncation error in a birth and death system,
U.S.S.R. Comput. Math. and Math. Phys. 28(6) (1988) 210– 211.
12. A.I. Zeifman, On the estimation of probabilities for birth and death processes, J. Appl. Probab. 32 (1995) 623–634.
13. A.I. Zeifman, Upper and lower bounds on the rate of convergence for nonhomogeneous birth and death processes, Stoch. Proc. Appl. 59 (1995) 157–173.
![Figure 3 represents the mean E{X N (t)|X N (0) = 0} for t ∈ [455, 555].](https://thumb-eu.123doks.com/thumbv2/123dokorg/7579837.112416/10.892.373.814.805.1078/figure-represents-mean-e-x-n-x-n.webp)
![Figure 5 shows the mean E {X N (t)|X N (0) = 0} in the in- in-terval [7 , 7.01].](https://thumb-eu.123doks.com/thumbv2/123dokorg/7579837.112416/11.892.71.822.89.943/figure-shows-mean-e-x-n-x-terval.webp)
