The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem
type: Item
instance of: scholarly article
title: The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem
zbMATH Open document ID: 0953.60064
published in: Advances in Mathematics
publication date: 1999-09-22T00:00:00Z
review text: A beautiful survey of results on state reduction algorithm for countable Markov chains is given. Applications of the algorithm for different problems are considered. There are the calculation of invariant distribution and other characteristics of Markov chains, the optimal stopping time problem for Markov chains, estimation of perturbation bounds for Markov chains and some problems in graph theory. The author presents new results in the field and improves the proofs of some known results. Some applications are also considered.
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 60G40
zbMATH DE Number: 1340109
zbMATH Keywords: countable Markov chain
zbMATH Keywords: invariant distribution
zbMATH Keywords: spanning tree
zbMATH Keywords: optimal stopping time
author: Isaac Sonin
reviewed by: Eugene Kozarovitsky
MaRDI profile type: Publication
full work available at URL: aima.1998.1813
OpenAlex ID: W1984161223
cites work: Technical Note—A Markov Chain Partitioning Algorithm for Computing Steady State Probabilities
cites work: Regenerative Analysis and Steady State Distributions for Markov Chains
cites work: Finite Continuous Time Markov Chains
cites work: Q5528211
cites work: Q4098444
cites work: Accurate Computation of the Fundamental Matrix of a Markov Chain
cites work: Numerical computation of mean passage times and absorption probabilities in Markov and Semi-Markov models
cites work: A Stable Algorithm to Calculate Steady-State Probability & Frequency of a Markov System
cites work: Further Comparisons of Direct Methods for Computing Stationary Distributions of Markov Chains
cites work: Numerical Solution of Linear Equations Arising in Markov Chain Models
cites work: Reduced System Algorithms for Markov Chains
cites work: Equilibrium distribution of block-structured Markov chains with repeating rows
cites work: Q4281304
cites work: Q3672830
cites work: Entrywise perturbation theory and error analysis for Markov chains
cites work: Partition-reversible Markov processes
cites work: Computing the Fundamental Matrix for a Reducible Markov Chain
cites work: Q5641856
cites work: Q4172681
cites work: Q4953862
cites work: Geometric bounds for eigenvalues of Markov chains
cites work: Q4847228
DOI: 10.1006/AIMA.1998.1813
Recommended article: Optimizing steady state Markov chains by state reduction
Recommended article: Reduced System Algorithms for Markov Chains
Recommended article: Reduction techniques for discrete-time Markov chains on totally ordered state space using stochastic comparisons
Recommended article: The complexity of graph-based reductions for reachability in Markov decision processes
Recommended article: Q4234053
Recommended article: State reduction in a Markov decision process
description: scientific article; zbMATH DE number 1340109