3.2 Why does a geometric relation hold for QBD processes?

There is a clear intuitive appeal to the fact that a geometric relation holds for QBD processes. In this subsection, we first focus on the reasons for the existence of this relationship via a simple example. Our first example is a QBD process that models an $M/Cox_2/1$ queue. The state transition diagram of the CTMC that models this queue is depicted in Figure 3.1. The state space ${\cal {S}}$ of this CTMC is divided into subsets ${\cal{S}}^{(0)} = \{(0,0)\}$ and ${\cal{S}}^{(i)} = \{(i,1), (i,2)\}$ for $i \geq 1$, implying that the stationary probability vector is also divided in the respective subvectors $\mbox{\boldmath {$\pi$}}^{(0)} = [\mbox{\boldmath {$\pi$}}(0,0)]$ and $\mbox{\boldmath {$\pi$}}^{(i)} = [\mbox{\boldmath {$\pi$}}(i,1),\mbox{\boldmath {$\pi$}}(i,2)]$, for $i \geq 1$.

Figure 3.1: The CTMC modeling an $M/Cox_2/1$ queue.

The block-partitioned infinitesimal generator ${\mathbf{Q}}_{QBD}$ is a infinite block tridiagonal matrix as defined in Eq.(2.18) and its component matrices are:

$$\begin{array}{c c c} \widehat{{\mathbf{L}}}= \left[ -\lambda... ... c} \lambda~&~0\\ 0 ~&~\lambda \end{array}\right]. \end{array}$$ (3.12)

To illustrate the existence of the geometric relationship among the various stationary probability vectors $\mbox{\boldmath {$\pi$}}^{(i)}$, we use the concept of stochastic complementation discussed in Subsection 2.8.2.

Figure 3.2: The CTMC of the stochastic complement of ${\cal {A}}= \cup _{j=0}^{j=i} {\cal {S}}^{(j)}$ of the CTMC modeling an $M/Cox_2/1$ queue.

We partition the state space into two subsets; ${\cal {A}}= \cup _{j=0}^{j=i} {\cal {S}}^{(j)}$ and $\overline{{\cal{A}}} = \cup_{j=i+1}^{\infty} {\cal{S}}^{(j)}$, i.e., a set with finite number of states and a set with an infinite number of states, respectively. The stochastic complement of the states in ${\cal{A}}$ is a new Markov chain that ``skips over'' all states in $\overline{{\cal{A}}}$. This Markov chain includes states in ${\cal{A}}$ only, but all transitions out of ${\cal{S}}^{(i)}$ (i.e., the boundary set) to ${\cal{S}}^{(i+1)}$ (i.e., the first set in $\overline{{\cal{A}}}$) need to be ``folded back'' to ${\cal{A}}$ (see Figure 3.2). This folding introduces a new direct transition with rate $x$ that ensures that the stochastic complement of the states in ${\cal{A}}$ is a stand-alone process. Because of the structure of this particular process, i.e., ${\cal{A}}$ is entered from $\overline{{\cal{A}}}$ only through state $(i,1)$, $x$ is simply equal to $\lambda$ (see Lemma on single entry state in Subsection 2.8.2). Furthermore, because of the repetitive structure of the original chain, this rate does not depend on $i$ (which essentially defines the size of set ${\cal{A}}$).

The steady state probability vector $\overline{\mbox{\boldmath {$\pi$}}} = [\overline{\mbox{\boldmath {$\pi$}}}^{(0)}, \cdots, \overline{\mbox{\boldmath {$\pi$}}}^{(i)}]$ of the stochastic complement of the states in ${\cal{A}}$ relates to the steady state probability $\mbox{\boldmath {$\pi$}}_{{\cal{A}}}$ of the original process with: $\overline{\mbox{\boldmath {$\pi$}}} = \mbox{\boldmath {$\pi$}}_{{\cal{A}}} / \mbox{\boldmath {$\pi$}}_{{\cal{A}}}\cdot {\mathbf{1}}^T$. This implies that if a relation exists between $\overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}$ and $\overline{\mbox{\boldmath {$\pi$}}}^{(i)}$, then the same relation holds for $\mbox{\boldmath {$\pi$}}^{(i-1)}$ and $\mbox{\boldmath {$\pi$}}^{(i)}$.

The flow balance equations for states $(i,1)$ and $(i,2)$ in the stochastic complement of ${\cal{A}}$, are:

$$(0.2\mu + 0.8 \mu) \overline{\mbox{\boldmath {$\pi$}}}^{(i)}... ...-1)}[1] + \lambda\overline{\mbox{\boldmath {$\pi$}}}^{(i)}[2],$$

$$(\gamma + \lambda) \overline{\mbox{\boldmath {$\pi$}}}^{(i)}... ...-1)}[2] + 0.8\mu \overline{\mbox{\boldmath {$\pi$}}}^{(i)}[1],$$

which can further be expressed as:

$$(- \mu \overline{\mbox{\boldmath {$\pi$}}}^{(i)}[1] + \lambd... ...2]) = -\lambda \overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}[1],$$

$$(0.8\mu \overline{\mbox{\boldmath {$\pi$}}}^{(i)}[1] - (\gam... ...2]) = -\lambda \overline{\mbox{\boldmath {$\pi$}}}^{(i-1)}[2].$$

This last set of equations leads us to the following matrix equation

$$\left[\overline{\mbox{\boldmath {$\pi$}}}^{(i)}[1], \overlin... ...ray}{c c } \lambda & 0 \\ 0 & \lambda \end{array} \right],$$

which implies that the relation between $\mbox{\boldmath {$\pi$}}^{(i-1)}$ and $\mbox{\boldmath {$\pi$}}^{(i)}$ can be expressed as

$$\mbox{\boldmath {$\pi$}}^{(i)} = \mbox{\boldmath {$\pi$}}^{(i-1)} {\mathbf{R}},$$ (3.13)

where matrix ${\mathbf{R}}$ is defined as

$${\mathbf{R}}= - \left[ \begin{array}{c c } \lambda ~&~ 0 \\... ...ay}{c c } 1 ~&~ 0\\ 1 ~&~ 0 \end{array}\right] \right)^{-1} .$$ (3.14)

Applying Eq.(3.13) recursively, one can obtain the result of Eq.(3.1). Observe that in this particular case an explicit computation of ${\mathbf{R}}$ is possible (i.e., there is no need to compute ${\mathbf{R}}$ [77] via an iterative numerical procedure as in the general case). Explicit computation of ${\mathbf{R}}$ in this example is possible because backward transitions from ${\cal{S}}^{(i)}$ to ${\cal{S}}^{(i-1)}$ are directed toward a single state only. In Subsection 3.8, we give details on the cases when matrix ${\mathbf{R}}$ can be explicitly computed.