New Algorithms for Finding the Limiting and Differential Matrices in Markov Chains
Close
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
597 8
Ultima descărcare din IBN:
2022-04-21 22:22
Căutarea după subiecte
similare conform CZU
519.2+519.8 (3)
Probability. Mathematical statistics (80)
Operational research (OR): mathematical theories and methods (168)
SM ISO690:2012
LAZARI, Alexandru, LOZOVANU, Dmitrii. New Algorithms for Finding the Limiting and Differential Matrices in Markov Chains. In: Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2020, nr. 1(92), pp. 75-88. ISSN 1024-7696.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
Numărul 1(92) / 2020 / ISSN 1024-7696 /ISSNe 2587-4322

New Algorithms for Finding the Limiting and Differential Matrices in Markov Chains

CZU: 519.2+519.8
MSC 2010: 65C40, 60J22, 90C40, 65F05, 65F15, 15B51.

Pag. 75-88

Lazari Alexandru, Lozovanu Dmitrii
 
Vladimir Andrunachievici Institute of Mathematics and Computer Science
 
Proiecte:
 
Disponibil în IBN: 5 septembrie 2020


Rezumat

New algorithms for determining the limiting and differential matrices in Markov chains, using fast matrix multiplication methods, new computation procedure of the characteristic polynomial and algorithms of resuming matrix polynomials, are proposed. We show that the complexity of finding the limiting matrix is O(n3) and the complexity of calculating differential matrices is O(n!+1), where n is the number of the states of the Markov chain and O(n!) is the complexity of the used matrix multiplication algorithm. The theoretical computational complexity estimation of the algorithm is governed by the fastest known matrix multiplication algorithm, for which ! < 2.372864.

Cuvinte-cheie
Discrete Markov Process, The Matrix of Limiting States Probabilities, Differential Matrices, Matrix Multiplication Complexity