6.3 GI/G/1 solution (High-level idea)

In this section, we present the high-level idea of our algorithm and outline the attributes of the structure of the CTMCs that we can solve. We observe that the pattern of interaction among states of a CTMC with infinitesimal generator ${\mathbf{Q}}$ given by Eq.(6.1) is the union of the patterns for GI/M/1-type and M/G/1-type processes, thus it is more general than either. Based on this observation, we propose the following solution steps:

1. We partition the union of the level sets ${\cal{S}}= \bigcup_{j=1}^{\infty}{\cal{S}}^{(j)}$, into two disjoint sets ${\cal{U}}$ and ${\cal{L}}$ such that ${\cal{U}}$ captures the GI/M/1-type behavior of ${\mathbf{Q}}$ and ${\cal{L}}$ captures the M/G/1-type behavior of ${\mathbf{Q}}$. We elaborate on the exact meaning of this statement in Section 6.4.
2. We use the well-known concept of stochastic complementation [61] to define two new processes (stochastic complements), one containing all states in ${\cal{U}}$ (plus a finite number of states ${\cal{G}}^+_g \subseteq {\cal{S}}^{(0)}$) and one containing all states in ${\cal{L}}$ (plus a finite number of states ${\cal{G}}^-_g \subseteq {\cal{S}}^{(0)}$).
3. We solve each new process using well-known techniques, and obtain the conditional stationary probabilities for all states in ${\cal{U}}\cup {\cal{G}}^+_g$ (or ${\cal{L}}\cup {\cal{G}}^-_g$) given that the original process ${\mathbf{Q}}$ is in ${\cal{U}}\cup {\cal{G}}^+_g$ (or ${\cal{L}}\cup {\cal{G}}^-_g$, respectively). In particular, the stochastic complement of the set ${\cal{U}}\cup {\cal{G}}^+_g$ is a GI/M/1-type process that is solved with the matrix geometric method [67] and the stochastic complement^6.2 of ${\cal{L}}\cup {\cal{G}}^-_g$ is an M/G/1-type process that is solved using the matrix analytic method [69,47].
4. Finally, we ``couple'' the two solutions in order to scale back the conditional stationary probabilities of all states in ${\cal{U}}\cup {\cal{G}}^+_g$ and ${\cal{L}}\cup {\cal{G}}^-_g$ and obtain the stationary probabilities of the original process.

Figure 6.1 illustrates the main structure of the CTMC required by the above steps, while the corresponding block structure of ${\mathbf{Q}}$ is shown in Table 6.1. We observe a ``two-level'' repetitive structure, where each level set ${\cal{S}}^{(j)}$, $j \ge 1$, is partitioned into two disjoint classes denoted ${\cal{U}}^{(j)}$ (for ``upper'') and ${\cal{L}}^{(j)}$ (for ``lower''). For the moment, we opt not to discuss any partitioning of the boundary portion of the process ${\cal{S}}^{(0)}$. Let ${\cal{U}}= \bigcup_{j=1}^{\infty} {\cal{U}}^{(j)}$ and ${\cal{L}}= \bigcup_{j=1}^{\infty} {\cal{L}}^{(j)}$. The following list summarizes the interactions within each set and across the two sets.

• Within set ${\cal{U}}$, forward transitions are allowed from any ${\cal{U}}^{(j)}$ only toward the next level ${\cal{U}}^{(j+1)}$. Backward transitions are allowed from set ${\cal{U}}^{(j)}$ to any lower level sets ${\cal{U}}^{(k)}$, $k < j$.
• Within set ${\cal{L}}$, forward transitions are allowed from any ${\cal{L}}^{(j)}$ toward any higher level ${\cal{L}}^{(k)}$, $k > j$. Backward transitions are allowed from set ${\cal{L}}^{(j)}$ to ${\cal{L}}^{(j-1)}$ only.
• Arbitrary local transitions (not shown) are allowed within each ${\cal{U}}^{(j)}$ and ${\cal{L}}^{(j)}$.
• Transitions from ${\cal{U}}^{(j)}$ to any ${\cal{L}}^{(k)}$, $k \ge 1$ are allowed.
• There is strictly no interaction from ${\cal{L}}$ toward ${\cal{U}}$ (except, of course, through the boundary portion ${\cal{S}}^{(0)}$).
• There is a special ``gate'' state $g$ in ${\cal{S}}^{(0)}$ such that any path from ${\cal{L}}$ to ${\cal{U}}$ must visit state $g$. In practice, such a gate might exist in ${\cal{S}}^{(1)}$ but not in ${\cal{S}}^{(0)}$; in this case, we simply redefine a new ${\cal{S}}^{(0)}$ as the union of the original sets ${\cal{S}}^{(0)}$ and ${\cal{S}}^{(1)}$ and ``shift all levels to the left by one''.

The gated structure for the interaction of ${\cal{U}}$ and ${\cal{L}}$ is critical for our algorithm, as it allows us to apply stochastic complementation in a special setting (see Subsection 2.8.2). Furthermore, in conjunction with the upper/lower interaction between sets ${\cal{U}}$ and ${\cal{L}}$, it ensures that (a) the stochastic complement of the upper set of states is a GI/M/1-type CTMC and (b) the pseudo stochastic complement of the lower set of states is a M/G/1-type CTMC. As it will be explained in Subsection. 6.4, the actual algorithm can recursively apply to chains where multiple upper or lower sets are identified. We elaborate on this topic in Subsection 6.9.

Figure 6.1: The two-level interaction between states and the gated structure of our CTMC.

Table: The nonzero pattern in our matrix ${\mathbf{Q}}$.

	${\cal{U}}^{(0)}$	$\overline{{\cal{L}}}^{(0)}$	${\cal{U}}^{(1)}$	${\cal{L}}^{(1)}$	${\cal{U}}^{(2)}$	${\cal{L}}^{(2)}$	${\cal{U}}^{(3)}$	${\cal{L}}^{(3)}$	$\cdots$
${\cal{U}}^{(0)}$	$\widehat{{\mathbf{L}}}^{(0)}_{{\cal{U}}{\cal{U}}}$	$\widehat{{\mathbf{L}}}^{(0)}_{{\cal{U}}\overline{{\cal{L}}}}$	$\widehat{{\mathbf{F}}}^{(1)}_{{\cal{U}}{\cal{U}}}$	$\widehat{{\mathbf{F}}}^{(1)}_{{\cal{U}}{\cal{L}}}$		$\widehat{{\mathbf{F}}}^{(2)}_{{\cal{U}}{\cal{L}}}$		$\widehat{{\mathbf{F}}}^{(3)}_{{\cal{U}}{\cal{L}}}$
$\overline{{\cal{L}}}^{(0)}$		$\widehat{{\mathbf{L}}}^{(0)}_{\overline{{\cal{L}}}\overline{{\cal{L}}}}$		$\widehat{{\mathbf{F}}}^{(1)}_{\overline{{\cal{L}}}{\cal{L}}}$		$\widehat{{\mathbf{F}}}^{(2)}_{\overline{{\cal{L}}}{\cal{L}}}$		$\widehat{{\mathbf{F}}}^{(3)}_{\overline{{\cal{L}}}{\cal{L}}}$
${\cal{U}}^{(1)}$	$\widehat{{\mathbf{B}}}^{(1)}_{{\cal{U}}{\cal{U}}}$	$\widehat{{\mathbf{B}}}^{(1)}_{{\cal{U}}\overline{{\cal{L}}}}$	$\L ^{(1)}_{{\cal{U}}{\cal{U}}}$	$\L ^{(1)}_{{\cal{U}}{\cal{L}}}$	${\mathbf{F}}^{(1)}_{{\cal{U}}{\cal{U}}}$	${\mathbf{F}}^{(1)}_{{\cal{U}}{\cal{L}}}$		${\mathbf{F}}^{(2)}_{{\cal{U}}{\cal{L}}}$
${\cal{L}}^{(1)}$		$\widehat{{\mathbf{B}}}^{(1)}_{{\cal{L}}\overline{{\cal{L}}}}$		$\L ^{(1)}_{{\cal{L}}{\cal{L}}}$		${\mathbf{F}}^{(1)}_{{\cal{L}}{\cal{L}}}$		${\mathbf{F}}^{(2)}_{{\cal{L}}{\cal{L}}}$
${\cal{U}}^{(2)}$	$\widehat{{\mathbf{B}}}^{(2)}_{{\cal{U}}{\cal{U}}}$	$\widehat{{\mathbf{B}}}^{(2)}_{{\cal{U}}\overline{{\cal{L}}}}$	${\mathbf{B}}^{(1)}_{{\cal{U}}{\cal{U}}}$	${\mathbf{B}}^{(1)}_{{\cal{U}}{\cal{L}}}$	$\L _{{\cal{U}}{\cal{U}}}$	$\L _{{\cal{U}}{\cal{L}}}$	${\mathbf{F}}^{(1)}_{{\cal{U}}{\cal{U}}}$	${\mathbf{F}}^{(1)}_{{\cal{U}}{\cal{L}}}$
${\cal{L}}^{(2)}$				$\widehat{{\mathbf{B}}}^{(1)}_{{\cal{L}}{\cal{L}}}$		$\L _{{\cal{L}}{\cal{L}}}$		${\mathbf{F}}^{(1)}_{{\cal{L}}{\cal{L}}}$
${\cal{U}}^{(3)}$	$\widehat{{\mathbf{B}}}^{(3)}_{{\cal{U}}{\cal{U}}}$	$\widehat{{\mathbf{B}}}^{(3)}_{{\cal{U}}\overline{{\cal{L}}}}$	${\mathbf{B}}^{(2)}_{{\cal{U}}{\cal{U}}}$	${\mathbf{B}}^{(2)}_{{\cal{U}}{\cal{L}}}$	${\mathbf{B}}^{(1)}_{{\cal{U}}{\cal{U}}}$	${\mathbf{B}}^{(1)}_{{\cal{U}}{\cal{L}}}$	$\L _{{\cal{U}}{\cal{U}}}$	$\L _{{\cal{U}}{\cal{L}}}$
${\cal{L}}^{(3)}$						$\widehat{{\mathbf{B}}}^{(1)}_{{\cal{L}}{\cal{L}}}$		$\L _{{\cal{L}}{\cal{L}}}$