3.3 Generalization: geometric solution for the GI/M/1 processes

We generalize the finding in the previous example by considering a GI/M/1-queue with infinitesimal generator ${\mathbf{Q}}_{GI/M/1}$ similarly to the proof given in [45]. To evaluate the relation between $\mbox{\boldmath {$\pi$}}^{(i-1)}$ and $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i > 1$, we construct the stochastic complement of the states in ${\cal{A}}= \cup_{j=0}^i {\cal{S}}^{(j)}$ ( $\overline{{\cal{A}}}={\cal{S}}- {\cal{A}}$). The stochastic complement of states in ${\cal{A}}$ has an infinitesimal generator defined by the following relation

$$\overline{{\mathbf{Q}}} = {\mathbf{Q}}[{\cal{A}}, {\cal{A}}]... ...)^{-1} \cdot {\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}],$$

where

$$\begin{array}{c c} {\mathbf{Q}}[{\cal{A}}, {\cal{A}}] = \lef... ...dots & \vdots & \vdots & \ddots \end{array}\right]. \end{array}$$ (3.15)

Observe that ${\mathbf{Q}}[\overline{{\cal{A}}}, \overline{{\cal{A}}}]$ is the same matrix for any $i > 1$. We define its inverse to be as follows

$$(- {\mathbf{Q}}[\overline{{\cal{A}}}, \overline{{\cal{A}}}])... ...dots & \vdots & \vdots & \vdots & \vdots \end{array}\right] .$$ (3.16)

From the special structure of ${\mathbf{Q}}[{\cal{A}}, \overline{{\cal{A}}}]$ we conclude that the second term in the summation that defines $\overline{{\mathbf{Q}}}$ is a matrix with all block entries equal to zero except the very last block row, whose block entries ${\mathbf{X}}_{j}$ are of the form:

$${\mathbf{X}}_{j} = {\mathbf{F}}\cdot \sum_{k=0}^{\infty} {\mathbf{A}}_{0,k} \widehat{{\mathbf{B}}}^{(j+1+k)} ~~~~ j = i$$

and

$${\mathbf{X}}_{j} = {\mathbf{F}}\cdot \sum_{k=0}^{\infty} {\mathbf{A}}_{0,k} {\mathbf{B}}^{(j+1+k)}, ~~~~ 0 \leq j < i.$$

Note that ${\mathbf{X}}_{0} = {\mathbf{F}}\cdot \sum_{k=0}^{\infty} {\mathbf{A}}_{0,k} {\mathbf{B}}^{(1+k)}$ which means that ${\mathbf{X}}_{0}$ does not depend on the value of $i > 1$. The infinitesimal generator $\overline{{\mathbf{Q}}}$ of the stochastic complement of states in ${\cal{A}}$ is determined as

$$\begin{array}{c c} \overline{{\mathbf{Q}}}= \left[ \begin{ar... ...{X}}_{1}& \L + {\mathbf{X}}_{0} \end{array}\right]. \end{array}$$ (3.17)

Let $\overline{\mbox{\boldmath {$\pi$}}}$ be the stationary probability vector of the CTMC with infinitesimal generator $\overline{{\mathbf{Q}}}$ and $\mbox{\boldmath {$\pi$}}_{{\cal{A}}}$ the steady-state probability vector of the CTMC of states in ${\cal{A}}$ in the original process, i.e., the process with infinitesimal generator ${\mathbf{Q}}_{GI/M/1}$. There is a linear relation between $\overline{\mbox{\boldmath {$\pi$}}}$ and $\mbox{\boldmath {$\pi$}}_{{\cal{A}}}$ given in the following equation:

$$\overline{\mbox{\boldmath {$\pi$}}} = \frac{\mbox{\boldmath ... ...}}}}{\mbox{\boldmath {$\pi$}}_{{\cal{A}}}\cdot{\mathbf{1}}^T}.$$ (3.18)

Since $\overline{\mbox{\boldmath {$\pi$}}}\overline{{\mathbf{Q}}} = {\mathbf{0}}$, we obtain the following relation

$$\overline{\mbox{\boldmath {$\pi$}}}^{(i)} \cdot (\L + {\math... ...\overline{\mbox{\boldmath {$\pi$}}}^{(i-1)} \cdot {\mathbf{F}}$$

implying:

$$\mbox{\boldmath {$\pi$}}^{(i)} \cdot (\L + {\mathbf{X}}_{0}) = -\mbox{\boldmath {$\pi$}}^{(i-1)} \cdot {\mathbf{F}}.$$

The above equation holds for any $i > 1$, because their matrix coefficients do not depend on $i$. By applying it recursively over all vectors $\mbox{\boldmath {$\pi$}}^{(i)}$ for $i > 1$, we obtain the following geometric relation

$$\mbox{\boldmath {$\pi$}}^{(i)} = \mbox{\boldmath {$\pi$}}^{(1)} \cdot {\mathbf{R}}^{i-1} ~~~~\forall~ i \geq 1.$$

Matrix ${\mathbf{R}}$, the geometric coefficient, has an important probabilistic interpretation: the entry $(k,l)$ of ${\mathbf{R}}$ is the expected time spent in the state $l$ of ${\cal{S}}^{(i)}$, before the first visit into ${\cal{S}}^{(i-1)}$, expressed in time unit $\Delta^{i}$, given the starting state is $k$ in ${\cal{S}}^{(i-1)}$. $\Delta^{i}$ is the mean sojourn time in the state $k$ of ${\cal{S}}^{(i-1)}$ for $i \geq 2$ [67, pages 30-35].