{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:25:42Z","timestamp":1787329542081,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>This work presents an approach for reducing the number of arithmetic operations involved in the computation of a stationary distribution for a finite Markov chain. The proposed method relies on a particular decomposition of a transition-probability matrix called stochastic factorization. The idea is simple: when a transition matrix is represented as the product of two stochastic matrices, one can swap the factors of the multiplication to obtain another transition matrix, potentially much smaller than the original. We show in the paper that the stationary distributions of both Markov chains are related through a linear transformation, which opens up the possibility of using the smaller chain to compute the stationary distribution of the original model. In order to support the application of stochastic factorization, we prove that the model derived from it retains all the properties of the original chain which are relevant to the stationary distribution computation. Specifically, we show that (i) for each recurrent class in the original Markov chain there is a corresponding class in the derived model with the same period and, given some simple assumptions about the factorization, (ii) the original chain is irreducible if and only if the derived chain is irreducible and (iii) the original chain is regular if and only if the derived chain is regular. The paper also addresses some issues associated with the application of the proposed approach in practice and briefly discusses how stochastic factorization can be used to reduce the number of operations needed to compute the fundamental matrix of an absorbing Markov chain.<\/jats:p>","DOI":"10.1137\/100798776","type":"journal-article","created":{"date-parts":[[2011,12,15]],"date-time":"2011-12-15T19:09:30Z","timestamp":1323976170000},"page":"1513-1523","source":"Crossref","is-referenced-by-count":2,"title":["Computing the Stationary Distribution of a Finite Markov Chain Through Stochastic Factorization"],"prefix":"10.1137","volume":"32","author":[{"given":"Andr\u00e9 M. S.","family":"Barreto","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcelo D.","family":"Fragoso","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,15]]},"reference":[{"key":"R1","unstructured":"A. M. S. Barreto, D. Precup, and J. Pineau,\n                      Policy iteration based on stochastic factorization\n                      , submitted."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. M. S. Barreto and M. D. Fragoso,\n                      Lumping the states of a finite Markov chain through stochastic factorization\n                      , in Proceedings of the 18th World Congress of the International Federation of Automatic Control (IFAC), Milano, Italy, 2011, pp. 4206\u20134211.","DOI":"10.3182\/20110828-6-IT-1002.00073"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/j.csda.2006.11.006"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(01)00320-2"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)90224-C"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1994.10485840"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.277"},{"key":"R8","first-page":"223","volume":"3","author":"Gregory D. A.","year":"1983","journal-title":"J. Combin. Inform. System Sci."},{"key":"R9","unstructured":"C. M. Grinstead and J. L. Snell,\n                      Introduction to Probability\n                      , 2nd ed., AMS, Providence, RI, 2006."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"O. H\u00e4ggstr\u00f6m,\n                      Finite Markov Chains and Algorithmic Applications\n                      , Cambridge University Press, Cambridge, UK, 2002.","DOI":"10.1017\/CBO9780511613586"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2007.02.026"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R13","unstructured":"R. Horn and C. Johnson,\n                      Matrix Analysis\n                      , Cambridge University Press, Cambridge, UK, 1990."},{"key":"R14","unstructured":"M.  Iosifescu,\n                      Finite Markov Chains and Their Applications\n                      , John Wiley & Sons, New York, 1980."},{"key":"R15","unstructured":"S. Karlin and H. Taylor,\n                      A Second Course in Stochastic Processes\n                      , Academic Press, New York, 1981."},{"key":"R16","unstructured":"J. G. Kemeny and J. L. Snell,\n                      Finite Markov Chains\n                      , Van Nostrand, New York, Princeton, NJ, 1976."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"J. G. Kemeny, J. L. Snell, and A. W. Knapp,\n                      Denumerable Markov chains\n                      , Springer, Berlin, New York, 1976.","DOI":"10.1007\/978-1-4684-9455-6"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1038\/44565"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"D. A. Levin, Y. Peres, and E. L. Wilmer,\n                      Markov Chains and Mixing Times\n                      , AMS, Providence, RI, 2008.","DOI":"10.1090\/mbk\/058"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1162\/neco.2007.19.10.2756"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1972-0289539-2"},{"key":"R22","unstructured":"W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery,\n                      Numerical Recipes\u2014The Art of Scientific Computing\n                      , 3rd ed., Cambridge University Press, Cambridge, UK, 2007."},{"key":"R23","unstructured":"W. J. Stewart,\n                      An Introduction to the Numerical Solutions of Markov Chains\n                      , Princeton University Press, Princeton, NJ, 1994."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/070709967"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100798776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:20:56Z","timestamp":1787325656000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100798776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1137\/100798776"],"URL":"https:\/\/doi.org\/10.1137\/100798776","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]}}}