Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

We deal with sharp bounds of the rate of convergence for a wide class of finite continuous-time Markov chains which describe the corresponding Markovian queueing models.

As it is known, the problem of finding sharp bounds of the rate of convergence to the limiting characteristics for such processes is very important for a number of reasons:

  1. (i)

    it is easier to calculate the limit characteristics of a process than to find the exact distribution of state probabilities, (see, for instance [1, 6, 16, 20]);

  2. (ii)

    the best bounds of perturbations require the corresponding best bounds on the rate of convergence, see [9, 19];

  3. (iii)

    sharp bounds on the rate of convergence are required to obtain truncation bounds which are uniform in time, see [17].

A general approach is closely connected with the notion of the logarithmic norm and the corresponding bounds for the Cauchy matrix. It was first studied for birth-death processes (with possible catastrophes), see details and references in [3, 7, 16], and for Markovian queueing models with batch arrivals and group service, see [18]. An essential component of this approach consists of special transformations of the reduced intensity matrix. These transformations were proposed in [12] and applied to general inhomogeneous birth-death models in [13]. Here we apply this approach and the same transformation to two new classes of inhomogeneous continuous-time Markov chains describing combined queueing systems with state-dependent arrival intensity and batch service; and vice versa for queueing system with batch arrivals and state-dependent service, see, for instance, [8, 10]. The case of a finite state space provides the possibility of, first, to simplify the reasoning and, second, to obtain essentially more precise bounds.

Definition. A Markov chain \(X\left( t\right) \) is called weakly ergodic, if

$$\begin{aligned} \lim \limits _{t \rightarrow \infty }\left\| \mathbf {p}^1\left( t\right) -\mathbf {p}^2\left( t\right) \right\| =0 \end{aligned}$$

for any initial conditions \(\mathbf {p}^1\left( 0\right) =\mathbf {p}^1\in \varOmega ,\ \mathbf {p}^2\left( 0\right) =\mathbf {p}^2\in \varOmega .\) In this situation one can consider any \(\mathbf {p}^1\left( t\right) \) as a quasi-stationary distribution of the chain \(X\left( t\right) \).

Definition. A Markov chain \(X\left( t\right) \) has the limiting mean \(\phi (t)\), if

$$\begin{aligned} \left| E(t;k) - \phi (t) \right| \rightarrow 0 \end{aligned}$$

as \(t \rightarrow \infty \) for any k, where E(t; k) is the mathematical expectation (the mean) of the process at the moment t under the initial condition \(X(0)=k\).

2 Basic Approaches to Bounding

There are two approaches to the study of the rate of convergence of continuous-time Markov chains.

The first approach is based on the notion of the logarithmic norm of a linear operator function and the corresponding bounds of the Cauchy operator, see the detailed discussion, for instance, in [3]. Namely, if \(B\left( t\right) \), \(t\ge 0\), is a one-parameter family of bounded linear operators on a Banach space \(\mathcal{B}\), then

$$\begin{aligned} \gamma \left( B\left( t\right) \right) _\mathcal{B} =\lim \limits _{h\rightarrow +0}\frac{ \left\| I+hB\left( t\right) \right\| -1}{h} \end{aligned}$$
(1)

is called the logarithmic norm of the operator \(B\left( t\right) \). If \(\mathcal{B}=l_1\) then the operator \(B\left( t\right) \) is given by the matrix \(B\left( t\right) =\left( b_{ij}\left( t\right) \right) _{i,j=0}^\infty \), \(t\ge 0\), and the logarithmic norm of \(B\left( t\right) \) can be found explicitly:

$$\begin{aligned} \gamma \left( B\left( t\right) \right) =\sup \limits _j\bigg ( b_{jj}\left( t\right) +\sum \limits _{i\ne j}\left| b_{ij}\left( t\right) \right| \bigg ) ,\quad t\ge 0. \end{aligned}$$

Hence the following bound on the rate of convergence holds:

$$\begin{aligned} \Vert {\mathbf x}(t)\Vert \le e^{\int _0^t \gamma \left( B\left( \tau \right) \right) \, d\tau }\Vert {\mathbf x}(0)\Vert , \end{aligned}$$

where \({\mathbf x}(t)\) is the solution of the differential equation

$$\begin{aligned} \frac{d {\mathbf x}}{dt}= B(t){\mathbf x}(t). \end{aligned}$$

Here we apply the second approach, the detailed consideration of which for the case of a finite state space can be found in our recent paper [20].

A matrix is called essentially nonnegative, if all off-diagonal elements of this matrix are nonnegative.

Let

$$\begin{aligned} \frac{d {\mathbf x}}{dt}= H(t){\mathbf x}(t), \end{aligned}$$
(2)

be a differential equation in the space of sequences \(l_1\) with essentially nonnegative for all \(t \ge 0\) countable matrix \(H(t) = \left( h_{ij}(t)\right) \) such that the corresponding operator function on \(l_1\) is bounded for almost all \(t\ge 0\) and locally integrable on \([0,\infty )\).

Therefore \({\mathbf x}(s) \ge 0\) implies \({\mathbf x}(t) \ge 0\) for any \(t \ge s\).

Put

$$\begin{aligned} h^*(t) = \sup _j \sum _i h_{ij}(t), \ \ \ h_*(t) = \inf _j \sum _i h_{ij}(t). \end{aligned}$$
(3)

Let \({\mathbf x}(0) \ge 0\). Then \({\mathbf x}(t) \ge 0\), if \( t \ge 0\) and \(\Vert {\mathbf x}(t)\Vert = \sum _i x_i(t)\). Hence (2) implies the inequality

$$\begin{aligned} \frac{d\Vert {\mathbf x}(t)\Vert }{dt} =\frac{d\sum _i x_i(t)}{dt} \le h^*(t) \sum _j x_j= h^*(t)\Vert {\mathbf x}\Vert . \end{aligned}$$

Then \( \Vert {\mathbf x}(t)\Vert \le e^{\int _0^t h^*(\tau )d\tau }\Vert {\mathbf x}(0)\Vert ,\) if \({\mathbf x}(0)\ge \mathbf{0}.\)

Let now \({\mathbf x}(0)\) be arbitrary vector from \(l_1\). Put \(x_i^+(0)=\max (x_i(0),0)\), \({\mathbf x}^+(0)=\left( x_1^+(0), x_2^+(0), \cdots \right) ^T\) and \({\mathbf x}^-(0)={\mathbf x}^+(0)-{\mathbf x}(0).\) Then \({\mathbf x}^+(0) \ge \mathbf{0}\), \({\mathbf x}^-(0) \ge \mathbf{0}\), \({\mathbf x}(0)={\mathbf x}^+(0)-{\mathbf x}^-(0)\), hence \(\Vert {\mathbf x}(0)\Vert =\Vert {\mathbf x}^+(0)\Vert +\Vert {\mathbf x}^-(0)\Vert \).

Finally we obtain the upper bound

$$\begin{aligned} \Vert {\mathbf x}(t)\Vert = \Vert {\mathbf x}^+(t)-{\mathbf x}^-(t)\Vert \le \Vert {\mathbf x}^+(t)\Vert +\Vert {\mathbf x}^-(t)\Vert \le \nonumber \\ \le e^{\int _0^t h^*(\tau )d\tau } \left( \Vert {\mathbf x}^+(0)\Vert +\Vert {\mathbf x}^-(0)\Vert \right) = e^{\int _0^t h^*(\tau )d\tau } \Vert {\mathbf x}(0)\Vert . \end{aligned}$$
(4)

for any initial condition.

On the other hand, if \({\mathbf x}(0) \ge 0,\) then

$$\begin{aligned} \frac{d\Vert {\mathbf x}(t)\Vert }{dt} = \sum _j \left( \sum _i h_{ij}\right) x_j \ge h_*(t) \sum _j x_j= h_*(t)\Vert {\mathbf x}\Vert , \end{aligned}$$

and we obtain the lower bound

$$\begin{aligned} \Vert {\mathbf x}(t)\Vert \ge e^{\int _0^t h_*(\tau )d\tau } \Vert {\mathbf x}(0)\Vert , \end{aligned}$$
(5)

for any nonnegative initial condition.

On sharpness of bounds

Let us note that if the matrix of system (2) is essentially nonnegative for any t, then one can see that the logarithmic norm of this matrix is equal to our new characteristic, \(\gamma \left( H(t) \right) = h^*(t)\).

Let \(\{d_i\}\), \(i \ge 0\), be a sequence of positive numbers such that \(\inf _i d_i = d >0\). Let \( \textsf {D} = diag\left( d_0, d_1, d_2, \dots \right) \) be the corresponding diagonal matrix and \(l_{1\textsf {D}}\) be a space of vectors \( l_{1\textsf {D}}=\left\{ \mathbf{x} =(x_0,x_1,x_2,\ldots )/\Vert \mathbf{x}\Vert _{1\textsf {D}}=\Vert \textsf {D} \mathbf{x}\Vert _1 <\infty \right\} .\)

Put \(\mathbf{z}(t)=\textsf {D}{} \mathbf{x}(t)\), then (2) implies the equation

$$\begin{aligned} \frac{d {\mathbf z}}{dt}= H_{\textsf {D}}(t){\mathbf z}(t), \end{aligned}$$
(6)

where \(H_{\textsf {D}}(t)= \textsf {D}H(t)\textsf {D}^{-1}\) with entries \(h_{ij \textsf {D}}(t)=\frac{d_i}{d_j}h_{ij}(t)\) is also essentially nonnegative for any \(t \ge 0\).

If there exists a sequence \(\{d_i\}\) such that

$$\begin{aligned} h^*_{\textsf {D}}(t) = \sup _j \sum _i \frac{d_i}{d_j}h_{ij}(t) = \inf _j \sum _i \frac{d_i}{d_j}h_{ij}(t), \end{aligned}$$
(7)

then the equality

$$\begin{aligned} \Vert {\mathbf x}(t)\Vert _{\textsf {D}} = e^{\int _0^t h^*_{\textsf {D}}(\tau )d\tau } \Vert {\mathbf x}(0)\Vert _{\textsf {D}} \end{aligned}$$
(8)

holds for any nonnegative initial condition. Therefore, the bound

$$\begin{aligned} \Vert {\mathbf x}(t)\Vert _{\textsf {D}} \le e^{\int _0^t h^*_{\textsf {D}}(\tau )d\tau } \Vert {\mathbf x}(0)\Vert _{\textsf {D}}, \end{aligned}$$
(9)

which is correct for any initial condition, is sharp.

Note that the construction of such sequences for homogeneous birth-death processes was studied in many papers, see for instance [2, 3, 7].

3 Classes of Markov Chains

Let X(t) be a continuous-time finite Markov chain with intensity matrix Q(t). Denote by \(A(t) = Q^T(t)\) the corresponding transposed intensity matrix. Thus it has the form

$$\begin{aligned} A(t)=\left( \begin{array}{cccccc} a_{00}(t) &{} a_{01}(t) &{} \cdots &{} a_{0r}(t)\\ a_{10}(t) &{} a_{11}(t) &{} \cdots &{} a_{1r}(t)\\ a_{20}(t) &{} a_{21}(t) &{} \cdots &{} a_{2r}(t)\\ \cdots \\ a_{r0}(t) &{} a_{r1}(t) &{} \cdots &{} a_{rr}(t) \end{array} \right) , \end{aligned}$$
(10)

where \(a_{ii}(t)=-\sum _{k \ne i} a_{ki}(t)\).

Now we can apply this approach to the following classes of finite inhomogeneous continuous-time Markov chains.

  1. (I)

    inhomogeneous birth-death processes; in this case all \(a_{ij}(t)=0\) for any \(t \ge 0\) if \(|i-j|>1\); here \(a_{i,i+1}(t)=\mu _{i+1}(t)\) and \(a_{i+1,i}(t)=\lambda _{i}(t)\) are birth and death rates respectively;

  2. (II)

    inhomogeneous chains with ‘batch’ births and single deaths; here all \(a_{ij}(t)=0\) for any \(t \ge 0\) if \(i<j-1\) and moreover, all ‘birth’ rates do not depend on the size of a ‘population’, where \(a_{i+k,i}(t)=a_k(t)\) for \(k\ge 1\) is the rate of ‘birth’ of a group of k particles, and \(a_{i,i+1}(t)=\mu _{i+1}(t)\) is the death rate;

  3. (III)

    vice-versa, inhomogeneous chains with ‘batch’ deaths and single births, here all \(a_{ij}(t)=0\) for any \(t \ge 0\) if \(i>j+1\) and moreover, all ‘death’ rates do not depend on the size of a ‘population’, where \(a_{i,i+k}(t)=b_k(t)\) for \(k\ge 1\) is the rate of ‘death’ of a group of k particles, and \(a_{i+1,i}(t)=\lambda _{i}(t)\) is the birth rate;

  4. (IV)

    inhomogeneous chains with ‘batch’ births and deaths, here all rates do not depend on the size of a ‘population’, where \(a_{i+k,i}(t)=a_k(t)\), and \(a_{i,i+k}(t)=b_k(t)\) for \(k\ge 1\) are the rates of ‘birth’ and ‘death’ of a group of k particles respectively.

Here for these four classes a unified approach based on a special transformation of reduced infinitesimal matrix is described. This unified approach has already been successfully applied to system from the \(\mathrm{I}^{st}\) and \(\mathrm{IV}^{th}\) class. Namely, for the inhomogeneous Markovian queueing model with a finite number of waiting rooms such as \(M|M|S|S+K\) the bounds were firstly obtained in our papers, see for instance [13].

Markovian queueing systems belonging to the \(\mathrm{IV}^{th}\) class were been studied in the recent papers [11, 18].

Queueing systems with group arrivals or services (types \(\mathrm{II}\) and \(\mathrm{III}\) respectively) were also studied (see, for example, the so-called \(M^x|M|c\) models [10] and the recent paper [8]).

Here we demonstrate that the approach is also suitable for the systems from the \(\mathrm{II}^{nd}\) and \(\mathrm{III}^{rd}\) class and thus offers a unified means for the analysis of the ergodicity properties of such Markov chains.

4 Transformation

Let X(t) be a finite continuous-time Markov chain and

$$\begin{aligned} \frac{d {\mathbf p}(t)}{dt}=A(t){\mathbf p}(t) \end{aligned}$$
(11)

be the corresponding forward Kolmogorov system, where \({\mathbf p}(t)\) is the vector of state probabilities. Since \(p_0(t) = 1 - \sum _{i = 1}^r p_i(t)\) due to the normalization condition, one can rewrite the system (11) as

$$\begin{aligned} \frac{d {\mathbf y}(t)}{dt}= B(t){\mathbf y}(t)+{\mathbf f}(t), \end{aligned}$$
(12)

where

$$\begin{aligned} {\mathbf f}(t)=\left( a_{10}(t), a_{20}(t),\dots , a_{r0}(t)\right) ^{T}, \ {\mathbf y}(t)=\left( p_1(t), p_2(t),\dots ,p_{r}(t) \right) ^{T}, \end{aligned}$$

and

$$\begin{aligned} B \!=\! \left( b_{ij}(t)\right) _{i,j=1}^{r} = {\left( \begin{array}{ccccc} a_{11}\left( t\right) \!-\!a_{10}\left( t\right) &{} a_{12}\left( t\right) \!-\!a_{10}\left( t\right) &{} \cdots &{} a_{1r}\left( t\right) \!-\!a_{10}\left( t\right) \\ a_{21}\left( t\right) \!-\!a_{20}\left( t\right) &{} a_{22}\left( t\right) \!-\!a_{20}\left( t\right) &{} \cdots &{} a_{2r}\left( t\right) \!-\!a_{20}\left( t\right) \\ \cdots &{} \cdots &{} \cdots &{} \cdots \\ a_{r1}\left( t\right) \!-\!a_{r0}\left( t\right) &{} a_{r2}\left( t\right) \!-\!a_{r0}\left( t\right) &{} \cdots &{} a_{rr}\left( t\right) \!-\!a_{r0}\left( t\right) \end{array} \right) .} \end{aligned}$$

Then the bound of the norm of the solution for the corresponding homogeneous system

$$\begin{aligned} \frac{d {\mathbf y}(t)}{dt}= B(t){\mathbf y}(t) \end{aligned}$$
(13)

yields the rate of convergence for X(t).

Denote by \(T_r\) the upper triangular matrix of the form

$$\begin{aligned} T_r={\tiny \left( \begin{array}{ccccccc} 1 &{} 1 &{} 1 &{} \cdots &{} 1 \\ 0 &{} 1 &{} 1 &{} \cdots &{} 1 \\ 0 &{} 0 &{} 1 &{} \cdots &{} 1 \\ \vdots &{} \vdots &{} \vdots &{} \ddots \\ 0 &{} 0 &{} 0 &{} \cdots &{} 1 \end{array} \right) . } \end{aligned}$$
(14)

Then the corresponding matrix \(H(t)=T_r B(t)T^{-1}_r = \left( h_{ij}(t)\right) _{i,j=1}^{r}\) is essentially nonnegative for all of our classes, hence we can apply the second approach and obtain the sharp bounds on the rate of convergence!

Namely, for the first class we have

$$\begin{aligned} H(t) = { \left( \begin{array}{ccccc} -\left( \lambda _0(t)+\mu _1(t)\right) &{} \mu _1(t) &{} 0 &{} \cdots &{} 0 \\ \lambda _1(t) &{} -\left( \lambda _1(t)+\mu _2(t)\right) &{} \mu _2(t) &{} \cdots &{} 0 \\ \ddots &{} \ddots &{} \ddots &{} \ddots &{} \ddots \\ 0 &{} \cdots &{} \cdots &{} \lambda _{r-1}(t) &{} -\left( \lambda _{r-1}(t)+\mu _r(t)\right) \end{array} \right) .} \end{aligned}$$

For the second class we obtain

$$\begin{aligned} H(t) = {\left( \begin{array}{ccccc} a_{11}(t)-a_r(t) &{} \mu _1(t) &{} 0 &{} \cdots &{} 0 \\ a_1(t)-a_r(t) &{} a_{22}(t)-a_{r-1}(t) &{} \mu _2(t) &{} \cdots &{} 0 \\ \ddots &{} \ddots &{} \ddots &{} \ddots &{} \ddots \\ a_{r-1}(t)-a_r(t) &{} \cdots &{} \cdots &{} a_1(t)-a_2(t) &{} a_{rr}(t)-a_1(t) \end{array} \right) }, \end{aligned}$$

hence, the off-diagonal elements \(h_{ij}(t) \ge 0\), if \(a_{k+1}(t) \le a_k(t)\) for any k, t.

For the third class we have

$$\begin{aligned} H(t) = {\left( \begin{array}{ccccc} -\left( \lambda _0(t)+b_1(t)\right) &{} b_1(t) - b_2(t) &{} b_2(t) - b_3(t) &{} \cdots &{} b_{r-1}(t) - b_r(t) \\ \lambda _1(t) &{} -\big (\lambda _1(t)+\sum \limits _{i\le 2}b_i(t)\big ) &{} b_1(t) - b_3(t) &{} \cdots &{} b_{r-2}(t) - b_r(t) \\ \ddots &{} \ddots &{} \ddots &{} \ddots &{} \ddots \\ 0 &{} \cdots &{} \cdots &{} \lambda _{r-1}(t) &{} -\big (\lambda _{r-1}(t)+\sum \limits _{i\le r}b_i(t)\big ) \end{array} \right) }, \end{aligned}$$

hence, the off-diagonal elements \(h_{ij}(t) \ge 0\), if \(b_{k+1}(t) \le b_k(t)\) for any k, t.

Finally, for the fourth class we have

$$\begin{aligned} H(t) = {\left( \begin{array}{ccccc} a_{11}(t)-a_r(t) &{} b_1(t) - b_2(t) &{} b_2(t) - b_3(t) &{} \cdots &{} b_{r-1}(t) - b_r(t)\\ a_1(t)-a_r(t) &{} a_{22}(t)-a_{r-1}(t) &{} b_1(t) - b_3(t) &{} \cdots &{} b_{r-2}(t) - b_r(t) \\ \\ \ddots &{} \ddots &{} \ddots &{} \ddots &{} \ddots \\ a_{r-1}(t)-a_r(t) &{} \cdots &{} \cdots &{} a_1(t)-a_2(t) &{} a_{rr}(t)-a_1(t) \end{array} \right) }, \end{aligned}$$

hence, the off-diagonal elements \(h_{ij}(t) \ge 0\), if \(a_{k+1}(t) \le a_k(t)\) and \(b_{k+1}(t) \le b_k(t)\) for any k, t.

5 Example

As a queueing example we can consider the rate of convergence for the Erlang loss system \(M_t|M_t|S|S\) and its generalizations.

The queue-length process X(t) for \(M_t|M_t|S|S\) is a birth-death process with \(r=S\), arrival and service intensities \(\lambda _k(t)=\lambda (t)\) and \(\mu _k(t)=k\mu (t)\) respectively. The rate of convergence for this process in the homogeneous situation and its asymptotic as \(S \rightarrow \infty \) were studied in many papers, see for instance [3, 5].

The approach considered in this paper was applied to a general inhomogeneous situation in [4, 12, 14].

Namely, the queue-length process for the ordinary \(M_t|M_t|S|S\) queue is weakly ergodic if and only if

$$\begin{aligned} \int _0^\infty \left( \lambda (t)+\mu (t)\right) \, dt = \infty . \end{aligned}$$
(15)

Bounds for different intensity functions were presented in [14]. Particularly, bound (4) holds for \(h^*(t)=\mu (t)\) and for \(h^*(t)=S^{-1}\lambda (t)\) for the transformations \(d_k=1\) and \(d_k=1/k\) respectively.

The simplest analogue of the \(M_t|M_t|S|S\) queue for a queueing system with group services was introduced and studied in [15]. For this model we suppose that the intensity of arrival of a customer to the queue is also \(\lambda (t)\), and the intensity of departure (servicing) of a group of k customers is \(b_k(t) = \mu (t)/k\), \(1 \le k \le S\). The queue-length process X(t) for such model belongs both to the III-d and IY-th classes. We obtained the same criterion (15) of the weak ergodicity of X(t). Moreover, bound (4) holds for \(h^*(t)=\mu (t)\) and for \(h^*(t)=S^{-1}\lambda (t)\) with the corresponding transformations \(d_k=1\) and \(d_k=1/k\).

The following model is an essential generalization of the Erlang loss system. Let the length of the queue is \(X(t) \le S\), and assume that a group of \(k \le M \le S\) customers can arrive to the queue with intensity \(a_{k}=\frac{\lambda (t)}{k}\), and a group of \(k \le N \le S\) customers can leave the queue after being serviced with intensity \(\mu _{k}=\frac{\mu (t)}{k}\), where M and N are fixed natural numbers. The asymptotics as \(S \rightarrow \infty \) of the rate of convergence for this model in the homogeneous situation was studied in [21]. A general inhomogeneous case was considered in [20]. Namely, if \(M=N=S\), then putting \(d_k=1\) we obtain the sharp bound on the rate of convergence (9) with \(h^*(t)=\lambda (t) + \mu (t)\).