2.1. Preliminaries

We will construct a convex polytope $\mathcal{P}$ , by considering the intersection of a polyhedral convex cone $\mathcal{C}$ on the first orthant $\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} \geq \textbf{0}\}$ of $\mathbb{R}^{N+1}$ and a hyperplane containing all probability vectors in $\mathbb{R}^{N+1}$ . As we will see, $\mathcal{C}$ and $\mathcal{P}$ take the following forms:

(2.1) \begin{align}\mathcal{C}&=\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}\textbf{\textit{A}} \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{B}} = \textbf{0}\},\nonumber\\[3pt] \mathcal{P}&=\mathcal{C} \cap \{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}\textbf{\textit{e}} =1 \}=\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}\textbf{\textit{A}} \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{B}} = \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} =1\},\end{align}

where $\textbf{\textit{A}}$ and $\textbf{\textit{B}}$ denote appropriate matrices with $N+1$ rows. Note that we allow $\textbf{\textit{B}} = \textbf{\textit{O}}$ , and in that case, we can ignore the constraint $\textbf{\textit{x}}\textbf{\textit{B}} = \textbf{0}$ in (2.1). In general, a convex polytope $\mathcal{P}$ can also be represented by a set of convex combinations of vertices of $\mathcal{P}$ . Specifically, by using an appropriate nonnegative matrix $\overline{\textbf{\textit{C}}}$ with $N+1$ columns such that $\overline{\textbf{\textit{C}}}\textbf{\textit{e}}=\textbf{\textit{e}}$ , $\mathcal{P}$ in (2.1) can also be represented as

\begin{align*}\mathcal{P}&=\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}=\boldsymbol{\alpha}\overline{\textbf{\textit{C}}},\boldsymbol{\alpha} \geq \textbf{0},\boldsymbol{\alpha}\textbf{\textit{e}} =1\}.\end{align*}

Note that $\overline{\textbf{\textit{C}}}$ is composed of $1 \times (N+1)$ probability vectors $\overline{\textbf{\textit{c}}}_i$ ( $i=0,1,\ldots,M$ ) that span $\mathcal{P}$ . If the M vectors $\overline{\textbf{\textit{c}}}_1 - \overline{\textbf{\textit{c}}}_0$ , $\overline{\textbf{\textit{c}}}_2-\overline{\textbf{\textit{c}}}_0$ , $\ldots$ , $\overline{\textbf{\textit{c}}}_M-\overline{\textbf{\textit{c}}}_0$ are linearly independent, $\mathcal{P}$ is called an M-simplex. Let $\textrm{ri}\, \mathcal{P}$ denote the relative interior of the convex polytope $\mathcal{P}$ :

(2.2) \begin{align}\textrm{ri}\, \mathcal{P}&=\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} \textbf{\textit{A}} > \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{B}}=\textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}}=1\}\\[3pt] &= \{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} = \boldsymbol{\alpha}\overline{\textbf{\textit{C}}},\boldsymbol{\alpha} > \textbf{0},\ \boldsymbol{\alpha}\textbf{\textit{e}}=1\}.\nonumber\end{align}

2.2. Characterization of $\boldsymbol{\pi}(N)$ in terms of $\textbf{\textit{Q}}^{(1,1)}(N)$

In this subsection, we assume that for an arbitrarily fixed $N \in\mathbb{Z}^+$ , the stationary distribution $\boldsymbol{\pi}$ of an ergodic, continuous-time Markov chain $\{X(t)\}_{t \in (\!-\infty,\infty)}$ is partitioned as in (1.2) and the infinitesimal generator $\textbf{\textit{Q}}$ is partitioned as follows:

(2.3) \begin{equation}\textbf{\textit{Q}} = \kbordermatrix{&\mathbb{Z}_0^N &\quad \mathbb{Z}_{N+1}^{\infty}\\ \\[-5pt] \mathbb{Z}_0^N & \textbf{\textit{Q}}^{(1,1)}(N) &\quad \textbf{\textit{Q}}^{(1,2)}(N) \\ \\[-5pt] \mathbb{Z}_{N+1}^{\infty} & \textbf{\textit{Q}}^{(2,1)}(N) &\quad \textbf{\textit{Q}}^{(2,2)}(N)}.\end{equation}

We define $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ as the collection of ergodic, continuous-time Markov chains on $\mathbb{Z}^+$ whose infinitesimal generators have the specific $(N+1) \times (N+1)$ northwest corner block $\textbf{\textit{Q}}^{(1,1)}(N)$ .

We first characterize the conditional stationary distribution $\boldsymbol{\pi}(N)$ of Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ . Owing to the ergodicity, $\textbf{\textit{Q}}^{(1,1)}(N)$ is nonsingular whether it is irreducible or not. We then define $\textbf{\textit{H}}(N)$ as

(2.4) \begin{align}\textbf{\textit{H}}(N)&=(\!-\textbf{\textit{Q}}^{(1,1)}(N))^{-1}.\end{align}

By definition, $\textbf{\textit{H}}(N) \geq \textbf{\textit{O}}$ and $\textbf{\textit{H}}(N) \textbf{\textit{e}} >\textbf{0}$ . Let $\overline{\textbf{\textit{H}}}(N)$ denote an $(N+1) \times (N+1)$ matrix obtained by normalizing each row of $\textbf{\textit{H}}(N)$ in such a way that $\overline{\textbf{\textit{H}}}(N) \textbf{\textit{e}} = \textbf{\textit{e}}$ :

\begin{equation*}\overline{\textbf{\textit{H}}}(N)=\textrm{diag}^{-1}(\textbf{\textit{H}}(N)\textbf{\textit{e}})\textbf{\textit{H}}(N),\end{equation*}

where for any $(n+1)$ -dimensional vector $\textbf{\textit{x}}$ , $\textrm{diag}(\textbf{\textit{x}})$ denotes an $(n+1)$ -dimensional diagonal matrix whose ith diagonal element is given by the ith element $[\textbf{\textit{x}}]_i$ of $\textbf{\textit{x}}$ . We also define $\Gamma(n)$ ( $n \in \mathbb{Z}^+$ ) as the set of all $(n+1)$ -dimensional probability vectors:

(2.5) \begin{align}\Gamma(n)&=\{\boldsymbol{\alpha} \in \mathbb{R}^{n+1};\quad \boldsymbol{\alpha}\geq\textbf{0},\boldsymbol{\alpha}\textbf{\textit{e}}=1\},\quad n \in \mathbb{Z}^+.\end{align}

Theorem 2.1. For any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ , we have

(2.6) \begin{align}\boldsymbol{\pi}(N) \in \mathcal{P}(N),\quad N \in \mathbb{Z}^+,\end{align}

where $\mathcal{P}(N)$ $(N \in \mathbb{Z}^+)$ denotes an N-simplex on the first orthant of $\mathbb{R}^{N+1}$ which is given by

(2.7) \begin{align}\mathcal{P}(N)&=\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N)) \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\}\end{align}

(2.8) \begin{align}&=\big\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}=\boldsymbol{\alpha} \overline{\textbf{\textit{H}}}(N),\boldsymbol{\alpha} \in \Gamma(N)\big\}.\end{align}

Proof. The starting point of the proof is the global balance equations (1.1) for $\boldsymbol{\pi}^{(1)}(N)$ :

(2.9) \begin{equation}\boldsymbol{\pi}^{(1)}(N) \textbf{\textit{Q}}^{(1,1)}(N)+\boldsymbol{\pi}^{(2)}(N) \textbf{\textit{Q}}^{(2,1)}(N)=\textbf{0}.\end{equation}

It then follows from (1.3) and (2.9) that

(2.10) \begin{align}\boldsymbol{\pi}(N) (\!-\textbf{\textit{Q}}^{(1,1)}(N))=\frac{\boldsymbol{\pi}^{(2)}(N)}{\boldsymbol{\pi}^{(1)}(N)\textbf{\textit{e}}}\cdot\textbf{\textit{Q}}^{(2,1)}(N).\end{align}

Because $\boldsymbol{\pi}^{(2)}(N)/\boldsymbol{\pi}^{(1)}(N)\textbf{\textit{e}}>\textbf{0}$ and $\textbf{\textit{Q}}^{(2,1)}(N) \geq \textbf{\textit{O}}$ , $\boldsymbol{\pi}(N)$ satisfies

\begin{equation*}\boldsymbol{\pi}(N)(\!-\textbf{\textit{Q}}^{(1,1)}(N)) \geq \textbf{0},\qquad\boldsymbol{\pi}(N)\textbf{\textit{e}} = 1,\end{equation*}

from which (2.6) with (2.7) follows.

Next, we show the equivalence between (2.7) and (2.8). We rewrite (2.7) as

\begin{align*}&\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N)) \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\}\\&\quad =\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N)) = \textbf{\textit{y}},\ \textbf{\textit{y}} \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\}\\&\quad =\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} = \textbf{\textit{y}} \textbf{\textit{H}}(N),\ \textbf{\textit{y}} \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\}\\&\quad =\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} = \textbf{\textit{y}} \textrm{diag}(\textbf{\textit{H}}(N) \textbf{\textit{e}}) \overline{\textbf{\textit{H}}}(N),\ \textbf{\textit{y}} \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\}.\end{align*}

Let $\boldsymbol{\alpha} = \textbf{\textit{y}} \textrm{diag}(\textbf{\textit{H}}(N)\textbf{\textit{e}})$ . Since $\textbf{\textit{x}} =\boldsymbol{\alpha} \overline{\textbf{\textit{H}}}(N)$ , we have $\textbf{\textit{x}}\textbf{\textit{e}} = \boldsymbol{\alpha}\textbf{\textit{e}}$ . Furthermore, if $\textbf{\textit{y}} \geq \textbf{0}$ , we have $\boldsymbol{\alpha} =\textbf{\textit{y}} \textrm{diag}(\textbf{\textit{H}}(N) \textbf{\textit{e}}) \geq \textbf{0}$ and vice versa, since $\textbf{\textit{H}}(N)\textbf{\textit{e}} > \textbf{0}$ . We thus have

(2.11) \begin{align}&\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} = \textbf{\textit{y}} \textrm{diag}(\textbf{\textit{H}}(N) \textbf{\textit{e}}) \overline{\textbf{\textit{H}}}(N),\ \textbf{\textit{y}} \geq \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\}\nonumber\\&\quad =\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} = \boldsymbol{\alpha} \overline{\textbf{\textit{H}}}(N),\boldsymbol{\alpha} \geq \textbf{0},\ \boldsymbol{\alpha}\textbf{\textit{e}} = 1\}.\end{align}

Because $\overline{\textbf{\textit{H}}}(N)$ is composed of $N+1$ linearly independent probability vectors, $\mathcal{P}(N)$ is an N-simplex on the first orthant of $\mathbb{R}^{N+1}$ . □

Theorem 2.1 implies that the conditional stationary distribution $\boldsymbol{\pi}(N)$ of any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ is given by a convex combination of row vectors of $\overline{\textbf{\textit{H}}}(N)$ ; i.e., there exists $\boldsymbol{\alpha}^*(N)$ such that

(2.12) \begin{equation}\boldsymbol{\pi}(N) = \boldsymbol{\alpha}^*(N) \overline{\textbf{\textit{H}}}(N),\quad\boldsymbol{\alpha}^*(N) \in \Gamma(N).\end{equation}

The following corollary can be used to evaluate the accuracy of an approximation to $\boldsymbol{\pi}(N)$ .

Corollary 2.1. For an arbitrary probability vector $\textbf{\textit{x}} \in \Gamma(N)$ , we have

(2.13) \begin{equation}\| \textbf{\textit{x}} - \boldsymbol{\pi}(N) \|_1\leq\max_{i \in \mathbb{Z}_0^N}\| \textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i(N) \|_1,\end{equation}

where $\| \cdot \|_1$ stands for the $\ell_1$ norm and $\overline{\textbf{\textit{h}}}_i(N)$ ( $i \in \mathbb{Z}_0^N$ ) denotes the ith row vector of $\overline{\textbf{\textit{H}}}(N)$ . Furthermore, if $\textbf{\textit{x}} \in \mathcal{P}(N)$ , we have

(2.14) \begin{equation}\max_{i \in \mathbb{Z}_0^N}\| \textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i(N) \|_1\leq\max_{i,j \in \mathbb{Z}_0^N}\| \overline{\textbf{\textit{h}}}_j(N) - \overline{\textbf{\textit{h}}}_i(N) \|_1,\quad\textbf{\textit{x}} \in \mathcal{P}(N).\end{equation}

Proof. (2.13) immediately follows from Theorem 2.1 and the convexity of $\mathcal{P}(N)$ . Furthermore, if $\textbf{\textit{x}} \in \mathcal{P}(N)$ , there exists a probability vector $\boldsymbol{\beta}=(\beta_0\ \beta_1\ \cdots\ \beta_N) \in \Gamma(N)$ such that

\begin{equation*}\|\textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i(N) \|_1=\|\sum_{j \in \mathbb{Z}_0^N} \beta_j\bigl( \overline{\textbf{\textit{h}}}_j(N) - \overline{\textbf{\textit{h}}}_i(N) \bigr) \|_1\leq\sum_{j \in \mathbb{Z}_0^N} \beta_j\| \overline{\textbf{\textit{h}}}_j(N) - \overline{\textbf{\textit{h}}}_i(N) \|_1,\end{equation*}

from which (2.14) follows. □

We now provide a probabilistic interpretation of (2.12). We partition the state space $\mathbb{Z}^+$ into $\mathbb{Z}_0^N$ and $\mathbb{Z}_{N+1}^{\infty}$ and regard $\{X(t)\}_{t \in (\!-\infty,\infty)}$ as an alternating Markov renewal process. For an integer n, let $T_n^{(1)}$ (resp. $T_n^{(2)}$ ) denote the nth time instant at which $\{X(t)\}_{t \in (\!-\infty,\infty)}$ enters into $\mathbb{Z}_0^N$ from $\mathbb{Z}_{N+1}^{\infty}$ (resp. into $\mathbb{Z}_{N+1}^{\infty}$ from $\mathbb{Z}_0^N$ ), where we assume $T_n^{(1)} < T_n^{(2)} < T_{n+1}^{(1)}$ without loss of generality. We define I(t) ( $t \in (\!-\infty, \infty)$ ) as the state at the last renewal epoch before time t, i.e.,

\begin{equation*}I(t)=\begin{cases}X(T_n^{(1)}),&T_n^{(1)} \leq t < T_n^{(2)},\\ X(T_n^{(2)}),&T_n^{(2)} \leq t < T_{n+1}^{(1)}.\end{cases}\end{equation*}

We then consider the joint process $\{(X(t),I(t))\}_{t \in (\!-\infty,\infty)}$ , which is assumed to be stationary.

Corollary 2.2. For any Markov chain $\{X(t)\}_{t \in (\!-\infty,\infty)}$ in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ , the (i,j)th $(i,j \in \mathbb{Z}_0^N)$ element of $\overline{\textbf{\textit{H}}}(N)$ is given by

(2.15) \begin{equation}[\overline{\textbf{\textit{H}}}(N)]_{i,j}=\mathbb{P}(X(0) = j\mid I(0) =i),\quad i,j \in \mathbb{Z}_0^N,\end{equation}

and the ith $(i \in \mathbb{Z}_0^N)$ element of $\boldsymbol{\alpha}^*(N)$ is given by

(2.16) \begin{equation}[\boldsymbol{\alpha}^*(N)]_i=\mathbb{P}(I(0) = i \mid X(0) \in \mathbb{Z}_0^N).\end{equation}

We thus interpret (2.12) as

(2.17) \begin{equation}[\boldsymbol{\pi}(N)]_j=\sum_{i \in \mathbb{Z}_0^N}\mathbb{P}(I(0) = i \mid X(0) \in \mathbb{Z}_0^N)\cdot\mathbb{P}(X(0) = j \mid I(0) =i),\quad j \in \mathbb{Z}_0^N.\end{equation}

The proof of Corollary 2.2 is given in Appendix A. Note that for a given $\textbf{\textit{Q}}^{(1,1)}(N)$ , $\mathcal{P}(N)$ in Theorem 2.1 may not be tight in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ . For example, $\mathcal{P}(N)$ may include $\textbf{\textit{x}} \in\mathbb{R}^{N+1}$ such that $[\textbf{\textit{x}}]_i = 0$ for some $i \in \mathbb{Z}_0^N$ , whereas $\boldsymbol{\pi}(N) > \textbf{0}$ since Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ are ergodic. In the next subsection, we eliminate redundancy in $\mathcal{P}(N)$ using the structural information $\mathcal{J}(N)$ in (1.4).

2.3. Characterization of $\boldsymbol{\pi}(\textbf{\textit{N}})$ in terms of $\textbf{\textit{Q}}^{(1,1)}(\textbf{\textit{N}})$ and $\mathcal{J}(\textbf{\textit{N}})$

For specific $\textbf{\textit{Q}}^{(1,1)}(N)$ and $\mathcal{J}(N)$ , we define $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N))$ as the collection of ergodic, continuous-time Markov chains on $\mathbb{Z}^+$ whose infinitesimal generators have $\textbf{\textit{Q}}^{(1,1)}(N)$ and $\mathcal{J}(N)$ . By definition,

\begin{equation*}\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))=\bigcup_{\mathcal{J}(N) \in 2^{\mathbb{Z}_0^N} \setminus \{\emptyset\}}\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N)).\end{equation*}

Note here that $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N))$ may be empty for some pairs of $\textbf{\textit{Q}}^{(1,1)}(N)$ and $\mathcal{J}(N)$ . For example, if $\textbf{\textit{Q}}^{(1,1)}(N)$ is a diagonal matrix, $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N),\mathcal{J}(N)) = \emptyset$ unless $\mathcal{J}(N) = \mathbb{Z}_0^N$ , owing to ergodicity. In the rest of this subsection, we assume that if $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N),\mathcal{J}(N)) \neq \emptyset$ , then $\mathcal{J}(N)=\{0,1,\dots,|\mathcal{J}(N)|-1\}$ without loss of generality.

If $\mathcal{J}(N) \neq \mathbb{Z}_0^N$ , we partition $\textbf{\textit{Q}}^{(1,1)}(N)$ and $\textbf{\textit{Q}}^{(2,1)}(N)$ in (2.3) into two matrices:

(2.18) \begin{align}\begin{pmatrix}\textbf{\textit{Q}}^{(1,1)}(N)\\ \\[-5pt] \textbf{\textit{Q}}^{(2,1)}(N)\end{pmatrix}=\kbordermatrix{& \mathcal{J}(N) & \mathbb{Z}_0^N \setminus \mathcal{J}(N)\\ \\[-5pt] \mathbb{Z}_0^N & \textbf{\textit{Q}}_+^{(1,1)}(N) &\quad \textbf{\textit{Q}}_0^{(1,1)}(N)\\ \\[-5pt] \mathbb{Z}_{N+1}^{\infty} & \textbf{\textit{Q}}_+^{(2,1)}(N) &\quad \textbf{\textit{O}}}.\end{align}

(2.10) is then rewritten as

(2.19) \begin{align}\boldsymbol{\pi}(N)\cdot\kbordermatrix{& \mathcal{J}(N) &\quad \mathbb{Z}_0^N \setminus \mathcal{J}(N)\\ \\[-5pt]& -\textbf{\textit{Q}}_+^{(1,1)}(N)&\quad -\textbf{\textit{Q}}_0^{(1,1)}(N)}=\kbordermatrix{& \mathcal{J}(N)&\quad \hbox to 7mm{\hss$\scriptstyle \mathbb{Z}_0^N \setminus \mathcal{J}(N)$\hss}\\ \\[-5pt]&\displaystyle\frac{\boldsymbol{\pi}^{(2)}(N)}{\boldsymbol{\pi}^{(1)}(N)\textbf{\textit{e}}} \cdot \textbf{\textit{Q}}_+^{(2,1)}(N)&\quad \textbf{0}}.\end{align}

We define $\Gamma^+(N)$ as

(2.20) \begin{equation}\Gamma^+(N)=\bigl\{\boldsymbol{\alpha} \in \mathbb{R}^{N+1};\ \boldsymbol{\alpha} \geq \textbf{0},\boldsymbol{\alpha}\textbf{\textit{e}}=1,\ [\boldsymbol{\alpha}]_i=0\ (i \in \mathbb{Z}_0^N\setminus\mathcal{J}(N))\bigr\}.\end{equation}

Theorem 2.2. Suppose $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N)) \neq \emptyset$ . For any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N))$ , we have

(2.21) \begin{align}\boldsymbol{\pi}(N) \in \textrm{ri}\, \mathcal{P}^+(N),\quad N \in \mathbb{Z}^+,\end{align}

where $\mathcal{P}^+(N)$ $(N \in \mathbb{Z}^+)$ denotes a $(|\mathcal{J}(N)|-1)$ -simplex on the first orthant of $\mathbb{R}^{N+1}$ which is given by $\mathcal{P}^+(N) = \mathcal{P}(N)$ if $\mathcal{J}(N) = \mathbb{Z}_0^N$ , and by

(2.22) \begin{align}\mathcal{P}^+(N)&=\big\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}(\!-\textbf{\textit{Q}}_+^{(1,1)}(N)) \geq \textbf{0},\ \textbf{\textit{x}}(\!-\textbf{\textit{Q}}_0^{(1,1)}(N)) = \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1\big\}\end{align}

(2.23) \begin{align}&\hspace*{-95pt}=\big\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}=\boldsymbol{\alpha}\overline{\textbf{\textit{H}}}(N),\boldsymbol{\alpha} \in \Gamma^+(N)\big\}\end{align}

otherwise.

Proof. If $\mathcal{J}(N)=\mathbb{Z}_0^N$ , we have $\boldsymbol{\pi}^{(2)}(N) \textbf{\textit{Q}}^{(2,1)}(N) >\textbf{0}$ since $\boldsymbol{\pi}^{(2)}(N) > \textbf{0}$ . Theorem 2.2 for $\mathcal{J}(N)=\mathbb{Z}_0^N$ then follows from (2.2), (2.10), and Theorem 2.1. On the other hand, if $\mathcal{J}(N) \neq \mathbb{Z}_0^N$ , then $\boldsymbol{\pi}^{(2)}(N) \textbf{\textit{Q}}_+^{(2,1)}(N) > \textbf{0}$ . In this case, (2.21) with (2.22) follows from (2.2) and (2.19). The equivalence between (2.22) and (2.23) for $\mathcal{J}(N) \neq \mathbb{Z}_0^N$ can be shown in a way similar to the proof of Theorem 2.1, as shown in Appendix B. Since $\overline{\textbf{\textit{H}}}(N)$ is nonnegative and nonsingular, $\mathcal{P}^+(N)$ is a $(|\mathcal{J}(N)|-1)$ -simplex on the first orthant of $\mathbb{R}^{N+1}$ . □

By definition, we have $\Gamma^+(N)\subseteq \Gamma(N)$ , and therefore

(2.24) \begin{equation}\mathcal{P}^+(N) \subseteq \mathcal{P}(N),\end{equation}

where $\mathcal{P}^+(N) = \mathcal{P}(N)$ iff $\mathcal{J}(N) = \mathbb{Z}_0^N$ . Theorem 2.2 indicates the importance of the structural information $\mathcal{J}(N)$ about direct transitions from $\mathbb{Z}_{N+1}^{\infty}$ to $\mathbb{Z}_0^N$ . For example, if $\mathcal{J}(N)$ is a singleton for a certain N, say, $\mathcal{J}(N)=\{i\}$ ( $i \in \mathbb{Z}_0^N$ ), $\boldsymbol{\pi}(N)$ is given by the ith row vector of $\overline{\textbf{\textit{H}}}(N)$ , as pointed out in [16, Corollary 3]. Numerical algorithms for block-structured Markov chains of level-dependent M/G/1-type in [Reference Kimura and Takine5, Reference Takine15] also utilize (2.21) with (2.22) implicitly.

The corollary below follows from Theorem 2.2; its proof is omitted because it is almost the same as that of Corollary 2.1.

Corollary 2.3. Suppose $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N)) \neq \emptyset$ . For an arbitrary probability vector $\textbf{\textit{x}} \in \Gamma(N)$ , we have

\begin{equation*}\| \textbf{\textit{x}} - \boldsymbol{\pi}(N) \|_1\leq\max_{i \in \mathcal{J}(N)}\| \textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i(N) \|_1.\end{equation*}

Furthermore, if $\textbf{\textit{x}} \in \mathcal{P}^+(N)$ , we have

\begin{equation*}\max_{i \in \mathcal{J}(N)}\| \textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i(N) \|_1\leq\max_{i,j \in \mathcal{J}(N)}\| \overline{\textbf{\textit{h}}}_j(N) - \overline{\textbf{\textit{h}}}_i(N) \|_1,\quad\textbf{\textit{x}} \in \mathcal{P}^+(N).\end{equation*}

Example 2.1. Consider an ergodic, level-dependent M ${}^{\text{X}}\!$ /M/1 queue with disasters, whose infinitesimal generator $\textbf{\textit{Q}}$ takes the following form:

\begin{equation}\textbf{\textit{Q}}=\left(\begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c@{\quad}c}-q_0 & q_{0,1} & q_{0,2} & q_{0,3} & q_{0,4} & q_{0,5} & \dots\\ \\[-7pt] q_{1,0} & -q_1 & q_{1,2} & q_{1,3} & q_{1,4} & q_{1,5} & \dots\\ \\[-7pt] q_{2,0} & q_{2,1} & -q_2 & q_{2,3} & q_{2,4} & q_{2,5} & \dots\\ \\[-7pt] q_{3,0} & 0 & q_{3,2} & -q_3 & q_{3,4} & q_{3,5} & \dots\\ \\[-7pt] q_{4,0} & 0 & 0 & q_{4,3} & -q_4 & q_{4,5} & \dots\\ \\[-7pt] q_{5,0} & 0 & 0 & 0 & q_{5,4} & -q_5 & \dots\\ \\[-7pt] \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots\end{array}\right),\notag\end{equation}

where $q_{i,0} > 0$ and $q_{i,i-1} > 0$ ( $i \in \mathbb{Z}^+ \setminus\{0\}$ ). We then have

\begin{equation*}\mathcal{J}(N) = \{0,N\},\end{equation*}

because the state immediately after a downward transition from state i ( $i \geq N+1$ ) is either state 0 or state $i-1$ . It then follows that

\begin{equation*}\Gamma^+(N)=\bigl\{\bigl(\alpha_0\ \ 0\ \ 0\ \ \cdots\ \ 0\ \ 1-\alpha_0\bigr) \in \mathbb{R}^{N+1};\ \alpha_0 \in [0,1]\bigr\},\end{equation*}

and

\begin{equation*}\boldsymbol{\pi}(N) \in \textrm{ri}\, \mathcal{P}^+(N)=\bigl\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}=\alpha_0 \overline{\textbf{\textit{h}}}_0(N) + (1-\alpha_0) \overline{\textbf{\textit{h}}}_N(N),\,\alpha_0 \in (0,1)\bigr\}.\end{equation*}

Note here that $\overline{\textbf{\textit{h}}}_i(N)$ ( $i \in \mathbb{Z}_0^N$ ) can be obtained by (i) solving $\textbf{\textit{x}}_i (\!-\textbf{\textit{Q}}^{(1,1)}(N)) = \textbf{\textit{e}}_i(N)$ for $\textbf{\textit{x}}_i \in \mathbb{R}^{N+1}$ and (ii) letting $\overline{\textbf{\textit{h}}}_i(N)=\textbf{\textit{x}}_i/\textbf{\textit{x}}_i\textbf{\textit{e}}$ , where $\textbf{\textit{e}}_i(N) \in \mathbb{R}^{N+1}$ denotes a $1 \times (N+1)$ unit vector whose ith element is equal to one. The simplest way to obtain an approximation $\boldsymbol{\pi}^{\textrm{approx}}(N) \in\textrm{ri}\, \mathcal{P}^+(N)$ to $\boldsymbol{\pi}(N)$ might be to solve $\textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}) = \beta_0 \textbf{\textit{e}}_0(N)+ (1-\beta_0) \textbf{\textit{e}}_N(N)$ for an arbitrary $\beta_0 \in (0,1)$ and let $\boldsymbol{\pi}^{\textrm{approx}}(N) = \textbf{\textit{x}}/\textbf{\textit{x}}\textbf{\textit{e}}$ .

We now show that $\mathcal{P}^+(N)$ is tight in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N),\mathcal{J}(N))$ .

Proof. We assume $[\textbf{\textit{x}}]_{j^*} = 0$ for some $j^* \in \mathbb{Z}_0^N$ and derive a contradiction. Since $\textbf{\textit{x}} = \boldsymbol{\alpha}(\textbf{\textit{x}})\overline{\textbf{\textit{H}}}(N)$ for some $\boldsymbol{\alpha}(\textbf{\textit{x}}) \in\textrm{ri}\, \Gamma^+(N)$ , $[\textbf{\textit{x}}]_{j^*} = 0$ is equivalent to $[\boldsymbol{\alpha}(\textbf{\textit{x}}) \overline{\textbf{\textit{H}}}(N)]_{j^*} = 0$ for some $\boldsymbol{\alpha}(\textbf{\textit{x}}) \in \textrm{ri}\, \Gamma^+(N)$ . This implies that $[\overline{\textbf{\textit{H}}}(N)]_{i,j^*} = 0$ for all $i \in \mathcal{J}(N)$ since $[\boldsymbol{\alpha}(\textbf{\textit{x}})]_i > 0$ for all $i \in \mathcal{J}(N)$ and $\overline{\textbf{\textit{H}}}(N) \geq \textbf{\textit{O}}$ . It then follows from (2.15) that $\mathbb{P}(X(0) = j^* \mid I(0) \in \mathcal{J}(N)) = 0$ for any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N),\mathcal{J}(N))$ . Furthermore, $\mathbb{P}(I(0) \in \mathbb{Z}_0^N \setminus \mathcal{J}(N)) = 0$ and $\mathbb{P}(X(0) = j^* \mid I(0) \in \mathbb{Z}_{N+1}^{\infty}) = 0$ by definition. We thus have

\begin{align*}\mathbb{P}(X(0)=j^*)&=\mathbb{P}(I(0) \in \mathcal{J}(N)) \mathbb{P}(X(0)=j^* \mid I(0) \in \mathcal{J}(N))\\[3pt] & \qquad\qquad {}+\mathbb{P}(I(0) \in \mathbb{Z}_{N+1}^{\infty})\mathbb{P}(X(0) = j^* \mid I(0) \in \mathbb{Z}_{N+1}^{\infty})\\[3pt] &= 0,\end{align*}

for any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N))$ , which contradicts the ergodicity. □

Proof. It follows from (2.24) that if $\textbf{\textit{x}} \in \textrm{ri}\, \mathcal{P}^+(N)$ , we have $\textbf{\textit{x}} \in \mathcal{P}(N)$ , i.e., $\textbf{\textit{x}} (\!-\textbf{\textit{Q}}^{(1,1)}(N)) \geq\textbf{0}$ and $\textbf{\textit{x}}\textbf{\textit{e}}=1$ . Note also that $\textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N)) \neq \textbf{0}$ , because if $\textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N)) = \textbf{0}$ held, we would have $\textbf{\textit{x}}= \textbf{0}\cdot (\!-\textbf{\textit{Q}}^{(1,1)}(N))^{-1} = \textbf{0}$ , which contradicts $\textbf{\textit{x}}\textbf{\textit{e}}=1$ . We then define $\boldsymbol{\zeta}(\textbf{\textit{x}})$ as

(2.25) \begin{equation}\boldsymbol{\zeta}(\textbf{\textit{x}})=\frac{\textbf{\textit{x}} (\!-\textbf{\textit{Q}}^{(1,1)}(N))}{\textbf{\textit{x}} (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}}}.\end{equation}

It is easy to see that $\boldsymbol{\zeta}(\textbf{\textit{x}}) \in \textrm{ri}\, \Gamma^+(N)$ for $\textbf{\textit{x}} \in \textrm{ri}\, \mathcal{P}^+(N)$ . For an arbitrarily chosen $\textbf{\textit{x}} \in\textrm{ri}\, \mathcal{P}^+(N)$ , we consider a Markov chain whose infinitesimal generator $\textbf{\textit{Q}}$ is given by

(2.26) \begin{equation}\textbf{\textit{Q}}= \kbordermatrix{&\mathbb{Z}_0^N & \mathbb{Z}_{N+1}^{\infty}\\ \\[-7pt]\mathbb{Z}_0^N & \textbf{\textit{Q}}^{(1,1)}(N) &\quad \textbf{\textit{Q}}^{(1,2)}(N)\\ \\[-7pt] \mathbb{Z}_{N+1}^{\infty}& (\!-\textbf{\textit{Q}}^{(2,2)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}(\textbf{\textit{x}}) &\quad \textbf{\textit{Q}}^{(2,2)}(N)}.\end{equation}

The global balance equations are then given by

(2.27) \begin{align}\boldsymbol{\pi}^{(1)}(N) \textbf{\textit{Q}}^{(1,1)}(N)+\boldsymbol{\pi}^{(2)}(N) (\!-\textbf{\textit{Q}}^{(2,2)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}(\textbf{\textit{x}}) &= \textbf{0},\end{align}

(2.28) \begin{align}\hspace*{40pt}\boldsymbol{\pi}^{(1)}(N) \textbf{\textit{Q}}^{(1,2)}(N) + \boldsymbol{\pi}^{(2)}(N) \textbf{\textit{Q}}^{(2,2)}(N)&= \textbf{0}.\end{align}

From (2.25) and (2.27), we observe that the special form of $\textbf{\textit{Q}}^{(2,1)}(N) =(\!-\textbf{\textit{Q}}^{(2,2)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}(\textbf{\textit{x}})$ ensures $\boldsymbol{\pi}^{(1)}(N) = c_1 \textbf{\textit{x}}$ for some positive constant $c_1$ . We now set

(2.29) \begin{equation}\textbf{\textit{Q}}^{(1,2)}(N) = (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \textbf{\textit{z}},\qquad\textbf{\textit{Q}}^{(2,2)}(N) = -\textbf{\textit{I}},\end{equation}

where $\textbf{\textit{z}}$ denotes a $1 \times \infty$ positive probability vector. Equation (2.28) is then reduced to

(2.30) \begin{equation}\boldsymbol{\pi}^{(1)}(N) (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}}\textbf{\textit{z}}- \boldsymbol{\pi}^{(2)}(N)= \textbf{0},\end{equation}

which indicates that (2.29) ensures $\boldsymbol{\pi}^{(2)}(N) = c_2 \textbf{\textit{z}} > \textbf{0}$ for some positive constant $c_2$ . In fact, solving (2.27) and (2.30) with $\boldsymbol{\pi}^{(1)}(N)\textbf{\textit{e}} +\boldsymbol{\pi}^{(2)}(N)\textbf{\textit{e}} = 1$ , we obtain

\begin{equation*}\boldsymbol{\pi}=\begin{pmatrix}\boldsymbol{\pi}^{(1)}(N) &\quad \boldsymbol{\pi}^{(2)}(N)\end{pmatrix}=\frac{1}{1+\textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}}}\begin{pmatrix}\textbf{\textit{x}} &\quad \textbf{\textit{x}}(\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \cdot \textbf{\textit{z}}\end{pmatrix}> \textbf{0}.\end{equation*}

We thus conclude that the Markov chain with the infinitesimal generator $\textbf{\textit{Q}}$ defined by (2.26) and (2.29) is a member of $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N),\mathcal{J}(N))$ and it has $\boldsymbol{\pi}(N) = \textbf{\textit{x}}$ . □

2.4. Implications for the augmented truncation approximation

We provide some practical implications of the results in Sections 2.2 and 2.3 for the augmented truncation approximation (ATA). As mentioned in Section 1, an ATA solution $\boldsymbol{\pi}^{\textrm{trunc}}(N)$ to $\boldsymbol{\pi}(N)$ is obtained by

(2.31) \begin{equation}\boldsymbol{\pi}^{\textrm{trunc}}(N) [\textbf{\textit{Q}}^{(1,1)}(N)+ \textbf{\textit{Q}}_{\textrm{A}}(N)]=\textbf{0},\quad\boldsymbol{\pi}^{\textrm{trunc}}(N)\textbf{\textit{e}}=1,\end{equation}

where $\textbf{\textit{Q}}_{\textrm{A}}(N)$ denotes an augmentation matrix, i.e., an $(N+1) \times (N+1)$ nonnegative matrix satisfying $\textbf{\textit{Q}}_{\textrm{A}}(N)\textbf{\textit{e}} = (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}}$ . The central topic in the literature on the ATA is the convergence of $\boldsymbol{\pi}^{\textrm{approx},N}=(\boldsymbol{\pi}^{\textrm{trunc}}(N)\ \ \textbf{0})$ to the stationary distribution $\boldsymbol{\pi}$ as N goes to infinity. Note that our interest is different from this; that is to say, we are interested in what kind of $\textbf{\textit{Q}}_{\textrm{A}}(N)$ is reasonable for a given N.

Although $\textbf{\textit{Q}}_{\textrm{A}}(N)$ is usually chosen in such a way that $[\textbf{\textit{Q}}^{(1,1)}(N)+ \textbf{\textit{Q}}_{\textrm{A}}(N)]$ is irreducible, we allow reducible $[\textbf{\textit{Q}}^{(1,1)}(N)+ \textbf{\textit{Q}}_{\textrm{A}}(N)]$ as well. Note that the error bound for the approximation $\boldsymbol{\pi}^{\textrm{approx},N} =(\boldsymbol{\pi}^{\textrm{trunc}}(N)\ \ \textbf{0})$ to the stationary distribution $\boldsymbol{\pi}$ is given by

\begin{equation*}2 \mathbb{P}(X(0) > N)\leq\| \boldsymbol{\pi}^{\textrm{approx},N} - \boldsymbol{\pi} \|_1\leq\epsilon^{\textrm{trunc}}(N) + 2 \mathbb{P}(X(0) > N)\end{equation*}

(see [Reference Kimura and Takine5]), where $\epsilon^{\textrm{trunc}}(N)$ denotes an upper bound of $\| \boldsymbol{\pi}^{\textrm{trunc}}(N) - \boldsymbol{\pi}(N)\|_1$ :

\begin{equation*}\| \boldsymbol{\pi}^{\textrm{trunc}}(N) - \boldsymbol{\pi}(N)\|_1 \leq \epsilon^{\textrm{trunc}}(N).\end{equation*}

It is clear that $\mathbb{P}(X(0) > N)$ is a decreasing function of N and that for a given N, $\boldsymbol{\pi}^{\textrm{approx},N}$ will be the best approximation to $\boldsymbol{\pi}$ when $\boldsymbol{\pi}^{\textrm{trunc}}(N) = \boldsymbol{\pi}(N)$ (i.e., $\epsilon^{\textrm{trunc}}(N) = 0$ ) [Reference Zhao and Liu16]. In what follows, we first consider Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ and discuss some implications of our results in Section 2.2 for the ATA.

We define $\mathcal{T}(N)$ as the set of all possible ATA solutions satisfying (2.31):

\begin{equation*}\mathcal{T}(N)=\bigl\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}\big[\textbf{\textit{Q}}^{(1,1)}(N)+\textbf{\textit{Q}}_{\textrm{A}}(N)\big]=\textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}}=1,\ \textbf{\textit{Q}}_{\textrm{A}}(N) \in \mathcal{A}(N)\bigr\},\end{equation*}

where $\mathcal{A}(N)$ denotes the set of all possible augmentation matrices,

\begin{equation*}\mathcal{A}(N)=\bigl\{\textbf{\textit{X}} \in \mathbb{R}^{(N+1)\times(N+1)};\ \textbf{\textit{X}}\geq\textbf{\textit{O}},\ \textbf{\textit{X}}\textbf{\textit{e}}=(\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}}\bigr\}.\end{equation*}

In the literature, the ATA is called linear if the rank of $\textbf{\textit{Q}}_{\textrm{A}}(N)$ is equal to one [Reference Gibson and Seneta2]. We then define $\mathcal{T}_{\textrm{L}}(N)$ as the set of all possible approximations obtained by the linear ATA:

\begin{equation*}\mathcal{T}_{\textrm{L}}(N)=\bigl\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}\big[\textbf{\textit{Q}}^{(1,1)}(N)+\textbf{\textit{Q}}_{\textrm{A}}(N)\big] = \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}}=1,\ \textbf{\textit{Q}}_{\textrm{A}}(N) \in \mathcal{A}_{\textrm{L}}(N)\bigr\},\end{equation*}

where $\mathcal{A}_{\textrm{L}}(N)$ denotes the set of all possible linear augmentation matrices,

\begin{equation*}\mathcal{A}_{\textrm{L}}(N)=\bigl\{\textbf{\textit{X}} \in \mathbb{R}^{(N+1)\times(N+1)};\ \textbf{\textit{X}} = (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \boldsymbol{\zeta},\boldsymbol{\zeta} \in \Gamma(N)\bigr\}.\end{equation*}

Recall that $\Gamma(N)$ is the set of all $1 \times (N+1)$ probability vectors, which is defined in (2.5).

Lemma 2.2. For any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N))$ , we have

\begin{equation*}\mathcal{T}(N) = \mathcal{T}_{\textrm{L}}(N) = \mathcal{P}(N),\quad N \in \mathbb{Z}^+,\end{equation*}

where $\mathcal{P}(N)$ is given by (2.8).

The proof of Lemma 2.2 is given in Appendix C. Lemma 2.2 implies the following.

Implication 2.1. In view of Remark 2.1, we can consider that the ATA attempts to find an approximation to the weight vector $\boldsymbol{\alpha}^*(N)$ for $\overline{\textbf{\textit{H}}}(N)$ in (2.12) by setting the augmentation matrix $\textbf{\textit{Q}}_{\textrm{A}}(N)$ appropriately. In this sense, the linear ATA has the same degree of freedom as the general ATA does.

We thus restrict our attention to the linear ATA with $\textbf{\textit{Q}}_{\textrm{A}}(N)= (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}$ , where $\boldsymbol{\zeta} \in\Gamma(N)$ . In this case, (2.31) is reduced to

(2.32) \begin{equation}\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})[\textbf{\textit{Q}}^{(1,1)}(N) + (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}] = \textbf{0},\quad\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})\textbf{\textit{e}}=1.\end{equation}

Note here that $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ in (2.32) is closely related to $\boldsymbol{\pi}(N)$ in a Markov chain with the infinitesimal generator $\textbf{\textit{Q}}$ in (2.26). Specifically, using the cut-flow balance equation

\begin{equation*}\boldsymbol{\pi}^{(1)}(N) (\!-\textbf{\textit{Q}}^{(1,1)}(N)) \textbf{\textit{e}}=\boldsymbol{\pi}^{(2)}(N) (\!-\textbf{\textit{Q}}^{(2,2)}(N)) \textbf{\textit{e}},\end{equation*}

we can rewrite (2.27) to be

\begin{equation*}\boldsymbol{\pi}^{(1)}(N) \bigl[\textbf{\textit{Q}}^{(1,1)}(N)+(\!-\textbf{\textit{Q}}^{(1,1)}(N)) \textbf{\textit{e}} \boldsymbol{\zeta}(\textbf{\textit{x}})\bigr] = \textbf{0}.\end{equation*}

We thus have $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) = \boldsymbol{\pi}(N) =\textbf{\textit{x}}\in \mathcal{P}(N)$ if we set $\boldsymbol{\zeta} = \boldsymbol{\zeta}(\textbf{\textit{x}})$ in (2.32).

Implication 2.2. The linear ATA solution $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ for a specific $\boldsymbol{\zeta}$ is identical to $\boldsymbol{\pi}(N)$ in an ergodic Markov chain whose infinitesimal generator takes the following form:

\begin{equation*}\textbf{\textit{Q}}= \kbordermatrix{&\mathbb{Z}_0^N & \mathbb{Z}_{N+1}^{\infty}\\ \\[-7pt]\mathbb{Z}_0^N & \textbf{\textit{Q}}^{(1,1)}(N) &\quad \textbf{\textit{Q}}^{(1,2)}(N) \\ \\[-7pt] \mathbb{Z}_{N+1}^{\infty}& (\!-\textbf{\textit{Q}}^{(2,2)}(N)\textbf{\textit{e}}) \boldsymbol{\zeta} &\quad \textbf{\textit{Q}}^{(2,2)}(N)}.\end{equation*}

Since $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) \in \mathcal{T}_{\textrm{L}}(N) = \mathcal{P}(N)$ , it follows from Theorem 2.1 that

(2.33) \begin{equation}\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})=\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) \overline{\textbf{\textit{H}}}(N)\end{equation}

for some $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) \in \Gamma(N)$ . Recall that there is a one-to-one correspondence between $\boldsymbol{\pi}^{\textrm{trunc}}(N;\,\boldsymbol{\zeta})$ and $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})$ , as stated in Remark 2.1. Note also that there are one-to-one correspondences between $\boldsymbol{\zeta}$ and $\boldsymbol{\alpha}(N;\,\boldsymbol{\zeta})$ ,

(2.34) \begin{equation}\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})=\frac{\boldsymbol{\zeta} \textrm{diag}(\textbf{\textit{H}}(N)\textbf{\textit{e}})}{\boldsymbol{\zeta} \textrm{diag}(\textbf{\textit{H}}(N)\textbf{\textit{e}})\textbf{\textit{e}}},\qquad\boldsymbol{\zeta}=\frac{\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) \textrm{diag}^{-1}(\textbf{\textit{H}}(N)\textbf{\textit{e}})}{\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) \textrm{diag}^{-1}(\textbf{\textit{H}}(N)\textbf{\textit{e}}) \textbf{\textit{e}}},\end{equation}

and between $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ and $\boldsymbol{\zeta}$ ,

\begin{equation*}\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})=\frac{\boldsymbol{\zeta} \textbf{\textit{H}}(N)}{\boldsymbol{\zeta} \textbf{\textit{H}}(N)\textbf{\textit{e}}},\qquad\boldsymbol{\zeta}=\frac{\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})(\!-\textbf{\textit{Q}}^{(1,1)}(N))}{\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})(\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}}}.\end{equation*}

From (2.33), we also observe that $\boldsymbol{\pi}^{\textrm{trunc}}(N;\,\boldsymbol{\zeta})$ is given by a convex combination of the row vectors $\overline{\textbf{\textit{h}}}_i(N)$ ( $i \in \mathbb{Z}_0^N$ ) of $\overline{\textbf{\textit{H}}}(N)$ with the nonnegative weight vector $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})$ . It then follows from (2.13) that

(2.35) \begin{equation}\|\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) - \boldsymbol{\pi}(N) \|_1\leq\max_{i \in \mathbb{Z}_0^N}\| \boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) - \overline{\textbf{\textit{h}}}_i(N) \|_1.\end{equation}

This error bound tempts us to set $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})$ in such a way that $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ is located at the center of the $\mathcal{P}(N)$ spanned by the $\overline{\textbf{\textit{h}}}_i(N)$ ( $i\in \mathbb{Z}_0^N$ ). For example, if we set $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) =\textbf{\textit{e}}^T/(N+1)$ , where T stands for the transpose operator, then $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ is given by the center of gravity of $\mathcal{P}(N)$ . Note here that (2.33) is equivalent to $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) (\!-\textbf{\textit{Q}}^{(1,1)}(N)) =\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) \textrm{diag}^{-1}(\textbf{\textit{H}}(N)\textbf{\textit{e}})$ .

Implication 2.3 If we have a desirable $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})$ rather than $\boldsymbol{\zeta}$ itself, $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ for such an $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})$ can be computed as follows:

1. (i) We first obtain $\boldsymbol{\eta}(N)\coloneqq \textbf{\textit{H}}(N)\textbf{\textit{e}}$ by solving $(\!-\textbf{\textit{Q}}^{(1,1)}(N)) \boldsymbol{\eta}(N) = \textbf{\textit{e}}$ .

2. (ii) We then obtain $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ by solving

   \begin{equation*}\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) (\!-\textbf{\textit{Q}}^{(1,1)}(N)) =\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) \textrm{diag}^{-1}(\boldsymbol{\eta}(N)).\end{equation*}

In the above procedure, we have to solve two systems of linear equations with $-\textbf{\textit{Q}}^{(1,1)}(N)$ . Therefore, relative to the procedure for solving (2.32) directly for a specific $\boldsymbol{\zeta}$ , the computational cost increases by $(N+1)^2$ in terms of the number of multiplications/divisions, if we utilize the LU decomposition. This increase can be regarded as the cost of specifying the weight vector $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})$ directly, instead of specifying $\boldsymbol{\zeta}$ .

Next we consider Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N))$ , where the structural information $\mathcal{J}(N)$ is assumed to be available. It follows from (2.34) that for all $i \in \mathbb{Z}_0^N$ ,

(2.36) \begin{equation}[\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta})]_i = 0\ \Leftrightarrow\ [\boldsymbol{\zeta}]_i = 0.\end{equation}

We then define $\mathcal{T}_{\textrm{L}}^+(N)$ as the set of all possible approximations obtained by the linear ATA when $\mathcal{J}(N)$ is available:

\begin{equation*}\mathcal{T}_{\textrm{L}}^+(N)=\bigl\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}}\big[\textbf{\textit{Q}}^{(1,1)}(N) + (\!-\textbf{\textit{Q}}^{(1,1)}(N)) \textbf{\textit{e}} \boldsymbol{\zeta}\big]= \textbf{0},\ \textbf{\textit{x}}\textbf{\textit{e}} = 1,\boldsymbol{\zeta} \in \Gamma^+(N)\bigr\},\end{equation*}

where $\Gamma^+(N)$ is given by (2.20). By definition, we have $\mathcal{T}_{\textrm{L}}^+(N) \subseteq \mathcal{T}_{\textrm{L}}(N)$ .

Lemma 2.3. Suppose $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N)) \neq \emptyset$ . For any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(N), \mathcal{J}(N))$ , we have

\begin{equation*}\mathcal{T}_{\textrm{L}}^+(N) = \mathcal{P}^+(N),\quad N \in \mathbb{Z}^+,\end{equation*}

where $\mathcal{P}^+(N)$ is given by (2.23).

The proof of Lemma 2.3 is given in Appendix D. We thus have $\boldsymbol{\pi}(N) \in \textrm{ri}\, \mathcal{T}_{\textrm{L}}^+(N)$ from Theorem 2.2. It also follows from (2.36) that if $[\boldsymbol{\zeta}]_i > 0$ for some $i \in \mathbb{Z}_0^N \setminus \mathcal{J}(N)$ , we have $\boldsymbol{\pi}^{\textrm{trunc}}(N;\,\boldsymbol{\zeta}) \notin \mathcal{P}^+(N)$ , because the $\overline{\textbf{\textit{h}}}_j(N)$ ( $j\in \mathbb{Z}_0^N$ ) are linearly independent. Moreover, it follows from Corollary 2.3 that

(2.37) \begin{equation}\|\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) - \boldsymbol{\pi}(N) \|_1\leq\max_{i \in \mathcal{J}(N)}\| \boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) - \overline{\textbf{\textit{h}}}_i(N) \|_1,\quad\boldsymbol{\zeta} \in \Gamma^+(N),\end{equation}

which is tighter than (2.35). In summary, we have the following.

Implication 2.4. If the structural information $\mathcal{J}(N)$ is available, it is natural that we should choose $\boldsymbol{\zeta}$ from $\textrm{ri}\, \Gamma^+(N)$ in obtaining a linear ATA solution, where $\Gamma^+(N)$ is given by (2.20). For example, we may choose $\boldsymbol{\zeta}$ whose ith ( $i \in \mathbb{Z}_0^N$ ) element is given by $1/|\mathcal{J}(N)|$ if $i\in \mathcal{J}(N)$ and by 0 otherwise.

Implication 2.4 indicates that the last-column augmentation $\boldsymbol{\zeta} =(0\ 0\ \cdots\ 0\ 1)$ , which is one of the common augmentation strategies in the literature, may not be effective unless $\mathcal{J}(N) =\{N\}$ , because if $\mathcal{J}(N) \neq \{N\}$ , we have $\boldsymbol{\zeta} = (0\ 0\ \cdots\ 0\ 1) \not\in \textrm{ri}\, \Gamma^+(N)$ and therefore $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) \not\in \textrm{ri}\, \mathcal{P}^+(N)$ , while $\boldsymbol{\pi}(N) \in \textrm{ri}\, \mathcal{P}^+(N)$ .

Example 2.3. (Example 2.1 continued.) Consider $\textbf{\textit{Q}}$ in Example 2.1 of Section 2.3. Since $\mathcal{J}(N) = \{0,N\}$ , we may set $\boldsymbol{\zeta} = (\zeta_0\ \ 0\ \ 0\ \ \cdots\ \ 0\ \ 1-\zeta_0) \in\textrm{ri}\, \Gamma^+(N)$ for an arbitrary $\zeta_0 \in (0,1)$ . The ATA solution $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta})$ is then obtained by solving

\begin{equation*}\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) [\textbf{\textit{Q}}^{(1,1)}(N) + (\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}] = \textbf{0}\end{equation*}

with $\boldsymbol{\pi}^{\textrm{trunc}}(N;\, \boldsymbol{\zeta}) \textbf{\textit{e}} = 1$ . If we are concerned with the error bound in (2.37), we first compute $\overline{\textbf{\textit{h}}}_i$ ( $i=0,N$ ) by the procedure described in Example 2.1 and then adopt $(\overline{\textbf{\textit{h}}}_0+\overline{\textbf{\textit{h}}}_N)/2$ as the ATA solution (or alternatively, we perform the procedure in Implication 2.3 with $\boldsymbol{\alpha}(N;\, \boldsymbol{\zeta}) =(1/2\ 0\ 0\ \cdots\ 0\ 1/2)$ ). Note that this choice yields the minimum error bound of (2.37) in this specific example, which is half the error bound of the last-column augmentation.

Remark 2.2. As shown in (A.1), we have

\begin{equation*}\boldsymbol{\zeta}^*=\frac{\boldsymbol{\pi}^{(2)}(N)\textbf{\textit{Q}}^{(2,1)}(N)}{\boldsymbol{\pi}^{(2)}(N)\textbf{\textit{Q}}^{(2,1)}(N)\textbf{\textit{e}}},\end{equation*}

which satisfies $\boldsymbol{\pi}(N)[\textbf{\textit{Q}}^{(1,1)}(N)+(\!-\textbf{\textit{Q}}^{(1,1)}(N))\textbf{\textit{e}} \boldsymbol{\zeta}^*] = \textbf{0}$ . Therefore, in order to obtain a good one-point approximation to the conditional stationary distribution $\boldsymbol{\pi}(N)$ , we need some information about $\boldsymbol{\pi}^{(2)}(N)$ , as in the Iterative Aggregation/Disaggregation methods for finite-state Markov chains [Reference Stewart13, Reference Takahashi14].

4.1. (K, N)-skip-free sets

For an arbitrary non-empty subset $\mathcal{B}$ of $\mathbb{Z}^+$ , we define $F(\mathcal{B})$ as the first passage time to $\mathcal{B}$ :

\begin{equation*}F(\mathcal{B}) = \inf\{t \geq 0;\ X(t) \in \mathcal{B}\},\qquad\mathcal{B} \subseteq \mathbb{Z}^+.\end{equation*}

Definition 4.1. ((K, N)-skip-free set.) For arbitrarily fixed $K, N \in \mathbb{Z}^+$ ( $K > N$ ), consider a Markov chain $\{X(t)\}_{t \in (\!-\infty,\infty)}$ in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K),\mathcal{J}(K))$ . We refer to a subset $\mathcal{X}$ of $\mathbb{Z}_0^K$ as a (K, N)-skip-free set if $\{X(t)\}_{t \in (\!-\infty,\infty)}$ starting from any state in $\mathbb{Z}_{K+1}^{\infty}$ must visit $\mathcal{X}$ by the first passage time to $\mathbb{Z}_0^N$ , i.e.,

\begin{equation*}\mathbb{P}(X(t) \in \mathcal{X} \mbox{ for some } t \in (0,F(\mathbb{Z}_0^N)]\mid X(0) \in \mathbb{Z}_{K+1}^{\infty}) = 1.\end{equation*}

In particular, a (K, N)-skip-free set $\mathcal{X}$ is called proper if for any proper subset $\mathcal{Y}$ of $\mathcal{X}$ ,

\begin{equation*}\mathbb{P}(X(t) \in \mathcal{Y} \mbox{ for some } t \in (0,F(\mathbb{Z}_0^N)]\mid X(0) \in \mathbb{Z}_{K+1}^{\infty}) < 1.\end{equation*}

Let $\mathcal{S}(K,N)$ denote the family of all (K, N)-skip-free sets and $\mathcal{S}^*(K,N)$ the family of all proper (K, N)-skip-free sets.

1. (i) (K, N)-skip-free sets are determined only by $\textbf{\textit{Q}}^{(1,1)}(K)$ and $\mathcal{J}(K)$ ,

2. (ii) $\mathcal{S}^*(K,N)\subseteq\mathcal{S}(K,N)$ ,

3. (iii) $\mathcal{J}(K) \in \mathcal{S}(K,N)$ and $\widetilde{\mathcal{J}}(K,N) \in \mathcal{S}^*(K,N)$ , where $\widetilde{\mathcal{J}}(K,N)$ is given by (3.19), and

4. (iv) $\mathcal{J}(K) \cap \mathbb{Z}_0^N \subseteq \mathcal{X}\ \mbox{for all}\ \mathcal{X} \in\mathcal{S}(K,N)$ .

We can provide an equivalent definition of (K, N)-skip-free sets by considering a directed graph associated with $\textbf{\textit{Q}}^{(1,1)}(K)$ and $\mathcal{J}(K)$ . Specifically, for arbitrarily fixed $K, N \in \mathbb{Z}^+$ ( $K > N$ ), we define the directed graph

(4.2) \begin{equation}G(K,N)=(V(K,N),E(K,N)),\end{equation}

where V(K, N) and E(K, N) denote sets of nodes and arcs defined as

\begin{align*}V(K,N) &= \{s,t\} \cup \mathbb{Z}_0^K,\\[3pt] E(K,N) &=\{(s,j);\ j \in \mathcal{J}(K)\} \cup \{(i,t);\ i \in \mathbb{Z}_0^N\}\\[3pt]&\quad {}\cup\{(i,j);\ i \in \mathbb{Z}_{N+1}^K,\ j \in \mathbb{Z}_0^K, q_{i,j}>0\}.\end{align*}

Node s represents the set of states in $\mathbb{Z}_{K+1}^{\infty}$ , and node t is a virtual terminal node for the first passage to $\mathbb{Z}_0^N$ . It is readily seen from Definition 4.1 that a subset $\mathcal{X}$ of $\mathbb{Z}_0^K$ is a (K, N)-skip-free set iff $\mathcal{X}$ is an (s,t)-node cut in G(K, N), and that $\mathcal{X}$ is proper iff it is a minimal (s, t)-node cut.

For a given G(K, N), nodes in $\mathbb{Z}_0^K$ can be classified into two classes, depending on whether they appear on the way of at least one path from node s to node t. That is,

\begin{equation*}\mathbb{Z}_0^K=\mathcal{N}_+(K,N) \cup \mathcal{N}_0(K,N),\qquad\mathcal{N}_+(K,N) \cap \mathcal{N}_0(K,N) = \emptyset,\end{equation*}

where nodes in $\mathcal{N}_+(K,N)$ are reachable from node s and each of them has at least one path to node t. Note here that $\mathcal{N}_0(K,N)= \mathbb{Z}_0^K \setminus \mathcal{N}_+(K,N)$ is given by

\begin{equation*}\mathcal{N}_0(K,N) = \mathcal{N}_0^{(1)}(K,N) \cup \mathcal{N}_0^{(2)}(K,N) \cup \mathcal{N}_0^{(3)}(K,N),\end{equation*}

where $\mathcal{N}_0^{(\ell)}(K,N)$ ( $\ell=1,2,3$ ) are defined as follows:

\begin{align*}\mathcal{N}_0^{(1)}(K,N)&=\mathbb{Z}_0^N \setminus \widetilde{\mathcal{J}}(K,N)=\{i \in \mathbb{Z}_0^N;\ \mathbb{P}(X(F(\mathbb{Z}_0^N)) = i \mid X(0) \in \mathbb{Z}_{K+1}^{\infty}) = 0\},\\[3pt] \mathcal{N}_0^{(2)}(K,N)&=\{i \in \mathbb{Z}_{N+1}^K;\ \\[3pt] &\qquad\qquad\mathbb{P}(X(t) \in \mathbb{Z}_{N+1}^{\infty} \mbox{ for all } t \in (0,F(\{i\})]\mid X(0) \in \mathbb{Z}_{K+1}^{\infty}) = 0\},\\[3pt] \mathcal{N}_0^{(3)}(K,N)&=\{i \in \mathbb{Z}_{N+1}^K;\ \mathbb{P}(X(t) \in \mathbb{Z}_{N+1}^K \mbox{ for all } t \in (0,F(\mathbb{Z}_0^N)]\mid X(0) = i) = 0\}.\end{align*}

Roughly speaking, states in $\mathcal{N}_0^{(1)}(K,N) \subseteq \mathbb{Z}_0^N$ and states in $\mathcal{N}_0^{(2)}(K,N) \subseteq \mathbb{Z}_{N+1}^K$ can be reached from any states in $\mathbb{Z}_{K+1}^{\infty}$ only after visiting $\widetilde{\mathcal{J}}(K,N) \subseteq \mathbb{Z}_0^N$ . On the other hand, states in $\mathcal{N}_0^{(3)}(K,N) \in \mathbb{Z}_{N+1}^K$ have no paths to $\widetilde{\mathcal{J}}(K,N)$ without visiting $\mathbb{Z}_{K+1}^{\infty}$ .

By definition, $\mathcal{X} \cap \mathcal{N}_0(K,N) = \emptyset$ if $\mathcal{X} \in\mathcal{S}^*(K,N)$ , whereas there may exist $\mathcal{X} \in \mathcal{S}(K,N)$ such that $\mathcal{X}\cap \mathcal{N}_0(K,N) \neq \emptyset$ . As we will see, all states in $\mathcal{N}_0(K,N)$ can be excluded from consideration when we study $\boldsymbol{\pi}(N)$ for Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K),\mathcal{J}(K))$ .

Before considering minimum convex polytopes for Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K),\mathcal{J}(K))$ , we provide a remark on (K, N)-skip-free sets. Note that (K, N)-skip-free sets can be regarded as a natural extension of levels with the skip-free-to-the-left property in Markov chains of M/G/1-type. Suppose a Markov chain $\{X(t)\}_{t\in(\!-\infty, \infty)}$ is of M/G/1-type; i.e., its state space $\mathbb{Z}^+$ is partitioned into disjoint levels $\{\mathcal{L}_m;\ m\in \mathbb{Z}^+\}$ , and transitions between two levels are skip-free to the left. We now consider the first passage time from $\mathcal{L}_{K+1}$ to $\mathcal{L}_N$ ( $K > N$ ). It then follows that each level $\mathcal{L}_m$ ( $m=N,N+1,\ldots,K$ ) can be regarded as a $(\hat{K},\hat{N})$ -skip-free set, where $\hat{K}$ and $\hat{N}$ denote the total number of states in $\bigcup_{m=0}^K \mathcal{L}_m$ and $\bigcup_{m=0}^N \mathcal{L}_m$ . One of the most notable differences between (K, N)-skip-free sets and levels with the skip-free-to-the-left property is that (K, N)-skip-free sets are not disjoint, while levels are disjoint.

Example 4.1. (Example 2.1 continued.) Consider $\textbf{\textit{Q}}$ in Example 2.1 of Section 2.3. $\mathcal{S}^*(K,N)$ is given by

\begin{equation*}\mathcal{S}^*(K,N) = \bigl\{ \{0,k\};\ k \in \mathbb{Z}_N^K \bigr\}.\end{equation*}

4.2. Minimum convex polytopes

We consider convex polytopes associated with (K, N)-skip-free sets. We partition $\textbf{\textit{H}}(K)=(\!-\textbf{\textit{Q}}^{(1,1)}(K))^{-1}$ into two matrices as in (4.1). Note here that

(4.3) \begin{equation}[\textbf{\textit{H}}^{(*,1)}(K;\, N)\textbf{\textit{e}}]_{i} = 0,\quad i \in \mathcal{N}_0^{(3)}(K,N),\end{equation}

and $[\textbf{\textit{H}}^{(*,1)}(K;\, N)\textbf{\textit{e}}]_{i} > 0$ for all $i \in \mathbb{Z}_0^K\setminus \mathcal{N}_0^{(3)}(K,N)$ . For any $(K+1)$ -dimensional vector $\textbf{\textit{x}}$ , we define $\textrm{diag}^*(\textbf{\textit{x}})$ as a $(K+1)$ -dimensional diagonal matrix whose ith ( $i \in \mathbb{Z}_0^K$ ) diagonal element is given by

\begin{equation*}[\textrm{diag}^*(\textbf{\textit{x}})]_{i,i}=\begin{cases}\displaystyle\frac{1}{[\textbf{\textit{x}}]_i}, & [\textbf{\textit{x}}]_i \neq 0,\\[3pt] 0, & \textrm{otherwise}.\end{cases}\end{equation*}

We then define $\Gamma(K,N;\,\mathcal{B})$ ( $K,N \in \mathbb{Z}^+$ , $K > N$ , $\mathcal{B} \subseteq\mathbb{Z}_0^K$ ) as

\begin{align*}\Gamma(K,N;\,\mathcal{B})&=\big\{\boldsymbol{\alpha} \in \mathbb{R}^{N+1};\ \boldsymbol{\alpha}=\boldsymbol{\beta}\textbf{\textit{U}}(K,N),\boldsymbol{\beta} \in \Gamma(K),\\[3pt]& {}[\boldsymbol{\beta}]_i \geq 0\ (i \in \mathcal{B}),\ [\boldsymbol{\beta}]_i = 0\ (i \in \mathbb{Z}_0^K\setminus\mathcal{B})\},\end{align*}

where $\Gamma(n)$ ( $n \in \mathbb{Z}^+$ ) is defined in (2.5) and $\textbf{\textit{U}}(K,N)$ is given by

\begin{align*}\textbf{\textit{U}}(K,N)&=\textrm{diag}^*(\textbf{\textit{H}}^{(*,1)}(K;\, N)\textbf{\textit{e}})\begin{pmatrix}\textbf{\textit{I}}\\ (\!-\textbf{\textit{Q}}^{(2,2)}(K,N))^{-1}\textbf{\textit{Q}}^{(2,1)}(K,N)\end{pmatrix}\\&\cdot(\textbf{\textit{I}} - \textbf{\textit{R}}(K,N))^{-1} \textrm{diag}(\textbf{\textit{H}}(N)\textbf{\textit{e}}).\end{align*}

Moreover, for $\mathcal{X} \in \mathcal{S}(K,N)$ , we define $\mathcal{X}^*$ as

\begin{equation*}\mathcal{X}^* = \mathcal{X} \setminus \mathcal{N}_0(K,N).\end{equation*}

Note that

(4.4) \begin{equation}\mathcal{X}^* \in \mathcal{S}(K,N)\ \mbox{ if }\ \mathcal{X} \in \mathcal{S}(K,N),\qquad\mathcal{X}^* = \mathcal{X}\ \mbox{ if }\ \mathcal{X} \in \mathcal{S}^*(K,N).\end{equation}

We then have the following theorem, whose proof is given in Appendix G.

Theorem 4.1. Suppose $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K), \mathcal{J}(K)) \neq \emptyset$ . For any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K),\break \mathcal{J}(K))$ , we have for $\mathcal{X} \in\mathcal{S}(K,N)$ ( $K>N$ ) that

\begin{equation*}\boldsymbol{\pi}(N) \in \mathcal{P}^+(K,N;\,\mathcal{X}^*),\end{equation*}

where $\mathcal{P}^+(K,N;\, \mathcal{X}^*)$ denotes a convex polytope on the first orthant of $\mathbb{R}^{N+1}$ which is given by

(4.5) \begin{align}\mathcal{P}^+(K,N;\, \mathcal{X}^{*})&=\big\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \big[(\textbf{\textit{x}}\ \textbf{\textit{y}})(\!-\textbf{\textit{Q}}^{(1,1)}(K))]_i \geq 0\ (i \in \mathcal{X}^*),\nonumber\\[3pt] &\quad\,\big[(\textbf{\textit{x}}\ \textbf{\textit{y}})(\!-\textbf{\textit{Q}}^{(1,1)}(K))]_i = 0\ (i \in \mathbb{Z}_0^K \setminus \mathcal{X}^{*}),\nonumber\\[3pt] &\quad \textbf{\textit{x}}\textbf{\textit{e}}=1,\ \textbf{\textit{y}}\geq\textbf{0}\big\}\end{align}

(4.6) \begin{align}\hspace*{40pt}&=\{\textbf{\textit{x}} \in \mathbb{R}^{N+1};\ \textbf{\textit{x}} = \boldsymbol{\alpha}\overline{\textbf{\textit{H}}}(N),\boldsymbol{\alpha} \in \Gamma(K,N;\, \mathcal{X}^*)\}.\end{align}

In particular,

\begin{equation*}\boldsymbol{\pi}(N) \in \textrm{ri}\, \mathcal{P}^+(K,N;\,\mathcal{X}^*) \ \mbox{ if }\ \mathcal{X}^* \in \mathcal{S}^*(K,N).\end{equation*}

Lemma 4.1. For Markov chains in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K),\mathcal{J}(K))$ with $\mathcal{X}_A,\mathcal{X}_B \in \mathcal{S}(K,N)$ , we consider the first passage times $F(\mathcal{X}_A^*)$ , $F(\mathcal{X}_B^*)$ , and $F(\mathbb{Z}_0^N)$ . If the statements

\begin{equation*}F(\mathcal{X}_A^*) \leq F(\mathcal{X}_B^*)\ \mbox{ given that }\ X(0) \in \mathbb{Z}_{K+1}^{\infty}\end{equation*}

and

(4.7) \begin{equation}F(\mathcal{X}_B^*) \leq F(\mathbb{Z}_0^N)\ \mbox{ given that }\ X(0) \in \mathcal{X}_A^*,\end{equation}

hold sample-path-wise, we have

\begin{equation*}\mathcal{P}(K,N;\, \mathcal{X}_A^*) \subseteq \mathcal{P}(K,N;\, \mathcal{X}_B^*).\end{equation*}

The proof of Lemma 4.1 is given in Appendix H. By definition, $\widetilde{\mathcal{J}}(K,N) \in \mathcal{S}^*(K,N)$ , and $\mathcal{P}^+(K,N;\,\widetilde{\mathcal{J}}(K,N))$ is identical to $\widetilde{\mathcal{P}}^+(K,N)$ in (3.24). Recall that $\widetilde{\mathcal{J}}(K,N) \subseteq \mathbb{Z}_0^N$ . Therefore, for any $\mathcal{X}\in \mathcal{S}(K,N)$ , $F(\mathcal{X}) \leq F(\widetilde{\mathcal{J}}(K,N))$ holds sample-path-wise, given $X(0) \in \mathbb{Z}_{K+1}^{\infty}$ . On the other hand, $\mathcal{J}(K) \in\mathcal{S}(K,N)$ , and each state in $\mathcal{J}(K)$ is reachable from some states in $\mathbb{Z}_{K+1}^{\infty}$ by direct transitions. Note here that

(4.8) \begin{equation}\mathcal{J}^*(K)=\mathcal{J}(K) \setminus \mathcal{N}_0(K,N)=\mathcal{J}(K) \setminus \mathcal{N}_0^{(3)}(K,N).\end{equation}

We thus have $F(\mathcal{J}^*(K)) \leq F(\mathcal{X}^*)$ sample-path-wise, given $X(0) \in \mathbb{Z}_{K+1}^{\infty}$ . The corollary below follows from Theorem 4.1 and the above observations.

Corollary 4.1. Among (K, N)-skip-free sets, $\widetilde{\mathcal{J}}(K,N)$ in (3.19) gives a maximum convex polytope, i.e.,

\begin{equation*}\mathcal{P}^+(K,N;\, \mathcal{X}^*) \subseteq \mathcal{P}^+(K,N;\,\widetilde{\mathcal{J}}(K,N)),\quad\mathcal{X} \in \mathcal{S}(K,N).\end{equation*}

On the other hand, among (K, N)-skip-free sets, $\mathcal{J}^*(K)$ gives a minimum convex polytope, i.e.,

\begin{equation*}\mathcal{P}^+(K,N;\,\mathcal{J}^*(K)) \subseteq \mathcal{P}^+(K,N;\, \mathcal{X}^*),\quad\mathcal{X} \in \mathcal{S}(K,N).\end{equation*}

Note here that $\mathcal{J}^*(K)$ is not proper in general. We thus consider a proper (K, N)-skip-free set that gives the minimum convex polytope $\mathcal{P}^+(K,N;\,\mathcal{J}^*(K))$ . Specifically, we introduce a subset $\mathcal{D}(K,N)$ of $\mathcal{J}(K)$ , which is generated by the following procedure.

Procedure 4.1. ([Reference Nagamochi9].)

1. (i) We obtain a directed graph $G^*(K,N)$ from G(K, N) in (4.2) by removing all incoming edges to nodes in $\mathcal{J}(K)$ .

2. (ii) We then find the subset $\mathcal{D}(K,N)$ of nodes in $\mathcal{J}(K)$ from which node t is reachable in $G^*(K,N)$ .

Note that Step (ii) can be performed with O(K) operations, by considering reverse paths from node t to node s in the graph $G^*(K,N)$ .

The proof of Lemma 4.2 is given in Appendix I.

Lemma 4.3. Suppose $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K), \mathcal{J}(K)) \neq \emptyset$ . For any Markov chain in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K),\break \mathcal{J}(K))$ ( $K>N$ ), we have

\begin{equation*}\mathcal{P}^+(K,N;\,\mathcal{D}(K,N)) = \mathcal{P}^+(K,N;\,\mathcal{J}^*(K)),\quad K,N\in\mathbb{Z}^+,\ K>N,\end{equation*}

where $\mathcal{J}^*(K)$ is given by (4.8).

Proof. Since $\mathcal{D}(K,N) \in \mathcal{S}^*(K,N)$ , we have $\mathcal{D}^*(K,N) = \mathcal{D}(K,N)$ from (4.4). It then follows from Remark 4.2 and $\mathcal{D}(K,N) \subseteq \mathcal{J}(K)$ that

\begin{equation*}\mathcal{P}^+(K,N;\, \mathcal{D}(K,N)) = \mathcal{P}^+(K,N;\, \mathcal{D}^*(K,N)) \subseteq\mathcal{P}^+(K,N;\, \mathcal{J}^*(K)).\end{equation*}

On the other hand, it follows from Lemma 4.2 that $F(\mathcal{J}^*(K)) \leq F(\mathcal{D}(K,N))$ if $X(0) \in\mathbb{Z}_{K+1}^{\infty}$ and $F(\mathcal{D}(K,N)) \leq F(\mathbb{Z}_0^N)$ if $X(0) \in\mathcal{J}^*(K)$ . We thus have $\mathcal{P}^+(K,N;\, \mathcal{J}^*(K)) \subseteq \mathcal{P}^+(K,N;\,\mathcal{D}(K,N))$ from Lemma 4.1, which completes the proof. □

The following theorem shows that the minimum convex polytope $\mathcal{P}^+(K,N;\, \mathcal{D}(K,N))$ is tight in $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K), \mathcal{J}(K))$ .

The proof of Theorem 4.2 is given in Appendix J. As shown in the proof, if $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K), \mathcal{J}(K)) \neq \emptyset$ and $\textbf{\textit{x}} \in\textrm{ri}\, \mathcal{P}^+(K,N;\,\mathcal{D}(K,N))$ , we have $\textbf{\textit{x}} > \textbf{0}$ . The following corollary comes from the fact that $\mathcal{P}^+(K,N;\ \mathcal{D}(K,N))$ is a convex polytope spanned by $\overline{\textbf{\textit{h}}}_i^{(*,1)}(K;\, N)$ for $i \in\mathcal{D}(K,N)$ (cf. (H.1)), where $\overline{\textbf{\textit{h}}}_i^{(*,1)}(K;\, N)$ ( $i \in \mathbb{Z}_0^K$ ) denotes the ith normalized row vector of $\textbf{\textit{H}}^{(*,1)}(K;\, N)$ in (4.1).

Corollary 4.2. Suppose $\mathcal{M}(\textbf{\textit{Q}}^{(1,1)}(K), \mathcal{J}(K)) \neq \emptyset$ . For an arbitrary probability vector $\textbf{\textit{x}} \in \Gamma(N)$ , we have

\begin{equation*}\| \textbf{\textit{x}} - \boldsymbol{\pi}(N) \|_1\leq\max_{i \in \mathcal{D}(K,N)}\| \textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i^{(*,1)}(K;\, N) \|_1.\end{equation*}

Furthermore, if $\textbf{\textit{x}} \in \mathcal{P}^+(K,N;\, \mathcal{D}(K,N))$ , we have

\begin{align*}\max_{i \in \mathcal{D}(K,N)}\| \textbf{\textit{x}} - \overline{\textbf{\textit{h}}}_i^{(*,1)}(K;\, N) \|_1&\leq\max_{i,j \in \mathcal{D}(K,N)}\| \overline{\textbf{\textit{h}}}_j^{(*,1)}(K;\, N)-\overline{\textbf{\textit{h}}}_i^{(*,1)}(K;\, N) \|_1,\\& \qquad\qquad\qquad\qquad\qquad\qquad\textbf{\textit{x}} \in \mathcal{P}^+(K,N;\, \mathcal{D}(K,N)).\end{align*}

Example 4.2. (Example 2.1 continued.) Consider $\textbf{\textit{Q}}$ in Example 2.1 of Section 2.3. Note that $\mathcal{J}(N)=\{0,N\}$ and $\mathcal{J}(K)= \mathcal{J}^*(K) = \mathcal{D}(K,N) = \{0,K\}$ . We set $q_{i,j} = \lambda_i b_{j-i}$ ( $i \in \mathbb{Z}^+, j > i$ ), $q_{i,i-1} = \mu_i$ ( $i \in \mathbb{Z}^+ \setminus\{0\}$ ), and $q_{i,0} = \gamma_i$ ( $i \in \mathbb{Z}^+ \setminus \{0,1\}$ ), where

\begin{gather*}\lambda_i = 2 - \frac{1}{i+1}\quad (i \in \mathbb{Z}^+),\qquad \hspace*{-12pt}b_i = \frac{1}{2^i}\quad (i \in \mathbb{Z}^+ \setminus \{0\}),\\ \mu_i = \frac{i}{10}\quad (i \in \mathbb{Z}^+ \setminus \{0\}),\qquad\gamma_i = \frac{\lambda_i}{i}\quad (i \in \mathbb{Z}^+ \setminus \{0,1\}).\end{gather*}

Table 1 shows the worst-case error bound

\begin{equation*}\max_{i,j \in \mathcal{D}(K,N)} \| \overline{\textbf{\textit{h}}}_j^{(*,1)}(K;\, N) -\overline{\textbf{\textit{h}}}_i^{(*,1)}(K;\, N) \|_1 = \|\overline{\textbf{\textit{h}}}_0^{(*,1)}(K;\, N) - \overline{\textbf{\textit{h}}}_K^{(*,1)}(K;\,N) \|_1\end{equation*}

of Corollary 4.2, where $N=50$ , and the result for $K=N$ indicates the worst-case error bound

\begin{equation*}\max_{i,j \in \mathcal{J}(N)} \| \overline{\textbf{\textit{h}}}_j(N) - \overline{\textbf{\textit{h}}}_i(N) \|_1 =\|\overline{\textbf{\textit{h}}}_0(N) - \overline{\textbf{\textit{h}}}_N(N) \|_1\end{equation*}

of Corollary 2.3. We observe that the worst-case error bound steadily decreases as K increases and that if $K=150$ , any probability vector $\textbf{\textit{x}} \in \textrm{ri}\, \mathcal{P}^+(K,N;\, \mathcal{D}(K,N))$ is a good approximation to $\boldsymbol{\pi}(N)$ in this specific case.

Table 1.

The worst-case error bounds in Example 4.2 ( $N=50$ ).