The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem. (English) Zbl 0953.60064
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.
Reviewer: E.Kazarovitsky (Kyïv)
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 05C05 | Trees |
| 60G40 | Stopping times; optimal stopping problems; gambling theory |
References:
| [1] | Sheskin, T. J., A Markov partitioning algorithm for computing steady-state probabilities, Oper. Res., 33, 228-535 (1985) · Zbl 0569.90092 |
| [2] | Grassmann, W. K.; Taksar, M. I.; Heyman, D. P., Regenerative analysis and steady-state distributions for Markov chains, Oper. Res., 33, 1107-1116 (1985) · Zbl 0576.60083 |
| [3] | Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1960), Van Nostrand-Reinhold: Van Nostrand-Reinhold Princeton · Zbl 0112.09802 |
| [4] | Kemeny, J. G.; Snell, J. L.; Knapp, A. V., Denumerable Markov Chains (1976), Springer-Verlag: Springer-Verlag New York · Zbl 0149.13301 |
| [5] | Isaacson, D. L.; Madsen, R. W., Markov Chains: Theory and Applications (1976), Wiley: Wiley New York · Zbl 0332.60043 |
| [6] | (Meyer, C. D.; Plemmons, R. J., Linear Algebra, Markov Chains, and Queueing models. Linear Algebra, Markov Chains, and Queueing models, IMA Vol. Math. Appl., 48 (1993), Springer-Verlag: Springer-Verlag New York) |
| [7] | Heyman, D. P., Accurate computation of the fundamental matrix of a Markov chain, SIAM J. Matrix Anal. Appl., 16, 954-963 (1995) · Zbl 0823.60056 |
| [8] | Kohlas, J., Numerical computation of mean passage times and absorption probabilities in Markov and semi-markov models, Z. Operat. Res., 30, A197-A207 (1986) · Zbl 0618.90094 |
| [9] | Kumar, S.; Grassmann, W. K.; Billinton, R., A stable algorithm to calculate steady-state probability and frequency of a Markov system, IEEE Trans. Reliability, R36, 58-62 (1987) · Zbl 0654.60072 |
| [10] | Heyman, D. P., Further comparisons of direct methods for computing stationary distributions of Markov chains, SIAM J. Algebraic Discrete Methods, 8, 226-232 (1987) · Zbl 0625.65150 |
| [11] | Heyman, D. P.; Reeves, A., Numerical solution of linear equations arising in Markov chain models, ORSA J. Comput., 1, 52-60 (1989) · Zbl 0757.65156 |
| [12] | Lal, R.; Bhat, U. N., Reduced systems algorithms for Markov chains, Management Sci., 34, 1202-1220 (1988) · Zbl 0678.60094 |
| [13] | Grassmann, W. K.; Heyman, D. P., Equilibrium distribution of block-structured Markov chains with repeating rows, J. Appl. Probab., 27, 557-576 (1990) · Zbl 0716.60076 |
| [14] | Heyman, D. P., A direct algorithm for computing the stationary distribution of a \(p\)-cyclic Markov chain, Linear Algebra, Markov Chains, and Queueing Models. Linear Algebra, Markov Chains, and Queueing Models, IMA Vol. Math. Appl., 48 (1993), Springer-Verlag: Springer-Verlag New York, p. 205-209 · Zbl 0789.65104 |
| [15] | Freidlin, M. I.; Wentzell, A. D., Perturbations of Stochastic Dynamic Systems (1984), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0522.60055 |
| [16] | O’Cinneide, C. A., Entrywise perturbation theory and error analysis for Markov chains, Numer. Math., 65, 109-120 (1993) · Zbl 0804.65145 |
| [17] | C. Alexopoulos, A. El-Tannir, and, R. Serfozo, Partition-reversible Markov processes, preprint, 1997.; C. Alexopoulos, A. El-Tannir, and, R. Serfozo, Partition-reversible Markov processes, preprint, 1997. · Zbl 0979.90122 |
| [18] | Sheskin, T. J., Computing the fundamental matrix for a reducible Markov chain, Math. Mag., 68, 393-398 (1995) · Zbl 0857.60066 |
| [19] | I. M. Sonin, Two simple theorems in the problems of optimal stopping, in, Proceedings, INFORMS Appl. Probab. Conf, Atlanta, GA, 1995.; I. M. Sonin, Two simple theorems in the problems of optimal stopping, in, Proceedings, INFORMS Appl. Probab. Conf, Atlanta, GA, 1995. |
| [20] | I. M. Sonin, Two simple theorems in the problems of optimal stopping and the Elimination Algorithm, preprint, 1997.; I. M. Sonin, Two simple theorems in the problems of optimal stopping and the Elimination Algorithm, preprint, 1997. |
| [21] | Chow, Y. S.; Robbins, H.; Sigmund, D., Great Expectations: The Theory of Optimal Stopping (1971), Houghton Mifflin: Houghton Mifflin New York · Zbl 0233.60044 |
| [22] | Shiryayev, A. N., Optimal Stopping Rules (1978), Springer-Verlag: Springer-Verlag New York · Zbl 0391.60002 |
| [23] | Bogart, K., Introductory Combinatorics (1990), Harcourt Brace Jovanovich: Harcourt Brace Jovanovich New York · Zbl 0956.05001 |
| [24] | Diaconis, P.; Strook, D., Geometric bounds for eigenvalues of Markov chains, Ann. of Appl. Probab., 1, 36-61 (1991) · Zbl 0731.60061 |
| [25] | (Chen, Wai-Kai, The Circuits and Filters. Handbook (1995), CRC Press: CRC Press Boca Raton) · Zbl 0925.93001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
