The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem

DOI10.1006/aima.1998.1813zbMath0953.60064OpenAlexW1984161223MaRDI QIDQ1304617

Isaac M. Sonin

Publication date: 22 September 1999

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/aima.1998.1813

zbMATH Keywords

spanning treeoptimal stopping timeinvariant distributioncountable Markov chain

Mathematics Subject Classification ID

Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stopping times; optimal stopping problems; gambling theory (60G40)

Related Items (11)

On the multiplicity of Laplacian eigenvalues and Fiedler partitions ⋮ Continue, quit, restart probability model ⋮ Solution of Optimal Stopping Problem Based on a Modification of Payoff Function ⋮ Optimal Stopping of Seasonal Observations and Projection of a Markov Chain ⋮ Hitting time quasi-metric and its forest representation ⋮ Measures of success in a class of evolutionary models with fixed population size and structure ⋮ A generalized Gittins index for a Markov chain and its recursive calculation ⋮ The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields ⋮ Optimal stopping of Markov chains and three abstract optimization problems ⋮ A new approach to the solution of optimal stopping problem in a discrete time ⋮ Parallel computing for Markov chains with islands and ports

Cites Work

• Geometric bounds for eigenvalues of Markov chains
• Entrywise perturbation theory and error analysis for Markov chains
• Partition-Reversible Markov Processes
• Further Comparisons of Direct Methods for Computing Stationary Distributions of Markov Chains
• Equilibrium distribution of block-structured Markov chains with repeating rows
• Technical Note—A Markov Chain Partitioning Algorithm for Computing Steady State Probabilities
• Regenerative Analysis and Steady State Distributions for Markov Chains
• Numerical computation of mean passage times and absorption probabilities in Markov and Semi-Markov models
• A Stable Algorithm to Calculate Steady-State Probability & Frequency of a Markov System
• Reduced System Algorithms for Markov Chains
• Finite Continuous Time Markov Chains
• Numerical Solution of Linear Equations Arising in Markov Chain Models
• Accurate Computation of the Fundamental Matrix of a Markov Chain
• Computing the Fundamental Matrix for a Reducible Markov Chain
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem