State Space Decomposition for Large Markov Chains

Maria Rieders
Additional contact information
Maria Rieders: Northwestern University

Chapter 33 in Computations with Markov Chains, 1995, pp 587-590 from Springer

Abstract: Abstract 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].

Keywords: Markov Chain; Probability Vector; Transition Probability Matrix; Hierarchical Decomposition; Drazin Inverse (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4615-2241-6_33

Ordering information: This item can be ordered from
http://www.springer.com/9781461522416

DOI: 10.1007/978-1-4615-2241-6_33

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().