The Markov chain tree theorem in commutative semirings and the state reduction algorithm in commutative semifields. (English) Zbl 1307.15053
Summary: We extend the Markov chain tree theorem to general commutative semirings, and we generalize the state reduction algorithm to general commutative semifields. This leads to a new universal algorithm, whose prototype is the state reduction algorithm which computes the Markov chain tree vector of a stochastic matrix.
MSC:
| 15B51 | Stochastic matrices |
| 16Y60 | Semirings |
| 12K10 | Semifields |
| 15A80 | Max-plus and related algebras |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
Keywords:
Markov chain; universal algorithm; commutative semiring; state reduction; commutative semifields; tree; stochastic matrixReferences:
| [1] | Baccelli, F.; Cohen, G.; Olsder, G. J.; Quadrat, J.-P., Synchronization and linearity: an algebra for discrete event systems (2001), free web edition |
| [2] | Backhouse, R. C.; Carré, B. A., Regular algebra applied to path-finding problems, J. Inst. Math. Appl., 15, 161-186 (1975) · Zbl 0304.68082 |
| [3] | Bapat, R. B., A max version of the Perron-Frobenius theorem, Linear Algebra Appl., 275-276, 3-18 (1998) · Zbl 0941.15020 |
| [4] | Benek Gursoy, B.; Kirkland, S.; Mason, O.; Sergeev, S., On the Markov chain tree theorem in the max algebra, Electron. J. Linear Algebra, 26, 15-27 (2013) · Zbl 1283.15080 |
| [5] | Butkovič, P., Max-Linear Systems: Theory and Algorithms (2010), Springer · Zbl 1202.15032 |
| [6] | Chu, Y. J.; Liu, T. H., On the shortest arborescence of a directed graph, Sci. Sin., 14, 1396-1400 (1965) · Zbl 0178.27401 |
| [7] | Edmonds, J., Optimum branchings, J. Res. Natl. Bur. Stand., 69B, 125-130 (1967) · Zbl 0155.51204 |
| [8] | Fenner, T. I.; Westerdale, T. H., A random graph proof for the irreducible case of the Markov chain tree theorem (2000), Birkbeck, University of London, Department of Computer Science and Information Systems, available from |
| [9] | Freĭdlin, M. I.; Wentzell, A. D., Perturbations of Stochastic Dynamic Systems (1979), Springer: Nauka: Springer: Nauka Moscow, translation of Russian edition: |
| [10] | Gondran, M., Path algebra and algorithms, (Roy, B., Combinatorial Programming: Methods and Applications (1975), Reidel: Reidel Dordrecht), 137-148 · Zbl 0326.90060 |
| [11] | 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 |
| [12] | Heidergott, B.; Olsder, G. J.; van der Wounde, J., Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications (2006), Princeton University Press · Zbl 1130.93003 |
| [13] | Jungnickel, D., Graphs, Networks and Algorithms (2005), Springer-Verlag · Zbl 1061.05001 |
| [14] | Kirkland, S.; Pullman, N. J., Boolean spectral theory, Linear Algebra Appl., 175, 177-190 (1992) · Zbl 0769.15007 |
| [15] | Litvinov, G. L.; Maslov, V. P., The correspondence principle for idempotent calculus and some computer applications, (Gunawardena, J., Idempotency (1998), Cambridge University Press), 420-443 · Zbl 0897.68050 |
| [16] | (Litvinov, G. L.; Maslov, V. P., Idempotent Mathematics and Mathematical Physics. Idempotent Mathematics and Mathematical Physics, Contemp. Math., vol. 307 (2005), Amer. Math. Soc.: Amer. Math. Soc. Providence) · Zbl 1069.00011 |
| [17] | Litvinov, G. L.; Maslova, E. V., Universal numerical algorithms and their software implementation, Program. Comput. Software, 26, 5, 275-280 (2000) · Zbl 0968.68194 |
| [18] | Litvinov, G. L.; Sobolevskiĭ, A. N., Idempotent interval analysis and optimization problems, Reliab. Comput., 7, 5, 353-377 (2001) · Zbl 1012.65065 |
| [19] | Litvinov, G. L.; Rodionov, A. Ya.; Sergeev, S. N.; Sobolevski, A. N., Universal algorithms for solving the matrix Bellman equations over semirings, Soft Comput., 17, 10, 1767-1785 (2013) · Zbl 1327.65082 |
| [20] | (Litvinov, G. L.; Sergeev, S. N., Tropical and Idempotent Mathematics. Tropical and Idempotent Mathematics, Contemp. Math., vol. 495 (2009), Amer. Math. Soc.: Amer. Math. Soc. Providence) · Zbl 1172.00019 |
| [21] | Meyer, C. D., Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems, SIAM Rev., 31, 240-272 (1989) · Zbl 0685.65129 |
| [22] | Minoux, M., Bideterminants, arborescences and extension of matrix-tree theorem to semirings, Discrete Math., 171, 191-200 (1997) · Zbl 0880.05065 |
| [23] | Minoux, M., Extension of Mac-Mahon’s master theorem to pre-semi-rings, Linear Algebra Appl., 338, 19-26 (2001) · Zbl 0992.15015 |
| [24] | Puhalskii, A., Large Deviations and Idempotent Probability (2001), Chapman & Hall · Zbl 0983.60003 |
| [25] | Rote, G., A systolic array algorithm for the algebraic path problem, Computing, 34, 191-219 (1985) · Zbl 0562.68056 |
| [26] | Sheskin, T., A Markov partitioning algorithm for computing steady-state probabilities, Oper. Res., 33, 228-235 (1985) · Zbl 0569.90092 |
| [27] | Sonin, I., The state reduction and related algorithms and their applications to the study of Markov chains, graph theory, and the optimal stopping problem, Adv. Math., 145, 159-188 (1999) · Zbl 0953.60064 |
| [28] | Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structures, Ann. Discrete Math., vol. 10 (1981), North-Holland: North-Holland Amsterdam · Zbl 0466.90045 |
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.
