For the analysis of complex Markov chains with large state spaces, decomposition and aggregation techniques are used as tools that reduce the complexity of the solution. The general idea behind decomposition and aggregation is to decompose (divide) the Markov chain in independent subchains which can be solved separately, and then aggregate (combine) the results back together. If a Markov chain can be divided into independent subchains then this Markov chain is completely decomposable. In practice, it is unusual to find completely decomposable Markov chains. However, there are cases where the condition of independent subchains almost holds. These type of Markov chains are called nearly completely decomposable.
A Markov chain is nearly completely decomposable if its state space
can be partitioned into subsets such that within the same
subset, the states interact strongly with one another,
i.e., are strongly connected, while between different subsets the states
interact loosely with one another, i.e., are loosely connected. For a
CTMC,
this means that the cumulative rate between states of the same subset
is much higher than the cumulative rate between the states of different
subsets [27]. The fundamental formal foundation of
decomposition methods for the steady state analysis of queueing systems
is due to Simon and Ando [96].
Generally speaking, aggregation and decomposition techniques yield approximate solutions. If they apply to the nearly completely decomposable Markov chains, the relative error can be maintained under a given small constant. If the conditions of nearly decomposable Markov chains do not hold, then the error introduced in the results is considerably large, with the notable exception of product-form queueing networks where the aggregation techniques yield exact solutions. The value of the decomposition and aggregation methodology is two-fold [26]: