State Space Decomposition for Large Markov Chains

This paper discusses various approaches for decomposing large Markov chains in a way that facilitates the use of aggregation type algorithms and increases the efficiency of such methods. For a Markov chain defined on state space N = {1,…, N} governed by transition probability matrix (t.p.m.)P, we are interesetd in finding the stationary distribution π, satisfying π T = π T , with π > 0, π T e =1, where e is the vector containing all ones. Agggregation disaggregation (A/D) algorithms are based on a decomposition of the state space N into smaller groups of states $$\mathcal{N} = \cup _{{m = 1}}^{M}L\left( m \right);$$ L(m) ∩ L(n) = Ø for m ≠ n. For an approximation π 1 of π, one defines two mappings Y: R N → R M (typically based on π 1) and E: R M → R N , and an aggregate matrix A = Y P E. In the aggregation step one finds a probability vector γ that solves the aggregated system γ T = γ T A. In the disaggregation step, one assigns a conditional probability vector yL(m) to the states in lump L(m). This may be achieved by constructing a new Markov chain on L(m) representing flow within L(m) as well as flow to and from the other sets. A new approximation of it is then obtained by setting π 2:L(m) = γ m y L(m)A/D algorithms proceed iteratively, until convergence is reached. Examples of A/D methods for Markov chains include Takahashi’s algorithm [7] and the replacement process algorithm of Sumita and Rieders [6].