1. Introduction
In this paper we examine necessary and sufficient conditions for recurrence and positive recurrence of a class of multi-dimensional Markov processes, namely level-dependent quasi-birth-and-death processes. These conditions are established by way of Lyapunov (potential) functions and variants of Foster’s criterion [Reference Foster17]. Additionally, we demonstrate a correspondence between these conditions and similar results for related Markov processes.
The quasi-birth-and-death (QBD) process is a bivariate, continuous-time Markov process
$\{(X_t,Y_t)\colon t\ge 0\}$
with countable state space
$S=\{(i,j)\colon i\ge 0,\, j=1,\ldots,K_i\}$
, where i is called the level of the process, j is the phase, and
$K_i$
is the number of phases in level i. Generally speaking,
$K_i$
can be either a finite, positive integer or infinity for each i. The process is restricted in level jumps only to its nearest neighbors but is unrestricted in the phase dimension. That is, from state
$(i,j)\in S$
the process may transition to the states (i,k), (i−1,k), or (i+1,k), but not to states of the form
$(i\pm n,k)$
where
$n\ge 2$
. It extends the standard birth-and-death process, whose state space consists only of the level i. If the transition rates of a QBD process are independent of i, it is termed a homogeneous or level-independent QBD process; if the rates change with i, it is termed a non-homogeneous or level-dependent QBD (LDQBD) process. The broad class of LDQBD processes is widely applicable to stochastic models arising in queueing theory, computer and communications systems, reliability theory, inventory theory, and many other areas. The level-independent version has been studied extensively in the applied probability literature and is given a comprehensive treatment by Latouche and Ramaswami [Reference Latouche and Ramaswami24]; the level-dependent version has received comparatively less attention.
For the class of LDQBD models examined here, it is assumed that
$K_i=K$
for all i, where K is a finite, positive integer. Since important attributes (e.g. recurrence and transience) of an irreducible continuous-time Markov chain can be ascertained via its embedded discrete-time Markov chain (DTMC) at jump epochs, we analyze this chain and denote it by
$\Phi\,{:\!=}\,\{(X_n,Y_n)\colon n\in {\mathbb{Z}_{_+}}\}$
. This process has state space
$S=\{(i,j)\colon i\ge 0,\, j=1,\ldots,K\}$
, and its one-step transition probability matrix (P) possesses the classical block tridiagonal form of a QBD process:
\[
P=\begin{pmatrix}
{A_{1}^{{(0)}}} & {A_{0}^{{(0)}}} & 0 & 0 & 0 & \cdots \\
{A_{2}^{{(1)}}} & {A_{1}^{{(1)}}} & {A_{0}^{{(1)}}} & 0 & 0 & \cdots \\
0 & {A_{2}^{{(2)}}} & {A_{1}^{{(2)}}} & {A_{0}^{{(2)}}} & 0 & \cdots \\
0 & 0 & {A_{2}^{{(3)}}} & {A_{1}^{{(3)}}} & {A_{0}^{{(3)}}}
& \cdots \\
0 & 0 & 0 & {A_{2}^{{(4)}}} & {A_{1}^{{(4)}}}
& \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\
\end{pmatrix}.
\]
The structure of P indicates that the process is skip-free in the level in both directions. For general LDQBD processes, the blocks along the main diagonal of P (
${A_{1}^{{(i)}}}$
for
$i\ge 0$
) are square matrices, while those on the secondary diagonals (
${A_{0}^{{(i)}}}$
and
${A_{2}^{{(i)}}}$
for
$i\ge 0$
) can be rectangular. The model we examine here assumes that all rows of P contain only square matrices of order K. Therefore, for each
$i\ge 0$
and
$m=0,1,2$
,
$A_m^{(i)}$
is a non-negative square matrix of order K, and the row sums of
$A^{(i)}\,{:\!=}\, A_2^{(i)}+A_1^{(i)}+A_0^{(i)}$
for
$i\ge 1$
are equal to 1, as are those of
$A_1^{(0)}+A_0^{(0)}$
. When it exists, denote the limiting distribution of
$\Phi$
by a positive row vector
$\textbf{\textit{x}}$
that uniquely solves the linear system
$\textbf{\textit{x}} P = \textbf{\textit{x}}$
and
$\textbf{\textit{x}} \textbf{\textit{e}}=1$
, where
$\textbf{\textit{e}}$
is a column vector of ones. The vector
$\textbf{\textit{x}}$
is partitioned by levels into subvectors so that
$\textbf{\textit{x}}=(\textbf{\textit{x}}_0,\textbf{\textit{x}}_1,\textbf{\textit{x}}_2,\ldots)$
, and
$\textbf{\textit{x}}_i$
contains the limiting probabilities for states in level i, namely those in the set
$L_i\,{:\!=}\,\{(i,1),\,(i,2),\ldots,(i,K)\}$
. If
$\Phi$
is irreducible, aperiodic, and positive recurrent, then there exist matrices
$\{R_i\colon i\ge 1\}$
such that
$\textbf{\textit{x}}_i=\textbf{\textit{x}}_{i-1}R_i$
, where
$\{R_i\colon i\ge 1\}$
is the minimal non-negative solution of the set of equations
\begin{equation}
R_i=A_0^{(i-1)}+R_i\,A_1^{(i)}+R_i\,R_{i+1}\,A_2^{(i+1)},\quad i\ge 1
\label{eqn1}
\end{equation}
(see Theorem 12.1.1 of [Reference Latouche and Ramaswami24]). Solving the system of equations (1) is typically relegated to numerical techniques, such as those described in [Reference Bright and Taylor8]. The LDQBD process is positive recurrent if and only if there exists a positive solution to the system of equations [Reference Latouche and Ramaswami24, Theorem 12.1.4]
\[
\textbf{\textit{x}}_0=\textbf{\textit{x}}_0 (A_1^{(0)}+A_0^{(0)}G_1)
\]
subject to the normalization condition
\[
\textbf{\textit{x}}_0\,\bigg(\sum_{n=0}^{\infty}\prod_{i=1}^nR_i\bigg)\textbf{\textit{e}}=1,
\]
where
$G_1$
contains the probabilities of reaching level 0 in finite time starting from level 1, and the empty product (when
$n=0$
) results in the identity matrix. Although the matrices
$G_1$
and
$\{R_i\colon i\ge 1\}$
can be obtained to any desired accuracy using, for example, the algorithms of Bright and Taylor [Reference Bright and Taylor8], our primary aim here is to determine analytical necessary and sufficient conditions for a special class of LDQBD processes.
Level-independent QBD processes arise frequently in the context of queueing models with non-standard arrival and/or service mechanisms (e.g. randomly varying arrival and/or service rates). One such example is the M/M/1 queue in a two-state environment [Reference Eisen and Tainiter14, Reference Yechiali and Naor50] in which the level i corresponds to the number of customers in the system, and the phase j is the state of an exogenous environment process that modulates the arrival and/or service rates. These early models were later extended by Neuts [Reference Neuts34, Reference Neuts35, Reference Neuts36] and Purdue [Reference Purdue40] to consider environment transitions not restricted to service completion epochs. Neuts [Reference Neuts38] formally categorized Markov-modulated queueing systems as homogeneous QBD processes and provided an average drift condition for this class of stochastic processes. Latouche and Taylor [Reference Latouche and Taylor25] provided a general proof for drift conditions of homogeneous QBD processes, which are also applicable to general matrix-analytic models. The emergence of retrial queueing models spawned variants of the homogeneous QBD process, including the LDQBD process in which the block tridiagonal structure varies over an infinite number of levels. Some representative examples of such models include [Reference Alfa1], [Reference Anisimov and Artalejo2], [Reference Artalejo and Chakravarthy3], [Reference Avram and Gwmez-Corral5], [Reference Breuer, Dudin and Klimenok7], [Reference Kumar, Rukmani and Thangaraj23], [Reference Li, Ying and Zhao26], [Reference Mushko, Jacob, Ramakrishnan, Krishnanmoorthy and Dudin33], and [Reference Shin46]. Bright and Taylor [Reference Bright and Taylor8] developed an efficient row-truncation algorithm to approximate the limiting distribution of an LDQBD process when it exists; however, the method does not readily yield information about the recurrence characteristics of the LDQBD process. Some models possess special properties to facilitate analysis of stability criterion, as in [Reference Artalejo, Krishnamoorthy and Lopez-Herrero4], whereas improvements in numerical algorithms such as ETAQA [Reference Ciardo and Smirni9] for computing the stationary distribution of LDQBD processes have made the numerical approach more tenable for queueing applications (see [Reference Baumann, Dayar, Orhan and Sandmann6], [Reference Dayar, Sandmann, Spieler and Wolf10], and [Reference Montoro Cazorla and Perez-Ocon32]).
For one-dimensional Markov chains with infinitely denumerable state spaces, it is well known that Lyapunov functions, along with Foster’s criterion [Reference Foster17], can be used to establish sufficient conditions for the ergodicity of irreducible chains. As a special case of Foster’s criterion, Pakes’ lemma [Reference Pakes39, Theorem 2] is perhaps most useful in that it generalizes to conditions on the subsequential upper bound of drift terms, and it uses the identity function as the Lyapunov (potential) function. Other extensions considering broader classes of Markov processes, including continuous-time Markov chains (CTMCs), appear in [Reference Marlin29], [Reference Mertens, Samuel-Cahn and Zamir30], [Reference Rosberg43, [Reference Tweedie48], and [Reference Tweedie49]. Non-ergodicity was first studied first by Kaplan [Reference Kaplan19] and subsequently by Sennott, Humblet, and Tweedie [Reference Sennott44, Reference Sennott, Humblet and Tweedie45]. However, the analysis of LDQBD processes falls more appropriately within the realm of multi-dimensional Markov processes, which have been studied extensively over the past several decades. Tweedie [Reference Tweedie49] approached the problem from the vantage point of general state spaces, followed by Szpankowsky [Reference Szpankowski, Baccelli and Fayolle47], Rosberg [Reference Rosberg42], and Sennott [Reference Sennott44]. To the best of our knowledge, the first appearance of a necessary and sufficient Foster–Lyapunov recurrence criterion appears in Mertens, Samuel-Cahn, and Zamir [Reference Mertens, Samuel-Cahn and Zamir30]. A corresponding necessary and sufficient criterion for the positive recurrence of Markov chains over countable state spaces is proved in [Reference Malyshev27]. This result, along with those of Mertens, Samuel-Cahn, and Zamir [Reference Mertens, Samuel-Cahn and Zamir30], are incorporated in the monograph by Fayolle, Malyshev, and Menshikov [Reference Fayolle, Malyshev and Menshikov16] on the constructive theory of countable Markov chains.
Due to the difficulties associated with analyzing general, multi-dimensional Markov processes with non-homogeneous transition matrices, attention has shifted to classes of structured chains that become homogeneous at a finite level of the state space. One important example is the class of LDQBD processes for which there exists a level L above which the process behaves as a homogeneous QBD process. Such models are termed LDQBDs with a large number of boundary states (see [Reference Bright and Taylor8] and [Reference Neuts38]) and are relevant to our work here in that their recurrence properties can be determined by examining the behavior of the process beyond level L. Bright and Taylor [Reference Bright and Taylor8] showed how to construct a stochastically dominating LDQBD process whose recurrence is sufficient to guarantee the recurrence of the process it dominates. Klimenok and Dudin [Reference Klimenok and Dudin21] defined and analyzed the so-called asymptotically quasi-Toeplitz Markov chain (AQTMC). The AQTMC is the non-homogeneous, asymptotically row-convergent form of the multi-dimensional QTMC introduced in [Reference Dudin and Klimenok12], which was motivated by their previous work on a retrial queue whose input is a batch Markovian arrival process (BMAP) [Reference Dudin and Klimenok11, Reference Dudin and Klimenok13, Reference Kim, Klimenok, Mushko and Dudin20]. The QTMC is more widely known as an M/G/1 -type Markov chain [Reference Neuts37], as its structure mirrors that of the system size process of an M/G/1 queue embedded at service completion epochs.
It is well known that the LDQBD process is a subclass of non-homogeneous M/G/1 -type Markov chains. Furthermore, if it is assumed that the blocks of the transition probability matrix converge (as
$i\to \infty$
), then the LDQBD process can be viewed as a discrete-time AQTMC. While the AQTMC analyzed in [Reference Klimenok and Dudin21] is more general, they provide only sufficient conditions for ergodicity and non-ergodicity of these types of chains. Koukoutsidis, Altman, and Kelif [Reference Koukoutsidis, Altman and Kelif22] devised a non-homogeneous QBD model for admission control of a WCDMA system. They conjectured an ergodicity condition for the case in which the blocks of the infinitesimal generator matrix converge asymptotically to those of a homogeneous QBD process. For chains that satisfy such convergence properties, the LDQBD process is ergodic if the QBD process to which it converges is ergodic; conversely, if the LDQBD process is non-ergodic, then so too is the QBD process. The sketch of their proof uses stochastic dominance concepts.
The primary aim of the present paper is to provide necessary and sufficient conditions for the recurrence and positive recurrence of a class of discrete-time LDQBD processes whose block matrices converge as
$i\to \infty$
. More specifically, we consider a continuous-time LDQBD process whose embedded jump chain satisfies the convergence criteria
\[
\lim_{i\to\infty}A_k^{(i)}=A_k^*,\;k=0,1,2\quad\mbox{ and }\quad \lim_{i\to\infty}A^{(i)}=A^*,
\]
where the above limits hold element-wise. This class of processes encompasses the class of LDQBD processes with a large number of boundary states. It can also be viewed as a special case of the asymptotically quasi-Toeplitz Markov chains; however, our approach and results differ in two important ways. First, we employ a Foster–Lyapunov drift approach to derive positive recurrence (and hence, ergodicity) conditions for this special type of LDQBD without the use of transforms. Second, we show that this condition is not only sufficient but also necessary, and demonstrate an analogy between our results and the average drift conditions for level-independent QBD processes.
The remainder of the paper is organized as follows. Section 2 first reviews LDQBD processes and some preliminaries related to drift functions and Foster’s criterion for one-dimensional Markov chains. In Section 3 we derive the generalized drift function for a specific form of Lyapunov function and employ a modified version of Foster’s criterion to provide sufficient conditions for recurrence, and necessary and sufficient conditions for positive recurrence, of the embedded DTMC
$\Phi$
. Section 4 establishes the existence of a limiting average drift and characterizes necessary and sufficient conditions for recurrence, null recurrence, positive recurrence, and transience using this drift term. Additionally, we highlight analogies between the homogeneous QBD process and the LDQBD process. A few concluding remarks are provided in Section 5.
2. Preliminaries
Although the LDQBD process is generally a continuous-time discrete-state stochastic process, we analyze its discrete-time counterpart (as the continuous-time version can be analyzed via embedding at transition epochs). Throughout the manuscript, we shall adopt the following notation and conventions. Let
${\mathbb{R}}$
be the set of real numbers,
${\mathbb{R}_{_+}}=[0,\infty)$
the set of non-negative reals,
${\mathbb{N}}=\{1,2,\ldots\}$
the set of natural numbers and
${\mathbb{Z}_{_+}}=\{0,1,\ldots\}$
the set of non-negative integers. The vector
$\textbf{\textit{e}}=(1,1,\ldots,1)'$
denotes a column vector of ones, and 0 denotes the zero column vector (or zero matrix), as needed. Finally, for any two column vectors
$\textbf{\textit{x}},\textbf{\textit{y}}\in {\mathbb{R}}^n$
, we write
$\textbf{\textit{x}}\le \textbf{\textit{y}}$
to indicate that the inequality holds component-wise.
Let
$\Phi\,{:\!=}\,\{(X_n,Y_n)\colon n\ge 0\}$
be a time-homogeneous, irreducible and aperiodic discrete-time Markov chain (DTMC) on the countable state space
\[
S\,{:\!=}\,{\{{(i,j)} \colon {i\in{\mathbb{Z}_{_+}},\;j\in {{\cal P}}}\}},
\]
where
${{\cal P}}\,{:\!=}\,\{1,\ldots,K\}$
for some
$K\in {\mathbb{N}}$
. The components i and j of the state are termed the level and phase of the process, respectively. The DTMC
$\Phi$
is a discrete-time quasi-birth-and-death (QBD) process because its one-step transition probability matrix (P) exhibits the block tridiagonal form
\begin{equation}
P=\begin{pmatrix}
{A_{1}^{{(0)}}} & {A_{0}^{{(0)}}} & 0 & 0 & 0 & \cdots \\[1.5pt]
{A_{2}^{{(1)}}} & {A_{1}^{{(1)}}} & {A_{0}^{{(1)}}} & 0 & 0 & \cdots \\[1.5pt]
0 & {A_{2}^{{(2)}}} & {A_{1}^{{(2)}}} & {A_{0}^{{(2)}}} & 0 & \cdots \\[1.5pt]
0 & 0 & {A_{2}^{{(3)}}} & {A_{1}^{{(3)}}} & {A_{0}^{{(3)}}}
& \cdots \\[1.5pt]
0 & 0 & 0 & {A_{2}^{{(4)}}} & {A_{1}^{{(4)}}}
& \cdots \\[1.5pt]
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\
\end{pmatrix} {.}
\label{eqn2}
\end{equation}
The time-homogeneity of
$\Phi$
implies that P is independent of time n. For each
$i\in {\mathbb{Z}_{_+}}$
, the entries
${A_{0}^{{(i)}}}$
,
${A_{1}^{{(i)}}}$
, and
${A_{2}^{{(i)}}}$
are non-negative
$K\times K$
matrices comprising transition probabilities between phase states and levels. As P is a one-step transition probability matrix, we note that
\[
{A_{}^{{(i)}}}\,{:\!=}\,
\begin{cases}
{A_{1}^{{(i)}}}+{A_{0}^{{(i)}}} & i=0 \\
{A_{2}^{{(i)}}}+{A_{1}^{{(i)}}}+{A_{0}^{{(i)}}} & i\ge 1
\end{cases}
\]
is a stochastic matrix. The structure of P shows that the process is skip-free in the level in both directions. More precisely, for
$i\in {\mathbb{N}}$
and any
$j,j'\in {{\cal P}}$
,
\begin{align*}
{[A_{0}^{{({i})}}]_{jj'}} &= {\mathbb{P}({X_{n+1}=i+1,Y_{n+1}=j'}|{X_n=i,Y_n=j})}, \\
{[A_{1}^{{({i})}}]_{jj'}}&= {\mathbb{P}({X_{n+1}=i, Y_{n+1}=j'}|{X_n=i,Y_n=j})}, \\
{[A_{2}^{{({i})}}]_{jj'}} &= {\mathbb{P}({X_{n+1}=i-1,Y_{n+1}=j'}|{X_n=i,Y_n=j})}.
\end{align*}
If
${A_{k}^{{(i)}}}={A_{k}^{{(i')}}}$
for every
$i,i'\in{\mathbb{Z}_{_+}}$
(except possibly for the boundary level
$i=0$
) and for each
$k\in\{0,1,2\}$
, then
$\Phi$
is called a level-independent QBD (or simply QBD) process. However, if
${A_{k}^{{(i)}}}\ne{A_{k}^{{(i')}}}$
for two or more non-zero levels
$i\ne i'$
, then
$\Phi$
is called a level-dependent QBD (LDQBD) process.
Our aim is to establish necessary and sufficient conditions for the positive recurrence (and thus ergodicity) of the LDQBD
$\Phi$
by analyzing the drift of the process. To that end, we first review drift functions, as well as an extension of Foster’s criterion [Reference Foster17] for a one-dimensional irreducible, aperiodic DTMC
$\xi\,{:\!=}\,{\{{X_n}\colon {n\geq 0}\}}$
on a countable state space S. We begin with the following definition.
Definition 1. Let
$\nu\colon S\to (0,\infty)$
be a positive function, and for each
$x\in S$
let
\[
{\delta_{_{\nu}}}(x)\,{:\!=}\,{\mathbb{E}({\nu{({X_{n+1}})}-\nu{({X_n})}}|{X_n=x})}.
\]
The function
$\nu$
is called a Lyapunov (or potential) function, and
${\delta_{_{\nu}}}(x)$
is the generalized drift of
$\xi$
in state x. Furthermore, if
$v(X_n)=X_n$
for each n, then
${\delta_{_{\nu}}}(x)$
is simply the drift in state x.
Foster [Reference Foster17] provided a sufficient condition for the positive recurrence of a one-dimensional, irreducible DTMC on the state space
${\mathbb{Z}_{_+}}$
. Fayolle, Malyshev, and Menshikov [Reference Fayolle, Malyshev and Menshikov16] extended Foster’s result by proving necessity of the drift condition and expanding its applicability to DTMCs with general countable state spaces. For convenience, we restate Theorem 2.2.3 of [Reference Fayolle, Malyshev and Menshikov16] here as Theorem 1.
Theorem 1. (Fayolle, Malyshev, and Menshikov [Reference Fayolle, Malyshev and Menshikov16]) An irreducible, aperiodic DTMC
${\{{X_n}\colon {n\geq 0}\}}$
on a countable state space S is positive recurrent if and only if there exist a function
$\nu\colon S\to (0,\infty)$
, a number
$\epsilon>0$
, and a finite set
$B\subset S$
such that
\begin{equation}
{\delta_{_{\nu}}}(x)\le -\epsilon,\;\mbox{$x\notin B$}\quad\mbox{and}\quad{\mathbb{E}({\nu(X_{n+1})}|{X_n=x})}<\infty,\;\mbox{$x\in B$}.
\label{eqn3}
\end{equation}
If we take
$S={\mathbb{Z}_{_+}}$
, condition (3) can be equivalently restated as follows: for some number
${\epsilon}>0$
, there exists an
$N_{\epsilon}\in {\mathbb{N}}$
such that
\[
{\delta_{_{\nu}}}(i)\le -\epsilon,\;\mbox{$i\ge N_{\epsilon}$}\quad\mbox{and}\quad{\mathbb{E}({\nu(X_{n+1})}|{X_n=i})}<\infty,\;\mbox{$i < N_{\epsilon}$}.
\]
In Section 3 we derive the generalized drift function for a specific form of the Lyapunov function
$\nu$
and employ a modified version of Theorem 1 to establish sufficient conditions for recurrence, and necessary and sufficient conditions for positive recurrence, of the LDQBD process
$\Phi$
.
3. Component and average drift conditions
For the results that follow, we consider a specific class of Lyapunov functions for the LDQBD process
$\Phi$
and its associated drift function. For each
$(i,j)\in S$
, define
$\nu\colon S\to(0,\infty)$
as follows:
\begin{equation}
\nu(i,j)=
\begin{cases}
k_{0j} & i=0,\;j\in{{\cal P}}, \\
i+k_{ij} & i\ge 1,\;j\in{{\cal P}},\end{cases}
\label{eqn4}
\end{equation}
where the constant
$k_{0j}>0$
for any
$j\in{{\cal P}}$
and
$k_{ij}$
is a non-negative constant for each
$i\in {\mathbb{N}}$
and
$j\in{{\cal P}}$
. We let
${\textbf{\textit{k}}}=[k_{ij}]$
denote the matrix composed of these constants, and let
${\textbf{\textit{k}}^{({i})}}=(k_{i1},k_{i2},\ldots,k_{iK})'$
denote the transpose of the ith row of
${\textbf{\textit{k}}}$
with the requirement that
${\textbf{\textit{k}}^{({0})}}>{\textbf{0}}$
. Let
\begin{equation}
{\delta_{_{\nu}}}(i,j)\,{:\!=}\,{\mathbb{E}({\nu{({X_{n+1},Y_{n+1}})}-\nu{({X_n,Y_n})}}|{(X_n,Y_n)=(i,j)})}
\label{eqn5}
\end{equation}
be the generalized drift in state (i,j) and define the column vector
\[
{\Delta^{(i)}}=({\delta_{_{\nu}}}(i,1),\ldots,{\delta_{_{\nu}}}(i,K))'
\]
as the level-i drift vector. The following proposition shows how to obtain
${\Delta^{(i)}}$
for each
$i\in {\mathbb{Z}_{_+}}$
.
Proposition 1. Let
$\Phi$
be the discrete-time LDQBD process with state space S and one-step transition probability matrix given by (2). For the Lyapunov function of equation (4), the generalized level-i drift vector is
\begin{equation} %%\label{eq:ldqbd_drift_fn1}
{\Delta^{(i)}}=\begin{cases}
{A_{0}^{{(0)}}}\textbf{\textit{e}}+{A_{0}^{{(0)}}}{\textbf{\textit{k}}^{({1})}}+{A_{1}^{{(0)}}}{\textbf{\textit{k}}^{({0})}}-{\textbf{\textit{k}}^{({0})}} & i=0,\\
{({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{({{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i+1})}}+{A_{1}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}+{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i-1})}}})}-{\textbf{\textit{k}}^{({i})}} & i\ge 1.\end{cases}
\end{equation}
Proof. For notational brevity, let
$x=(i,j)$
and
$x'=(i',j')$
be two states in S, and let
$p_{xx'}$
denote the one-step transition probability from x to x’. First we consider the case when
$i\ge 1$
. Applying equations (4) and (5), the generalized drift in state
$x=(i,j)$
is
\begin{equation}
{\delta_{_{\nu}}}(x)=\sum_{x'\in S}p_{xx'}[\nu(x')-\nu(x)]=\sum_{x'\in S}p_{xx'}[(i'+k_{i'j'})-(i+k_{ij})].
\label{eqn6}
\end{equation}
For each
$i\in {\mathbb{N}}$
, consider the ith-level partition
$({S_{i}^{-}},{S_{i}^{\circ}},{S_{{i}}^{+}})$
of S, where
\begin{equation}\label{eq:i_th_ss_partition}
{S_{i}^{-}}={\{{(i-1,j)}\colon {j\in{{\cal P}}}\}}, \quad {S_{i}^{\circ}}={\{{(i,j)} \colon {j\in{{\cal P}}}\}},\quad {S_{i}^{+}}={\{{(i+1,j)} \colon {j\in{{\cal P}}}\}},
\end{equation}
which allows us to decompose the summation in (6) as follows:
\begin{align}
{\delta_{_{\nu}}}(x)
&=\sum_{x'\in S}p_{xx'}[(i'+k_{i'j'})-(i+k_{ij})]\notag \\
&=\sum_{x'\in{S_{i}^{-}}}p_{xx'}(k_{i-1,j'}-k_{ij}-1)+\sum_{x'\in{S_{i}^{\circ}}}p_{xx'}(k_{ij'}-k_{ij})
+\sum_{x'\in{S_{i}^{+}}}p_{xx'}(k_{i+1,j'}-k_{ij}+1).
\label{eqn7}\end{align}
Equation (7) can be equivalently expressed as
\begin{align*}
{\delta_{_{\nu}}}(x)
&=\sum_{j'\in{{\cal P}}}{[A_{2}^{{(i)}}]_{jj'}}{({k_{i-1,j'}-k_{ij}-1})}+\sum_{j'\in{{\cal P}}}{[A_{1}^{{(i)}}]_{jj'}}{({k_{ij'}-k_{ij}})}
\\ &\quad\,
+\sum_{j'\in{{\cal P}}}{[A_{0}^{{(i)}}]_{jj'}}{({k_{i+1,j'}-k_{ij}+1})}
\\ &
=\sum_{j'\in{{\cal P}}} ({ [A_{0}^{{(i)}}]_{jj'}}-{ [A_{2}^{{(i)}}]_{jj'}})-k_{ij}\sum_{j'\in{{\cal P}}} [{A^{({i})}}]_{jj'}
\\ &\quad\,
+\sum_{j'\in{{\cal P}}}k_{i-1,j'}{ [A_{2}^{{(i)}}]_{ij'}}+k_{ij'}{ [A_{1}^{{(i)}}]_{jj'}}+k_{i+1,j'}{ [A_{0}^{{(i)}}]_{jj'}},
\end{align*}
which in matrix–vector form gives
\[
{\Delta^{(i)}}={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{ ({{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i+1})}}+{A_{1}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}+{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i-1})}}})}-{\textbf{\textit{k}}^{({i})}}.
\]
Second, for the boundary case
$i=0$
, noting that there are no downward jumps from level 0, we can repeat the derivation for the case
$i\ge 1$
and exclude all terms containing
${A_{2}^{{(i)}}}$
. Doing so yields
\[
{\Delta^{({0})}}={A_{0}^{{(0)}}}\textbf{\textit{e}}+{A_{0}^{{(0)}}}{\textbf{\textit{k}}^{({1})}}+{A_{1}^{{(0)}}}{\textbf{\textit{k}}^{({0})}}-{\textbf{\textit{k}}^{({0})}},
\]
and the proof is complete.
We now consider the generalized drift vector
${\Delta^{(i)}}$
restricted to the class of Lyapunov functions (4) for which
k
has identical rows, that is,
${\textbf{\textit{k}}^{({i})}}=\textbf{\textit{c}}\ge {\textbf{0}}$
for all
$i\in {\mathbb{N}}$
. In this case, we obtain a simplified (homogeneous) version of the drift vector given by
\begin{equation} %%\label{eq:ldqbd_drift_fn2}
{\Delta_h^{({i})}}={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{A^{({i})}}\textbf{\textit{c}}-\textbf{\textit{c}},\quad i\in{\mathbb{N}}.
\end{equation}
The relationship between
${\Delta_h^{({i})}}$
and
${\Delta^{(i)}}$
is critical to our analysis. We will establish the fact that, under suitable conditions, the existence of solutions
c
that satisfy
${\Delta_h^{({i})}}\le -{\boldsymbol{\epsilon}}$
imply the existence of solutions
$\{{\textbf{\textit{k}}^{({i-1})}},{\textbf{\textit{k}}^{({i})}},{\textbf{\textit{k}}^{({i+1})}}\}$
that satisfy
${\Delta^{(i)}}\le -{\boldsymbol{\epsilon}}$
, where
${\boldsymbol{\epsilon}}=({\epsilon},{\epsilon},\ldots,{\epsilon})'$
for some
${\epsilon}>0$
.
Our first result, Theorem 2, follows immediately by applying Foster’s criterion to the homogeneous drift vector
${\Delta_h^{({i})}}$
. Before stating this result, we impose a partial ordering (
$\leq_s$
) on the state space S. For any two states (i,j) and (i’,j’) in S, let
\begin{equation}
(i,j)\leq_s (i',j')\quad\mbox{if and only if } i\leq i',
\label{eqn8}
\end{equation}
for any
$j,j'\in {{\cal P}}$
(i.e. S is ordered according to the level of each state). This ordering allows us to apply results suited for processes whose state space is
${\mathbb{Z}_{_+}}$
.
Theorem 2. Suppose that
$\Phi$
is an irreducible, aperiodic discrete-time LDQBD process.
(i)
$\Phi$
is recurrent if there exists a constant vector
${\hat{\textbf{\textit{c}}}}\in{\mathbb{R}_{_+}^K}$
such that, for some
$N\in {\mathbb{N}}$
,
\[
{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}\le (I-{A^{({i})}}){\hat{\textbf{\textit{c}}}}\quad\mbox{for all $i\geq N$}.
\]
(ii)
$\Phi$
is positive recurrent if there exists a constant vector
${\hat{\textbf{\textit{c}}}}\in{\mathbb{R}_{_+}^K}$
such that, for some
$\epsilon>0$
, there exists an
$N_{{\epsilon}}\in {\mathbb{N}}$
such that where
\[
{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}\le (I-{A^{({i})}}){\hat{\textbf{\textit{c}}}}-{\boldsymbol{\epsilon}}\quad\mbox{for all $i\geq N_{\epsilon}$}.
\]
${\boldsymbol{\epsilon}}=(\epsilon,\epsilon,\ldots,\epsilon)'$
.
Proof. For recurrence, we first note that
$\nu(i,j)=i+\hat{c}_j\to \infty$
as
$i\to \infty$
for all
$j\in {{\cal P}}$
due to the partial ordering (8) and non-negativity of
$\hat{c}_j$
. By supposition, there exists
${\hat{\textbf{\textit{c}}}}\in {\mathbb{R}_{_+}^K}$
and some
$N\in {\mathbb{N}}$
such that the level-i drift vector
\[
{\Delta_h^{({i})}}={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{A^{({i})}}{\hat{\textbf{\textit{c}}}}-{\hat{\textbf{\textit{c}}}}\le {\textbf{0}}\quad\mbox{for all $i\geq N$},
\]
or equivalently
\[
{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}\le (I-{A^{({i})}}){\hat{\textbf{\textit{c}}}}\quad\mbox{for all $i\geq N$}.
\]
This condition holds for all
$(i,j)\notin B\,{:\!=}\,\{0,1,\ldots,N-1\}\times {{\cal P}}$
, where
$|B|<\infty$
. Therefore, by Theorem 2.1 of [Reference Fayolle, Malyshev and Menshikov15], the process is recurrent.
For positive recurrence, suppose there exists a constant vector
${\hat{\textbf{\textit{c}}}}\in{\mathbb{R}_{_+}^K}$
, a number
$\epsilon>0$
, and a positive integer
$N_{{\epsilon}}$
such that
\[
{\Delta_h^{({i})}}={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{A^{({i})}}{\hat{\textbf{\textit{c}}}}-{\hat{\textbf{\textit{c}}}}\le -{\boldsymbol{\epsilon}}\quad\mbox{for all $i\geq N_{\epsilon}$},
\]
or equivalently
\[
{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}\le (I-{A^{({i})}}){\hat{\textbf{\textit{c}}}}-{\boldsymbol{\epsilon}}\quad\mbox{for all $i\geq N_{\epsilon}$}.
\]
Thus, we let
$B_{\epsilon}\,{:\!=}\,\{0,1,\ldots,N_{\epsilon}-1\}\times {{\cal P}}$
be a finite subset of S and see that
${\delta_{_{\nu}}}(i,j)\le -{\epsilon}$
for all
$(i,j)\notin B_{\epsilon}$
. It remains to show that
\[
\mu_{ij}\,{:\!=}\,{\mathbb{E}({\nu(X_{n+1},Y_{n+1})}|{(X_n,Y_n)=(i,j)})}<\infty
\]
for all
$(i,j)\in B_{\epsilon}$
. In fact, we will show that
$\mu_{ij}$
is finite for all
$(i,j)\in S$
, since level jumps are bounded in a LDQBD. Fixing
$x=(i,j)$
and letting
$x'=(i',j')$
, we observe that
\begin{equation}
\mu_{ij}\le |\mu_{ij}|=\bigg|\sum_{x'\in S}p_{xx'}(i'+k_{i'j'})\bigg|\le \sum_{x'\in S}|p_{xx'}|\cdot|i'+k_{i'j'}|.
\label{eqn9}
\end{equation}
To see that the rightmost term of inequality (9) is finite, we note that
$p_{xx'}=0$
for any state
$x'\in S^c_{ij}$
, where for each
$(i,j)\in S$
,
\[
S_{ij}\,{:\!=}\,
\begin{cases}
\{(i',j')\in S\colon i'\in \{i,i+1\},\,j'\in {{\cal P}}\} & i=0, \\
\{(i',j')\in S\colon i'\in \{i-1,i,i+1\},\,j'\in {{\cal P}}\} & i\ge 1.
\end{cases}
\]
Noting that
$|S_{ij}|<\infty$
, and by inequality (9),
\begin{equation}
\mu_{ij}\le \sum_{x'\in S}|p_{xx'}|\cdot|i'+k_{i'j'}|\le \sum_{x'\in S_{ij}}1\cdot|i'+k_{i'j'}|=\sum_{x'\in S_{ij}}\nu(i',j')<\infty.
\end{equation}
Therefore, by Theorem 2.2.3 of [Reference Fayolle, Malyshev and Menshikov16], the process is positive recurrent.
Next we state our main results, namely necessary and sufficient conditions for recurrence and positive recurrence, respectively, based on an average drift criterion. Before stating the main results, we first state the following assumption, which describes the specific class of LDQBD processes under consideration.
Assumption 1. For the discrete-time LDQBD process
$\Phi$
, there exist
$K\times K$
sub-stochastic matrices,
$A_2^*$
,
$A_1^*$
, and
$A_0^*$
whose sum
\[
A^* = A_2^* + A_1^* + A_0^*
\]
is stochastic and which are related to the process
$\Phi$
via the limit
\[
\lim_{i\to\infty}A_k^{(i)}=A_k^*,\quad k=0,1,2,
\]
where the limit holds element-wise.
Assumption 1 asserts that, if the level is sufficiently large, then the LDQBD process evolves in a manner similar to that of a level-independent QBD process. The class of models satisfying this condition is quite large, encompassing many models arising in queueing, reliability, inventory and telecommunications settings.
Theorem 3. Let
$\Phi$
be an irreducible, aperiodic discrete-time LDQBD process satisfying Assumption 1 and define the scalar quantities
\begin{equation} %%\label{eq:simple_drift}
{D^{({i})}}={\bpi^{({i})}}{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}},
\end{equation}
where
${\bpi^{({i})}}$
is the invariant row vector of
${A^{({i})}}={A_{0}^{{(i)}}}+{A_{1}^{{(i)}}}+{A_{2}^{{(i)}}}$
for each
$i\in{\mathbb{Z}_{_+}}$
.
(i)
$\Phi$
is recurrent if and only if there exists an
$N\in {\mathbb{N}}$
such that
\[
{D^{({i})}}\leq 0\quad \mbox{for all $i\ge N$.}
\]
(ii)
$\Phi$
is positive recurrent if and only if, for some positive number
$\epsilon$
, there exists an
$N_{\epsilon}\in
{\mathbb{N}}$
such that
\[
{D^{({i})}}<-{\epsilon} \quad\mbox{for all $i\ge N_{\epsilon}$}.
\]
Before proving Theorem 3, let us define an operator
${\Gamma^{(i)}} \colon {\mathbb{R}}^K\to {\mathbb{R}}^K$
by
\[
{\Gamma^{(i)}}(\textbf{\textit{c}})={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{A^{({i})}}\textbf{\textit{c}}-\textbf{\textit{c}}
\]
such that
${\Gamma^{(i)}}(\textbf{\textit{c}})={\Delta_h^{({i})}}$
. Additionally, for each
$i\in {\mathbb{Z}_{_+}}$
, define the null sets for
${\Gamma^{(i)}}$
by
\[
\mathcal{N}({\Gamma^{(i)}})={ \{{\textbf{\textit{c}}\in {\mathbb{R}}^K} \colon {{\Gamma^{(i)}}(\textbf{\textit{c}})={\textbf{0}}}\}}\quad\mbox{and}\quad\mathcal{N}^+({\Gamma^{(i)}})=\mathcal{N}({\Gamma^{(i)}})\cap{\mathbb{R}_{_+}^K}.
\]
The proof of Theorem 3 requires two technical lemmas.
Lemma 1.
${D^{({i})}}=0$
if and only if
$\mathcal{N}^+({\Gamma^{(i)}})\neq\emptyset$
.
Proof.
$(\Leftarrow )$
Fix the level i and suppose there exists some
$\textbf{\textit{c}}\in \mathcal{N}^+({\Gamma^{(i)}})$
. Then
\[
{\Gamma^{(i)}}(\textbf{\textit{c}})={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{A^{({i})}}\textbf{\textit{c}}-\textbf{\textit{c}}={\textbf{0}},
\]
which implies
\begin{equation}
{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}=-{A^{({i})}}\textbf{\textit{c}}+\textbf{\textit{c}}.
\label{eqn10}
\end{equation}
Left-multiplying both sides of (10) by
${\bpi^{({i})}}$
yields
\begin{align*}
D^{(i)}={\bpi^{({i})}}{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}=-{\bpi^{({i})}}{A^{({i})}}\textbf{\textit{c}}+{\bpi^{({i})}}\textbf{\textit{c}}=-{\bpi^{({i})}}\textbf{\textit{c}}+{\bpi^{({i})}}\textbf{\textit{c}}=0.
\end{align*}
$(\Rightarrow )$
Now suppose
${D^{({i})}}=0$
. We seek to show the existence of a
$\textbf{\textit{c}}\in {\mathbb{R}_{_+}^K}$
such that
\begin{equation}
{\Gamma^{(i)}}(\textbf{\textit{c}})={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}} +{ ({{A^{({i})}}-I})}\textbf{\textit{c}}={\textbf{0}}.
\label{eqn11}
\end{equation}
To this end, we employ two related Theorems of Alternative – one due to Farkas and the other due to Gordan – both of which are summarized in [Reference Mangasarian28] and restated without proof in the Appendix. Using (11), we can write the linear system of equalities
\begin{equation}
{ ({{A^{({i})}}-I})}\textbf{\textit{c}}=-{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}.
\label{eqn12}
\end{equation}
Setting
c
=
e
, we note that
${ ({{A^{({i})}}-I})}\textbf{\textit{e}}={\textbf{0}}$
; hence,
e
is a non-negative, non-zero solution to the linear system of equations
\[
{ ({{A^{({i})}}-I})}\textbf{\textit{c}} = {\textbf{0}}.
\]
Therefore Alternative (ii) of Gordan’s theorem [Reference Gordan18] cannot be satisfied; hence,
\[
\textbf{\textit{y}}'{ ({{A^{({i})}}-I})}\ngtr {\textbf{0}}\quad \mbox{for all $\textbf{\textit{y}}\in {\mathbb{R}}^K$}.
\]
This implies that the system in Alternative (ii) of Farkas’s lemma, namely
$\textbf{\textit{y}}'{ ({{A^{({i})}}-I})}\ge {\textbf{0}}$
, can only be satisfied in equality. Because A
(i)
is finite and irreducible, the unique solution at equality is
$\textbf{\textit{y}}'={\bpi^{({i})}}$
(up to a multiplicative constant), since
${\bpi^{({i})}}{ ({{A^{({i})}}-I})}={\textbf{0}}$
. However,
\[
-\textbf{\textit{y}}'{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}=-{\bpi^{({i})}}{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}=-{D^{({i})}}=0.
\]
Hence, there does not exist
$\textbf{\textit{y}}\in {\mathbb{R}}^K$
satisfying Alternative (ii) of Farkas’s lemma, which implies that Alternative (i) of Farkas holds. That is, there exists a
$\textbf{\textit{c}}\ge {\textbf{0}}$
that solves (12), from which we conclude that
${\mathcal{N}}^+({\Gamma^{(i)}})\ne \emptyset$
.
We next demonstrate the relationship of the average drift D
(i)
to the solution
c
of the system of inequalities
${\Gamma^{(i)}}(\textbf{\textit{c}})\leq -{\boldsymbol{\epsilon}}$
, where
${\boldsymbol{\epsilon}}=({\epsilon},{\epsilon},\ldots{\epsilon})>{\textbf{0}}$
. For each
$i\in {\mathbb{Z}_{_+}}$
, define the cones
\[
{\mathcal{C}}_{{\epsilon}}({\Gamma^{(i)}})={ \{{\textbf{\textit{c}}\;\in{\mathbb{R}}^K} \colon {{\Gamma^{(i)}}(\textbf{\textit{c}})\leq-{\boldsymbol{\epsilon}}}\}}\quad\mbox{and}\quad
{\mathcal{C}}_{{\epsilon}}^+({\Gamma^{(i)}})\,{:\!=}\,{\mathcal{C}}_{{\epsilon}}({\Gamma^{(i)}})\cap{\mathbb{R}_{_+}^K}.
\]
Lemma 2. For some positive number
$\epsilon$
,
${D^{({i})}}\leq -\epsilon$
if and only if
${\mathcal{C}}_{\epsilon}^+({\Gamma^{(i)}})\neq\emptyset$
.
Proof.
$(\Leftarrow )$
Suppose there exists some
$\textbf{\textit{c}}\in {\mathcal{C}}_{{\epsilon}}^+({\Gamma^{(i)}})$
. That is, for such a solution,
\[
{\Gamma^{(i)}}(\textbf{\textit{c}})={ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{ ({{A^{({i})}}-I})}\textbf{\textit{c}}\le-{\boldsymbol{\epsilon}}.
\]
Left-multiplying by the stochastic vector
${\bpi^{({i})}}$
yields
\[
{\bpi^{({i})}}{\Gamma^{(i)}}(\textbf{\textit{c}})={\bpi^{({i})}} [{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{ ({{A^{({i})}}-I})}\textbf{\textit{c}}]\le-{\bpi^{({i})}}{\boldsymbol{\epsilon}}=-{\epsilon}.
\]
However, note that
${\bpi^{({i})}}{\Gamma^{(i)}}(\textbf{\textit{c}})={D^{({i})}}+0={D^{({i})}}$
; therefore, we conclude that
${D^{({i})}}\le-{\epsilon}$
.
$(\Rightarrow)$
Conversely, suppose that
${D^{({i})}}\le-\epsilon$
for some
$\epsilon>0$
, which implies that
${D^{({i})}}\textbf{\textit{e}}\le-{\boldsymbol{\epsilon}}$
. Our aim is to show the existence of a non-negative vector
$\hat{\textbf{\textit{c}}}$
such that
\[
{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{ ({{A^{({i})}}-I})}\hat{\textbf{\textit{c}}}={D^{({i})}}\textbf{\textit{e}},
\]
or equivalently
\begin{equation}
{ ({{A^{({i})}}-I})}\hat{\textbf{\textit{c}}}={D^{({i})}}\textbf{\textit{e}}-{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}.
\label{eqn13}
\end{equation}
To simplify notation, let
$M\,{:\!=}\,{A^{({i})}}-I$
and
$\textbf{\textit{b}}\,{:\!=}\,{D^{({i})}}\textbf{\textit{e}}-{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}$
. As shown in the proof of Lemma 1, the system
$\textbf{\textit{y}}'M\ge {\textbf{0}}$
can only be satisfied in equality, and the unique solution is
$\textbf{\textit{y}}'={\bpi^{({i})}}$
up to a multiplicative constant. Therefore, it remains to show that
$\textbf{\textit{y}}'\textbf{\textit{b}}\nless 0$
. We see that
\begin{align*}
\textbf{\textit{y}}'\textbf{\textit{b}}
&={\bpi^{({i})}}\textbf{\textit{b}}\\
& = {\bpi^{({i})}} [{D^{({i})}}\textbf{\textit{e}}-{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}]\\
& = {\bpi^{({i})}}{D^{({i})}}\textbf{\textit{e}} - {\bpi^{({i})}}{ ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}} \notag \\
& = {D^{({i})}} - {D^{({i})}}\\
&= 0.
\end{align*}
Hence, there does not exist a
$\textbf{\textit{y}}\ge {\textbf{0}}$
satisfying
$\textbf{\textit{y}}'\textbf{\textit{b}}<0$
. Therefore, by Farkas’s lemma, there is a non-negative solution
$\hat{\textbf{\textit{c}}}$
to the system (13). Noting that
${D^{({i})}}\textbf{\textit{e}}\le -{\boldsymbol{\epsilon}}$
, we see that
${\mathcal{C}}_{{\epsilon}}^+({\Gamma^{(i)}})\,{\neq}\,\emptyset$
.
Equipped with Lemmas 1 and 2, we are now prepared to prove the main result, Theorem 3.
Proof of Theorem 3. Part (i): recurrence. To prove the first result, we will establish that the conditions required by Theorem 2.2.1 of [Reference Fayolle, Malyshev and Menshikov16] are met, that is,
$\nu(i,j)\to\infty$
as
$i\to \infty$
and
${\Delta^{(i)}}\le {\textbf{0}}$
for sufficiently large i. Under the partial ordering (8), it is clear that, for each
$j\in
{{\cal P}}$
,
$\nu(i,j)=i+k_{ij}\to\infty$
as
$i\to\infty$
due to the non-negativity of
$k_{ij}$
. Hence, it remains to show that, for sufficiently large i,
${D^{({i})}}\le 0$
if and only if there exists a sequence of constant vectors
$\{{\textbf{\textit{k}}^{({i})}} \colon i\in {\mathbb{Z}_{_+}}\}$
such that
${\Delta^{(i)}}\le {\textbf{0}}$
. To this end, for each
$i\in {\mathbb{Z}_{_+}}$
, define the operator
${\Lambda^{(i)}}$
such that
\[
{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})} \,{:\!=}\, { ({{A_{0}^{{(i)}}}-{A_{2}^{{(i)}}}})}\textbf{\textit{e}}+{ ({{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i+1})}}+{A_{1}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}+{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i-1})}}})}-{\textbf{\textit{k}}^{({i})}}={\Delta^{(i)}}.
\]
(
$\Rightarrow$
) Suppose there is some
$N\in {\mathbb{N}}$
such that
${D^{({i})}}\le 0$
for each
$i\ge N$
. Our aim is to show that there exists a number
$N^*\geq N$
and a sequence of vectors
\[
{{\cal K}}={ \{{{\textbf{\textit{k}}^{({i})}}\in{\mathbb{R}_{_+}^K}} \colon {i\in{\mathbb{Z}_{_+}}}\}}
\]
such that
${{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}\le{\textbf{0}}$
whenever
$i\geq N^*$
. To this end, we first show that the component-wise limits
\[
\bell_g=\lim_{i\to\infty}{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\quad\mbox{and}\quad\bell_l=\lim_{i\to\infty}{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}
\]
exist for a certain choice of
${{\cal K}}$
. Next, we will show that
$\bell_g$
and
$\bell_l$
are equal, and when it has been shown that
$\bell_g\leq {\textbf{0}}$
, we will have demonstrated the sufficiency of part (i) of Theorem 3.
To establish the existence of
${{\cal K}}$
, we first obtain a solution to the inequality
\begin{equation}
{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})={ ({A_0^{(i)}-A_2^{(i)}})}\textbf{\textit{e}}+ ({A^{({i})}}-I){\textbf{\textit{k}}^{({i})}}\le{\textbf{0}}.
\label{eqn14}
\end{equation}
By supposition, we have that
$D^{(i)}\le 0$
for each
$i\ge N$
; hence, we can satisfy (14) by solving the system of linear equalities
${\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})=D^{(i)}\textbf{\textit{e}}$
. That is,
\[
{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})={ ({A_0^{(i)}-A_2^{(i)}})}\textbf{\textit{e}}+({A^{({i})}}-I){\textbf{\textit{k}}^{({i})}}=D^{(i)}\textbf{\textit{e}}.
\]
By rearranging the terms in the above expression, we obtain
\begin{equation}
({A^{({i})}}-I){\textbf{\textit{k}}^{({i})}}=D^{(i)}\textbf{\textit{e}}- (A_0^{(i)}-A_2^{(i)})\textbf{\textit{e}}.
\label{eqn15}
\end{equation}
Since A (i) −I is singular, an explicit solution of (15) can alternatively be obtained by employing the theory of group inverses. By Theorem 2.1 of [Reference Meyer31], the existence and uniqueness of the group inverse
\[
{ (T^{({i})})^{\#}}={{{ ({I-{A^{({i})}}})}}^{\#}}
\]
of the matrix
${T^{({i})}}=I-{A^{({i})}}$
is guaranteed, as each A
(i)
is the transition matrix of an irreducible, time-homogeneous Markov chain. Theorem 2.2 of [Reference Rao and Mitra41] shows that every possible solution
k
(i) of (15) is of the form
\begin{equation}
{\textbf{\textit{k}}^{({i})}}=-{ (T^{({i})})^{\#}}{ ({D^{(i)}\textbf{\textit{e}}- (A_0^{(i)}-A_2^{(i)})\textbf{\textit{e}}})}+ { ({I-{ (T^{({i})})^{\#}}{T^{({i})}}})}\textbf{\textit{z}}_i,
\label{eqn16}
\end{equation}
where
$\textbf{\textit{z}}_i\in{\mathbb{R}}^K$
is arbitrary for each
$i\ge 1$
. Equation (16) can be further refined by noting the equivalence
\begin{equation}
\Pi^{(i)} = I-{ (T^{({i})})^{\#}}{T^{({i})}},
\label{eqn17}
\end{equation}
where
$\Pi^{(i)}\in{\mathbb{R}}^{K\times K}$
is the matrix whose rows are all the stationary probability vector
${\bpi^{({i})}}$
(see Theorem 2.3 of [Reference Meyer31]), from which we obtain
\begin{equation}
{\textbf{\textit{k}}^{({i})}}= -{ (T^{({i})})^{\#}}{ ({D^{(i)}\textbf{\textit{e}}- (A_0^{(i)}-A_2^{(i)})\textbf{\textit{e}}})} + \Pi^{(i)}\textbf{\textit{z}}_i.
\label{eqn18}
\end{equation}
For some non-negative scalar
$m_i$
, let
$\textbf{\textit{z}}_i\,{:\!=}\,m_i\,\textbf{\textit{e}}\in{\mathbb{R}}^K$
, the column vector consisting of non-negative scalar entries
$m_i$
. Equation (18) then reduces to
\begin{equation}
{\textbf{\textit{k}}^{({i})}}=-{ (T^{({i})})^{\#}}{ ({D^{(i)}\textbf{\textit{e}}- (A_0^{(i)}-A_2^{(i)})\textbf{\textit{e}}})}+m_i\textbf{\textit{e}}.
\label{eqn19}
\end{equation}
Next, we show that there exists a positive sequence
${ \{{m_i} \colon {i\in{\mathbb{N}}}\}}$
that induces the solutions
k
(i) to be non-negative in (19). To this end, it is necessary to show that
\[
{ (T^{({i})})^{\#}}={{{ ({I-{A^{({i})}}})}}^{{\#}}}\quad\mbox{and}\quad{D^{({i})}} = {\bpi^{({i})}}{ ({{A_{0}^{{(i)}}} - {A_{2}^{{(i)}}}})}\textbf{\textit{e}}
\]
converge as
$i\to \infty$
. By Assumption 1, the convergence of sequences
${ \{{{A_{j}^{{(i)}}}}\}}$
for
$j=0,1,2$
ensures convergence of I−A
(i). Next, we use this convergence, along with (17), to show that if the generalized inverse
${ \{{{ (T^{({i})})^{\#}}}\}}$
converges, then the sequence of stationary vectors
${ \{{{\bpi^{({i})}}}\}}$
likewise converges. Lemma 3 of the Appendix establishes that
\[
\lim_{i\to\infty}{ (T^{({i})})^{\#}} = {{{ ({T^*})}}^{{\#}}},
\]
ensuring that all terms on the right-hand side of (19) (with the exception of
$m_i$
) form convergent sequences. We will now choose an appropriate sequence of numbers
$\{m_i\}$
. Define the limits
\[
D^*\,{:\!=}\,\lim_{i\to\infty}{D^{({i})}},\quad T^*\,{:\!=}\,\lim_{i\to\infty}{T^{({i})}},\quad \bpi^*\,{:\!=}\, \lim_{i\to\infty}{\bpi^{({i})}}\ro{,}
\]
and the function
$\kappa\colon {\mathbb{R}}\to{\mathbb{R}}^K$
by
\begin{equation}
\kappa(x)\,{:\!=}\,-{{{ ({T^*})}}^{{\#}}} [D^*\textbf{\textit{e}}-(A_0^*-A_2^*)\textbf{\textit{e}}]+x\textbf{\textit{e}}.
\label{eqn20}
\end{equation}
As the first summand on the right-hand side of (20) is a real constant vector, we may choose a sufficiently large number
$M>0$
such that
$\kappa(M)\ge {\textbf{0}}$
component-wise. The convergence of
${ \{{{\textbf{\textit{k}}^{({i})}}}\}}$
in (19) when
$m_i\colon =M$
ensures there is an integer
$J\in{\mathbb{N}}$
such that
${\textbf{\textit{k}}^{({i})}}\ge {\textbf{0}}$
for every
$i\ge J$
. We may thus set
\[
{{\cal K}}\,{:\!=}\, { \{{{\textbf{\textit{k}}^{({i})}}} \colon {i=0,\ldots, J-1}\}} \cup { \{{{\textbf{\textit{k}}^{({i})}}} \colon {i\ge J,\,m_i=M}\}}\subset{\mathbb{R}_{_+}^K},
\]
where vectors
${ \{{{\textbf{\textit{k}}^{({i})}}} \colon {i=0,\ldots, J-1}\}}\subset{\mathbb{R}_{_+}^K}$
may be chosen arbitrarily. In this way, we obtain a sequence
${{\cal K}}$
of feasible solutions to
${\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\le {\textbf{0}}$
that converges to some vector
${\textbf{\textit{k}}}^*\in{\mathbb{R}_{_+}^K}$
. Now, the existence of
${\textbf{\textit{k}}}^*=\lim_{i\to\infty}{\textbf{\textit{k}}^{({i})}}$
ensures convergence of the sequences
${ \{{{A_{j}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
for
$j=0,1,2$
, and hence of
${ \{{{A^{({i})}}{\textbf{\textit{k}}^{({i})}}} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
. Consequently, we obtain the convergence of
${ \{{{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
and
${ \{{{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
with the additional property that, as
$i\to \infty$
,
\[
{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\to { ({A_0^*-A_2^*})}\textbf{\textit{e}}+(A^*-I){\textbf{\textit{k}}}^*\le {\textbf{0}}.
\]
We now show that
${ \{{{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
and
${ \{{{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
converge to the same limit. To this end, let
$\|B\|$
be any matrix norm of a square matrix of K dimensions with real entries and let
$\|B\|_{\rm op}$
be the operator norm of a bounded linear transformation
$\mathbb{R}^K\to \mathbb{R}^K$
whose operator matrix is B. Observe that for any
$\epsilon>0$
and sufficiently large i,
\begin{align}
& \|{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}- {\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\| \notag \\
&\qquad = \|{ ({{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i+1})}}-{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}})}+ { ({{A_{1}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}-{A_{1}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}})}+ { ({{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i-1})}}-{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}})}\| \notag \\
&\qquad \le \|{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i+1})}}-{A_{0}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}\|+ \|{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i-1})}}-{A_{2}^{{(i)}}}{\textbf{\textit{k}}^{({i})}}\| \notag \\
&\qquad \le \|{A_{0}^{{(i)}}}\|_{\textrm{op}} \|{\textbf{\textit{k}}^{({i+1})}}-{\textbf{\textit{k}}^{({i})}}\|+ \|{A_{2}^{{(i)}}}\|_{\textrm{op}} \|{\textbf{\textit{k}}^{({i-1})}}-{\textbf{\textit{k}}^{({i})}}\| \notag \\
&\qquad \le \eta_0 \|{\textbf{\textit{k}}^{({i+1})}}-{\textbf{\textit{k}}^{({i})}}\|+\eta_2 \|{\textbf{\textit{k}}^{({i-1})}}-{\textbf{\textit{k}}^{({i})}}\| \notag \\
&\qquad \le \eta(\epsilon/2) + \eta(\epsilon/2) \notag\\
& \qquad =\eta\epsilon,
\label{eqn21}\end{align}
where
$\eta = \max\{\eta_0,\eta_2\}$
, since convergent sequences are Cauchy-convergent in finite-dimensional Euclidean space. Thus, there exists an
$N^*>N$
such that
${{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}\leq{\textbf{0}}$
for each
$i\geq N^*$
; hence, the process
$\Phi$
is recurrent.
(
$\Leftarrow$
) Conversely, suppose that
$\Phi$
is recurrent. By [Reference Fayolle, Malyshev and Menshikov15, Theorem 2.2.1], there exists some
$N^*>0$
and some sequence
${{\cal K}}={ \{{{\textbf{\textit{k}}^{({i})}}} \colon {i\in{\mathbb{Z}_{_+}}}\}}\subset{\mathbb{R}_{_+}^K}$
of vectors such that
\begin{equation}
{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}\leq{\textbf{0}}, \quad i\geq N^*.
\label{eqn22}
\end{equation}
It is possible to construct a convergent
${{\cal K}}'$
from the elements of
${{\cal K}}$
that satisfies (22). Indeed, due to Assumption 1, each
${A_{k}^{{(i)}}}$
for
$k=0,1,2$
converges element-wise, thereby ensuring the existence of some
$N'\geq N^*$
such that (22) holds for the convergent sequence
\[
{{\cal K}}'={ \{{{\textbf{\textit{k}}^{({i})}}} \colon {i\in{\mathbb{Z}_{_+}},\,{\textbf{\textit{k}}^{({i})}}={\textbf{\textit{k}}^{({N'})}}\ \text{for }i\geq N'}\}}.
\]
Then, from Assumption 1 and the convergence of sequence
${{\cal K}}'$
, we obtain the inequality (21) over the sequence
${{\cal K}}'$
whenever
$i\ge N''$
, for some
$N''>N'$
. This, together with the fact that (22) holds over
${{\cal K}}'$
shows that
${\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\le{\textbf{0}}$
must likewise hold over
${{\cal K}}'$
for sufficiently large i. By Lemmas 1 and 2, it must be the case that
${D^{({i})}}\le 0$
for all such i. This completes the proof of part (i).
Part (ii): positive recurrence. The assertion of part (ii) follows directly from the proof of part (i) by invoking Theorem 2.2.3 of [Reference Fayolle, Malyshev and Menshikov16] in place of Theorem 2.2.1 of the same reference.
4. Connections to level-independent QBD processes
In this section we draw parallels between established drift conditions for level-independent QBD processes and conditions derived in Section 3. In Proposition 2 we establish the existence of the limiting drift D * and show that it can be computed in a manner that is analogous to computing the average drift of its level-independent counterpart.
Proposition 2. Suppose that the assumptions of Theorem 3 hold for the discrete-time process
$\Phi$
. Then the limiting drift D* exists and is given by
\[
D^*\,{:\!=}\,\lim_{i\to\infty}{D^{({i})}}={\boldsymbol{\pi}^*}{ ({A_0^*-A_2^*})}\textbf{\textit{e}},
\]
where
${\boldsymbol{\pi}^*}$
is the unique solution to the system of equations
\begin{equation}
\textbf{\textit{x}} A^*=\textbf{\textit{x}} \quad\mbox{and}\quad \textbf{\textit{x}}\textbf{\textit{e}}=1,
\label{eqn23}
\end{equation}
$A^* = A_2^*+ A_1^*+ A_0^*$
, and the matrices
$A_j^*$
,
$j=0,1,2$
are defined in Assumption 1.
Proof. First we establish that the K-dimensional vector
${\boldsymbol{\pi}^*}\,{:\!=}\,\lim {\bpi^{({i})}}$
is a solution to (23). For each
$i\in {\mathbb{N}}$
,
${\bpi^{({i})}}{A^{({i})}}={\bpi^{({i})}}$
and
${\bpi^{({i})}}\textbf{\textit{e}} =1$
; therefore,
\begin{equation}
\lim_{i\to \infty}{\bpi^{({i})}}{A^{({i})}}=\lim_{i\to \infty}{\bpi^{({i})}}={\boldsymbol{\pi}^*}\quad\mbox{and}\quad 1=\lim_{i\to\infty}{\bpi^{({i})}}\textbf{\textit{e}}={\boldsymbol{\pi}^*} \textbf{\textit{e}}.
\label{eqn24}
\end{equation}
Next we show that
${\bpi^{({i})}}{A^{({i})}} \to {\boldsymbol{\pi}^*} A^*$
as
$i\to \infty$
. For each phase
$j\in {{\cal P}}$
,
\begin{align*}
\lim_{i\to \infty} [{\bpi^{({i})}}{A^{({i})}}]_j=\lim_{i\to \infty} \sum_{m\in {{\cal P}}}{\bpi^{({i})}_m}{A^{({i})}_{m,j}}=\sum_{m\in {{\cal P}}}\lim_{i\to \infty} {\bpi^{({i})}_m}{A^{({i})}_{m,j}}
&= \sum_{m\in {{\cal P}}}({\boldsymbol{\pi}^*_m}) (A^*_{m,j})
= [{\boldsymbol{\pi}^*} A^*]_j.
\end{align*}
As the left- and right-hand sides are equal for every j, it follows that
\begin{equation}
\lim_{i\to \infty}{\bpi^{({i})}}{A^{({i})}}={\boldsymbol{\pi}^*} A^*.
\label{eqn25}
\end{equation}
By equations (24) and (25),
${\boldsymbol{\pi}^*} A^*={\boldsymbol{\pi}^*}$
and
${\boldsymbol{\pi}^*} \textbf{\textit{e}}=1$
. To see that
${\boldsymbol{\pi}^*}$
is the unique solution to (23), note that
\[
\textbf{\textit{e}}=\lim_{i\to\infty}{A^{({i})}}\textbf{\textit{e}}= \Big(\lim_{i\to\infty}{A^{({i})}}\Big)\textbf{\textit{e}}=A^*\textbf{\textit{e}},
\]
demonstrating that A * is stochastic. The irreducibility and finite-dimensionality of A *, along with (24) and (25), prove that
${\boldsymbol{\pi}^*}$
uniquely solves (23). Finally, the existence of
${\boldsymbol{\pi}^*}$
, along with Assumption 1, establish the existence of
\begin{align*}
D^*=\lim_{i\to\infty}{\bpi^{({i})}} ({A_{0}^{{(i)}}}-{A_{2}^{{(i)}}})\textbf{\textit{e}} &= \Big(\lim_{i\to\infty}{\bpi^{({i})}}\Big) \Big(\lim_{i\to\infty} ({A_{0}^{{(i)}}}-{A_{2}^{{(i)}}})\textbf{\textit{e}}\Big)
={\boldsymbol{\pi}^*} (A^*_0-A^*_2)\textbf{\textit{e}},
\end{align*}
and the proof is complete.
For the embedded DTMC of irreducible, level-independent QBD processes in which
$A_0$
,
$A_1$
, and
$A_2$
are constant matrices over the levels i, it is well known that the average drift of the process is
\[
D =\bpi(A_0-A_2)\textbf{\textit{e}},
\]
where
$\bpi$
is the unique solution of the system of equations
$\bpi(A_0+A_1+A_2)=\bpi$
and
$\bpi \textbf{\textit{e}}=1$
. Furthermore, it can be shown that the process is positive recurrent if and only if
$D<0$
, null recurrent if and only if
$D=0$
, and transient if
$D>0$
(see [Reference Latouche and Ramaswami24] and [Reference Neuts38]). Proposition 3 asserts that similar conditions can be stated for the level-dependent process
$\Phi$
considered herein.
Proposition 3. Suppose the assumptions of Theorem 3 hold. Then the discrete-time LDQBD process
$\Phi$
is
(i) recurrent if and only if
$D^*\le 0$
and
${D^{({i})}}>0$
for at most finitely many i,(ii) positive recurrent if and only if
$D^*<0$
,(iii) null recurrent if and only if
$D^*=0$
and
${D^{({i})}}>0$
for at most finitely many i,(iv) transient if and only if
$D^*\ge 0$
and
${D^{({i})}}>0$
for infinitely many i.
Proof. For part (i), suppose first that
$D^*\le 0$
and
${D^{({i})}}>0$
for at most a finite number of terms i. Then there must be some
$N>0$
such that the terms
${D^{({i})}}\le 0$
for every
$i\geq N$
, by existence of
$D^*=\lim_{i\to\infty}{D^{({i})}}$
. Thus, there is a finite number
$\epsilon=\inf_{i\geq N}{ ({-{D^{({i})}}})}\ge 0$
. So by Lemmas 1 and 2, there is a sequence
${{\cal K}}={ \{{{\textbf{\textit{k}}^{({i})}}\in{\mathbb{R}_{_+}^K}} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
such that
\begin{equation} %%\label{eq:hdrift_cor}
{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\leq-\epsilon\quad\mbox{for $i\ge N$}.
\end{equation}
It was shown in the proof of Theorem 3 that
${{\cal K}}$
is convergent and, furthermore, that there exists an
$N^*>N$
such that
\[
{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}\le -\epsilon,\quad i\geq N^*,
\]
thus establishing the recurrence of
$\Phi$
. Conversely, if
$\Phi$
is recurrent, then by Theorem 3, there exists an
$\epsilon
\ge 0$
and
$N>0$
such that
${D^{({i})}}\le-\epsilon$
for all
$i\ge N$
. As
${D^{({i})}}\to D^*$
, the limit point must satisfy
$D^*\le-\epsilon$
, which completes the proof of part (i).
For part (ii), assuming the strict inequality
$D^*<0$
implies the existence of some
$N>0$
such that the terms
${D^{({i})}}<0$
for every
$i>N$
. This further implies the existence of a finite number
$\epsilon=\inf_{i\geq N}
{ ({-{D^{({i})}}})}>0$
. By Lemma 2, we then obtain a sequence
${{\cal K}}=
{ \{{{\textbf{\textit{k}}^{({i})}}\in{\mathbb{R}_{_+}^K}} \colon {i\in{\mathbb{Z}_{_+}}}\}}$
such that
\[
{\Gamma^{(i)}}({\textbf{\textit{k}}^{({i})}})\leq-\epsilon<0\quad \text{for } i\geq N.
\]
As in the proof of part (i), we may then infer the existence of an
$N^*>N$
such that
\[
{{\Lambda^{(i)}}({\textbf{\textit{k}}^{({i})}})}\le -\epsilon<0,\quad i\geq N^*,
\]
which establishes the positive recurrence of
$\Phi$
. On the other hand, if
$\Phi$
is positive recurrent, then Theorem 3 gives the existence of an
$\epsilon>0$
and
$N>0$
such that
${D^{({i})}}\le-\epsilon<0$
for all
$i\ge N$
. As
${D^{({i})}}\to D^*$
, the limit point must satisfy
$D^*\le-\epsilon<0$
, which completes the proof of part (ii).
Part (iii) follows immediately from parts (i) and (ii), since the region of null recurrence indicated by D * must be the complement of the set
${ \{{D^*\in{\mathbb{R}}} \colon {D^*<0}\}}$
within the indicated region of recurrence.
Finally, part (iv) follows from part (i) due to the fact that the regions of transience and recurrence must be complementary.
5. Conclusion
In this paper, we have provided both necessary and sufficient conditions for the recurrence and positive recurrence of a class of LDQBD processes that exhibit convergence in the rows by employing a Foster–Lyapunov approach. For such processes, a limiting drift term D * was shown to exist, and this term provides an analytical means by which to characterize the recurrence properties of the process. The parallels to the level-independent QBD process are apparent, namely that a negative average drift is necessary and sufficient to ensure positive recurrence. The analysis contained herein provides a simpler means by which to perform stability analysis for broad classes of queueing models with non-standard input and output processes.
Theorem 4. (Farkas’s lemma) Let
$M\in {\mathbb{R}}^{m\times n}$
be an
$m\times n$
matrix and
$\textbf{\textit{b}}\in {\mathbb{R}}^m$
a column vector of dimension m. Then exactly one of the statements (i) or (ii) is true.
(i) There exists some
$\textbf{\textit{x}}\in {\mathbb{R}}^n$
with
$\textbf{\textit{x}}\ge {\textbf{0}}$
such that
$M\textbf{\textit{x}} = \textbf{\textit{b}}$
.(ii) There exists some
$\textbf{\textit{y}}\in {\mathbb{R}}^m$
such that
$\textbf{\textit{y}}'M\ge {\textbf{0}}$
and
$\textbf{\textit{y}}'\textbf{\textit{b}}<0$
.
Theorem 5. (Gordan’s theorem) Let
$M\in {\mathbb{R}}^{m\times n}$
be an
$m\times n$
matrix. Then exactly one of the statements (i) or (ii) is true.
(i) There exists some
$\textbf{\textit{x}}\in {\mathbb{R}}^n$
with
$\textbf{\textit{x}}\ge {\textbf{0}}$
and
$\textbf{\textit{x}}\ne {\textbf{0}}$
such that
$M\textbf{\textit{x}} = {\textbf{0}}$
.(ii) There exists some
$\textbf{\textit{y}}\in {\mathbb{R}}^m$
such that
$\textbf{\textit{y}}'M> {\textbf{0}}$
.
Proposition 4. For
$n\in {\mathbb{N}}$
, let
${ \{{M_i}\}}$
be a sequence of elements in
${\mathbb{R}}^{n\times n}$
that converges element-wise to an invertible limit
$M_*$
. Then
\[
\lim_{i\to\infty}M_i^{-1}=M_*^{-1}.
\]
Proof. From rudimentary linear algebra, it is known that diagonalizable invertible matrices
$M_i$
may be expressed in terms of the decompositions
$M_i=P_iD_iP_i^{-1}$
, where
$D_i$
is a diagonal matrix whose non-zero entries are the (possibly repeated) real and complex eigenvalues of
$M_i$
, and is unique up to ordering of the eigenvalues. Otherwise, if
$M_i$
is not diagonalizable, then one may still decompose the matrix as
$M_i=P_iJ_iP_i^{-1}$
, where
$J_i$
is the corresponding Jordan canonical form (JCF) of
$M_i$
. Likewise, one may also write
$M_*=P_*D_*P_*^{-1}$
or
$M_*=P_*J_*P_*^{-1}$
, where
$D_*$
is a diagonal matrix and
$J_*$
is a JCF, depending upon whether or not
$M_*$
is diagonalizable.
For the special case in which each
$M_i=P_iD_iP_i^{-1}$
is a diagonalizable matrix, the fact that
$M_i\to M_*$
, together with the uniqueness of the diagonal decomposition and the invertibility of
$P_i$
, guarantees the convergence
$P_i\to P_*$
,
$P_i^{-1}\to P_*^{-1}$
, and hence
$D_i\to D_*$
. This shows that
$M_*$
must likewise be diagonalizable. Setting
\[
D_i\,{:\!=}\,{\mathrm{diag} ({{\lambda}_{i1},{\lambda}_{i2},\ldots,{\lambda}_{in}})},\quad D_*={\mathrm{diag} ({{\lambda}_{*1},{\lambda}_{*2},\ldots,{\lambda}_{*n}})},
\]
we see that
${\lambda}_{ik}\to{\lambda}_{*k}$
must hold for each
$k=1,\ldots, n$
. Consequently, we must also have
$1/{\lambda}_{ik}\to 1/{\lambda}_{*k}$
for each k, which proves that
$D_i^{-1}\to D_*^{-1}$
, and thus
$M_i^{-1}\to M_*^{-1}$
.
For the case in which each
$M_i$
is non-diagonalizable, we may express each
$J_i$
for large enough i as
$J_i={\mathrm{diag} ({J_{i1},J_{i2},\ldots,J_{ir}})}$
and
$J_*={\mathrm{diag} ({J_{*1},J_{*2},\ldots,J_{*r}})}$
for some
$r\ge 1$
. For a fixed
$k\in{\mathbb{Z}_{_+}}$
and complex eigenvalues
${\lambda}_{ik}$
and
${\lambda}_{*k}$
, the corresponding block entries
$J_{ik}$
and
$J_{*k}$
, both of which are of the dimension
$n_k\times n_k$
, appear in the form
\[
J_{ik}=\begin{bmatrix}
{\lambda}_{ik} & 1 \\
& {\lambda}_{ik} & 1 \\
& & \ddots & \ddots \\
& & & {\lambda}_{ik} & 1 \\
\end{bmatrix},\quad
J_{*k}=\begin{bmatrix}
{\lambda}_{*k} & 1 \\
& {\lambda}_{*k} & 1 \\
& & \ddots & \ddots \\
& & & {\lambda}_{*k} & 1 \\
\end{bmatrix}.
\]
The dimensions of these matrices must obey the relation
$n=\sum_{k=1}^r n_k$
. By the uniqueness of the JCF decomposition (up to ordering of the eigenvalues in the JCF matrix), together with the invertibility of
$P_i$
, the convergence
$M_i\to M_*$
implies that
$P_i\to P_*$
,
$P_i^{-1}\to P_*^{-1}$
, and thus
$J_i\to J_*$
. In particular,
$J_{ik}\to J_{*k}$
implies that
${\lambda}_{ik}\to{\lambda}_{*k}$
for each
$k=1,\ldots, r$
.
We will now show that
$M_i^{-1}\to M_*^{-1}$
, where
\[
M_i^{-1}=P_i^{-1}J_i^{-1}P_i\quad\text{and}\quad M_*^{-1}= P_*^{-1}J_*^{-1}P_*.
\]
Based on the properties of JCF decompositions, it is sufficient to demonstrate the convergence
$J_i^{-1}\to J_*^{-1}$
. In order to do this, we will consider
$J_i$
for large i. Since
\[
J_i^{-1}={\mathrm{diag} ({J_{i1}^{-1},J_{i2}^{-1},\ldots,J_{ir}^{-1}})},
\]
we will choose an arbitrary fixed k and note that
\[
J_{ik}^{-1}=
\begin{bmatrix}
\mu_{ik} & \mu_{ik}^2 & \mu_{ik}^3 & \dots & \mu_{ik}^{n_k} \\[3pt]
& \mu_{ik} & \mu_{ik}^2 & \dots & \mu_{ik}^{n_k-1}\\[3pt]
& & \mu_{ik} & \dots & \mu_{ik}^{n_k-2}\\[2pt]
& & & \ddots & \vdots \\[2pt]
& & & & \mu_{ik}
\end{bmatrix},
\quad \mu_{ik}=1/{\lambda}_{ik}.
\]
Due to the triangular shape of the matrix, it is possible to find some nilpotent matrix
$N_{ik}$
such that
$N_{ik}^{n_k+1}={\textbf{0}}$
for some
$n_k\ge 1$
, and for which
\begin{equation}
J_{ik}^{-1}=I-\mu_{ik}N_{ik}+\mu_{ik}^2N_{ik}^2-\dots\pm\mu_{ik}^{n_k}N_{ik}^{n_k}=\mu_{ik}{ ({I+\mu_{ik}N_{ik}})}^{-1}.
\label{eqn26}
\end{equation}
Applying the convergence
${\lambda}_{ik}\to{\lambda}_{*k}$
to (26) then gives
$\mu_{ik}\to\mu_{*k}=1/{\lambda}_{*k}$
, which in turn produces
$J_{ik}^{-1}\to J_{*k}^{-1}$
for each
$k=1,\ldots,r$
. Consequently,
$J_i^{-1}\to J_*^{-1}$
and
\[
M_*^{-1}=P_*^{-1}J_*^{-1}P_*=\lim_{i\to\infty}P_i^{-1}J_i^{-1}P_i,
\]
and the proof is complete.
Lemma 3. Suppose that Assumption 1 holds. Then
\[
\lim_{i\to\infty}{ (T^{({i})})^{\#}} = {{{ ({T^*})}}^{\#}},
\]
where
${T^{({i})}}=I-{A^{({i})}}$
,
$T^*=\lim_{i\to\infty}{T^{({i})}}$
and B # denotes the generalized inverse of a matrix
$B\in{\mathbb{R}}^{K\times K}$
defined in [Reference Meyer31].
Proof. To prove the assertion, we will appeal to the Jordan canonical forms (JCF) of the operator T (i) and its group inverse (T (i))#. The irreducibility of A (i) for every i allows us to invoke Corollary 2.1 of [Reference Meyer31], which states that
\[
{T^{({i})}} = { ({{S^{({i})}}})}^{-1}{\left({
\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & I-U^{(i)}
\end{array}}\right)}{S^{({i})}},\quad
{ (T^{({i})})^{\#}} = { ({{S^{({i})}}})}^{-1}{\left({
\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & { ({I-U^{(i)}})}^{-1}
\end{array}}\right)}{S^{({i})}},
\]
where
${S^{({i})}}\in{\mathbb{R}}^{K\times K}$
and
$U^{(i)}\in{\mathbb{R}}^{(K-1)\times (K-1)}$
are invertible matrices. By Assumption 1, we know that
$T^*=I-A^*=\lim_{i\to\infty}I-{A^{({i})}}$
exists. Thus, from the same result, we obtain the JCF decompositions
\begin{equation}
T^* = { ({S^*})}^{-1}{\left({
\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & I-U^*
\end{array}}\right)}S^*,\quad
{{{ ({T^*})}}^{\#}} = { ({S^*})}^{-1}{\left({
\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & { ({I-U^*})}^{-1}
\end{array}}\right)}S^*,
\end{equation}
where
$S^*\in{\mathbb{R}}^{K\times K}$
and
$U^*\in{\mathbb{R}}^{(K-1)\times (K-1)}$
are invertible matrices. It is well known that the JCF decomposition is unique up to ordering of the distinct eigenvalues, as explained in the proof of Proposition 4. We will assume that the eigenvalues in each
$I-U^{(i)}$
are ordered in such a way that the element-wise convergence
${ ({I-U^{(i)}})}\to{ ({I-U^*})}$
makes sense, should it occur.
For notational brevity, we will label the following JCFs as
\[
J^{(i)}\,{:\!=}\,{\left({
\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & I-U^{(i)}
\end{array}}\right)}\quad\mbox{and}\quad
J^*\,{:\!=}\,{\left({
\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & I-U^*
\end{array}}\right)}.
\]
The known convergence of
${T^{({i})}}={S^{({i})}}J^{(i)}{ ({{S^{({i})}}})}^{-1}\to T^*$
, together with the invertibility of S
(i) and the uniqueness of the JCF decomposition, allows us to assert the convergence of
${S^{({i})}}\to S^*$
,
$U^{(i)}\to U^*$
,
$J^{(i)}\to J^*$
, and
${ ({{S^{({i})}}})}^{-1}\to{ ({S^*})}^{-1}$
. The convergence
$U^{(i)}\to U^*$
further implies that
$J^{(i)}\to J^*$
. In summary, we obtain the convergence of {T
(i)} to the limiting JCF decomposition
\begin{equation}
T^*= \lim_{i\to\infty}{T^{({i})}}
= \lim_{i\to\infty}{ ({{S^{({i})}}})}^{-1}J^{(i)}{S^{({i})}}
= { ({S^*})}^{-1}J^*S^*.
\label{eqn27}
\end{equation}
We may now apply the convergence
${S^{({i})}}\to S^*$
,
$U^{(i)}\to
U^*$
,
$J^{(i)}\to J^*$
, and
${ ({{S^{({i})}}})}^{-1}\to{ ({S^*})}^{-1}$
, which were determined in the course of formulating (27), to the sequence
${ \{{{ (T^{({i})})^{\#}}}\}}$
in order to obtain
\[
\lim_{i\to\infty}{ (T^{({i})})^{\#}} = { ({S^*})}^{-1}
{\left({\begin{array}{c|c}
0 & {\textbf{0}} \\\hline
{\textbf{0}} & (I-U^*)^{-1}
\end{array}}\right)}S^*
={{{ ({T^*})}}^{\#}},
\]
where
${ \{{{ ({I-U^{(i)}})}^{-1}}\}}\to{ ({I-U^*})}^{-1}$
results from Proposition 4.
Acknowledgements
The authors are grateful to an anonymous referee for valuable comments that have improved the results of this work. This research was sponsored in part by a grant from the US Air Force Office of Scientific Research (FA9550-08-1-0004). The views expressed in this paper are those of the authors and do not reflect the official policy or position of the US Air Force, Department of Defense, or the US Government.
