The State Reduction and Related Algorithms and Their Applications to the Study of Markov Chains, Graph Theory, and the Optimal Stopping Problem
✍ Scribed by Isaac Sonin
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 221 KB
- Volume
- 145
- Category
- Article
- ISSN
- 0001-8708
No coin nor oath required. For personal study only.
✦ Synopsis
We discuss the State ReductionÂGTH (Grassmann, Taksar, Heyman) algorithm for recursively finding invariant measure. We demonstrate the relationship between this algorithm and the Freidlin Wentzell ``tree decomposition'' approach to study the characteristics of Markov chains. The structure of the State ReductionÂGTH algorithm suggests the natural idea for finding the distribution of a Markov chain at the moment of first visit to a given set, and some similar characteristics. We study the possible range of such algorithms. We also present a new algorithm for solving the classical problem of optimal stopping of a Markov chain based on a similar idea of sequential elimination of some states. We give shorter and more transparent proofs of some previously known results, and improve the bounds of Freidlin Wentzell in the perturbation theory of Markov chains. Some applications to graph theory are also discussed.