6.9 Multiple upper-lower classes

In our exposition, we have restricted ourselves to a single pair of upper and lower sets. Here, we present an extension of our upper-lower aggregation algorithm based on recursion that allows us to deal with multiple upper and lower partitions.

The partition is defined by splitting each ${\cal{S}}^{(j)}$, $j \ge 1$, into $U$ upper sets ${\cal{U}}^{(j)}_t$, $1 \leq t \leq U$, and $L$ lower sets ${\cal{L}}^{(j)}_t$, $1 \leq t \leq L$ consistent with a partition of the set of state indices $\{1,\ldots,n\}$ within a level set ${\cal{S}}^{(j)}$ into $U+L$ classes ${\cal{N}}_1, \ldots, {\cal{N}}_U,{\cal{N}}_{U+1}, \ldots, {\cal{N}}_{U+L}$, that is:

$$\forall j \geq 1, ~~ {\cal{U}}^{(j)}_t = \left\{s^{(j)}_i : i... ...}^{(j)}_t = \left\{s^{(j)}_i : i \in {\cal{N}}_{U+t} \right\}.$$

Let ${\cal{U}}_t = \bigcup_{j=1}^{\infty} {\cal{U}}^{(j)}_t$, ${\cal{U}}^{(j)} = \bigcup_{t=1}^{U} {\cal{U}}^{(j)}_t$, and ${\cal{U}}= \bigcup_{t=1}^{U} {\cal{U}}_t$; analogously, ${\cal{L}}_t = \bigcup_{j=1}^{\infty} {\cal{L}}^{(j)}_t$, ${\cal{L}}^{(j)} = \bigcup_{t=1}^{L} {\cal{L}}^{(j)}_t$, and ${\cal{L}}= \bigcup_{t=1}^{L} {\cal{L}}_t$.

Given that $L$ lower sets and $U$ upper sets exist that satisfy the main conditions, i.e., there are no transitions among sets of the same type (except, of course, through the boundary set), there are transitions only from the upper sets to the lower sets, and communication from the lower sets to the upper sets can occur only through the boundary set ${\cal{S}}^{(0)}$, we can apply Algorithm 6.4 in a recursive manner.

  (Recursive aggregation of ${\mathbf{Q}}$ given $U$ upper and $L$ lower classes)

Step 1: Determine the upper and lower classes in ${\mathbf{Q}}$.
Select one lower set ${\cal{L}}_t$, $1 \le t \le L$ and redefine ${\cal{U}}= \left( \bigcup_{j=1}^{U} {\cal{U}}_j \right) \cup \left( \bigcup_{j=1,j \ne t}^{L} {\cal{L}}_j \right)$ and ${\cal{L}}= {\cal{L}}_t$, so as to obtain a new partition of the state space that consists of only one upper set ${\cal{U}}$ and one lower set ${\cal{L}}$ such that there is a special ``gate'' state $g$ in ${\cal{S}}^{(0)}$ such that all paths from ${\cal{L}}$ to ${\cal{U}}$ must first visit $g$. Sets ${\cal{G}}^+$, ${\cal{G}}^+_g$, ${\cal{G}}^-$, and ${\cal{G}}^-_g$ are defined as in Algorithm 6.4.

If no such partitioning exists, then the algorithm first attempts to solve ${\mathbf{Q}}$ with a known method, if this is not possible then the algorithm exits. Otherwise, the algorithm continues with step 2.

Step 2: Generate and solve the ``upper CTMC''. Using stochastic complementation identify a new CTMC observing the behavior of the original CTMC only in the states ${\cal{G}}^+_g \cup {\cal{U}}$. The infinitesimal generator of the new process is ${\mathbf{Q}}_{{\cal{G}}^+_g \cup {\cal{U}}}$. Observe that the new ``upper'' CTMC is composed by the $U$ upper sets and $L-1$ lower sets of the original partitioning.

Step 2a: If $(L-1) \ge 1$, then call Recursive aggregation of ${\mathbf{Q}}_{{\cal{G}}^+_g \cup {\cal{U}}}$ given $U$ upper and $L-1$ lower classes

Step 2b: If $(L-1) = 0$, i.e., if the new ``upper CTMC'' is composed only of the ``upper'' sets of the original process, then the process defined by ${\mathbf{Q}}_{{\cal{G}}^+_g \cup {\cal{U}}}$ is of the GI/M/1-type. This process can be solved using the matrix geometric method, or by applying stochastic complementation to each of its $U$ sets.

Step 3: Generate and solve the ``lower CTMC''. Same as in Algorithm 6.4.

Step 4: Compute the coupling factors. Same as in Algorithm 6.4.

Step 5: Generate the stationary distribution of the original process. Same as in Algorithm 6.4.

Remarks: We assume that there are $U$ upper sets. Because there is strictly no connection among their infinite parts (except, of course, through the boundary set), applying stochastic complementation to these $U$ sets in the CTMC that results in Step 2b is an easy problem. We observe that the single entry condition must be satisfied for each of the stochastic complements to be solved efficiently, that each stochastic complement results in a process of the GI/M/1-type, and that more than one of the new processes may share the same gate state.

To illustrate the idea of the multiple lower and upper sets, we give an example of applying Algorithm 6.9. The CTMC in Figure 6.3(a) has a gate state $g_d$ which we use to construct the pseudo-stochastic complement of the states in ${\cal{L}}_d$. This is Step 1 of Algorithm 6.9. We proceed with Step 2 of Algorithm 6.9 and construct the stochastic complement of the rest of the CTMC, which by itself is an independent CTMC as shown in Figure 6.3(b). We continue with Step 2a of Algorithm 6.9 and in the new CTMC of Figure 6.3(b) identify a new lower subchain and since Step 2a is satisfied we recursively continue with Step 1 of Algorithm 6.9. The gate state for the second lower subchain is $g_c$. We built the CTMC of the pseudo-stochastic complement (sets in ${\cal{L}}_c$). We go on with Step 2 of Algorithm 6.9 and generate the stochastic complement as shown in Figure 6.3(c). Now the Step 2a of Algorithm 6.9 is not satisfied and we continue with Step 2b by identifying upper sets of the CTMC in Figure 6.3(c). We find the gate states $g_a$ and $g_b$ and built the stochastic complements for the states in ${\cal{L}}_a$ and ${\cal{L}}_b$ respectively as shown in Figure 6.3(d). After solving these two stochastic complements, we can apply the classic aggregation on the sets of the chain in Figure 6.3(c), as shown in Figure 6.3(d). This completes Step 2b of Algorithm 6.9 and we continue to Step 3, namely solving the lower subsets identified in recursive Step 1 of Algorithm 6.9. Since we have computed the conditional probabilities of the whole set of upper states, we can proceed with the solution of the pseudo-stochastic complements. Finally, we can apply Step 4 and Step 5 of Algorithm 6.9 to complete the solution of the given CTMC.

Figure 6.3: Example of a CTMC with two lower and two upper sets.

We close this section with the following observation. Given the stationary probabilities, we can compute various performance measures of interest such as the expected queue length or its higher moments. The performance measures of interest are computed at Step 2 and Step 3 of both Algorithm 6.4 and Algorithm 6.9, where the conditional stationary probabilities of the stochastic complements or the pseudo-stochastic complements are computed and then scaled back according to the coupling factors as defined by Step 4.