2.8.1 Exact aggregation and decomposition

The basic idea behind the aggregation/decomposition is to group states in strongly connected subchains that are loosely connected to each other and:

(a) analyze and solve each subchain as if there is no interaction among them,

(b) analyze the interaction among subchains, ignoring the interaction within each subchain.

The infinitesimal generator matrix ${\mathbf{Q}}_{NCD}$ of nearly decomposable Markov chains should be partitioned in such a way that the off-diagonal elements are very small compared to the elements of the diagonal blocks

$${\mathbf{Q}}_{NCD} = \left[ \begin{array}{c c c c } {\mathbf... ...{N-1,1} & \cdots & {\mathbf{Q}}_{N-1,N-1} \end{array}\right] .$$ (2.26)

The diagonal blocks ${\mathbf{Q}}_{i,i},~\mbox{for}~i=0,...,N-1$, are square with dimension $n_i~i=0,...,N-1$, where $\sum_{i=0}^{N-1} n_i = n$, is the cardinality of the state space ${\cal {S}}$.

The solution follows the steps outlined at the beginning of this subsection. First, we assume that ${\mathbf{Q}}_{NCD}$ is completely decomposable, that is, the off-diagonals blocks in Eq.(2.26) are ${\mathbf{0}}$. We solve the $N$ different Markov chains defined by the diagonal blocks ${\mathbf{Q}}_{i,i},~\mbox{for}~i=0,...,N-1$ in Eq.(2.26). If any of these diagonal blocks is not an infinitesimal generator itself, which is usually the case when ${\mathbf{Q}}_{NCD}$ is nearly completely decomposable, the sum of the probabilities in the off-diagonal blocks is used as a correction factor to the elements of the diagonal blocks of ${\mathbf{Q}}_{NCD}$. This correction process affects the accuracy of the solution.

Let $\mbox{\boldmath {$\alpha$}}^{(i)}$ be the stationary distribution vector obtained by solving the subchain with infinitesimal generator matrix ${\mathbf{Q}}_{i,i}^{*}$^2.7 for $i=0,...,N-1$. The element $\mbox{\boldmath {$\alpha$}}^{(i)} [ j ]$ for $i=0,...,N-1$ and $j=0,...,n_i-1$ is the probability of being in state $j$ of subchain $i$, given that the process finds itself in subchain $i$. We need to compute $\vert\vert{\mathbf{a}}[i] \vert\vert$ for $i=0,...,N-1$, which are the probabilities of being in subchain $i$ for $i=0,...,N-1$, such that we can eliminate the condition factor from the elements of the probability vectors $\mbox{\boldmath {$\alpha$}}^{(i)}$, to construct the stationary probability vector $\mbox{\boldmath {$\pi$}}$ of the original process with infinitesimal generator matrix ${\mathbf{Q}}_{NCD}$. We define an infinitesimal generator matrix ${\mathbf{Q}}_{c}$ with $N \times N$ elements as

$${\mathbf{Q}}_{c} = \left[ \begin{array}{c c c c } q_{0,0} & ... ...N-1,0} & q_{N-1,1} & \cdots & q_{N-1,N-1} \end{array}\right] ,$$ (2.27)

where $q_{i,j} = \mbox{\boldmath {$\alpha$}}^{(i)} {\mathbf{Q}}_{i,j} {\mathbf{1}}^T$ for $i \neq j, i,j=0,...,N-1$. The infinitesimal generator matrix ${\mathbf{Q}}_{c}$ represent a new irreducible CTMC whose stationary distribution ${\mathbf{a}}$ can be computed based on Eq.(2.4.2) [107]. After computing ${\mathbf{a}}$, the stationary distribution $\mbox{\boldmath {$\pi$}}$ of the original process is constructed as $\mbox{\boldmath {$\pi$}}= [ {\mathbf{a}}[ 0 ]\mbox{\boldmath {$\alpha$}}^{(0)},..., {\mathbf{a}}[ N-1 ]\mbox{\boldmath {$\alpha$}}^{(N-1)}]$. The infinitesimal generator ${\mathbf{Q}}_{c}$ is known as the coupling matrix. More details on the coupling matrix and the coupling process are given in the following subsection.