|
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2020, Number 1, Pages 75–88
(Mi basm524)
|
|
|
|
Research articles
New algorithms for finding the limiting and differential matrices in Markov chains
Alexandru Lazari, Dmitrii Lozovanu Vladimir Andrunachievic Institute of Mathematics and Computer Science, 5 Academiei str., Chişinău, MD-2028, Moldova
Abstract:
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(n^3)$ and the complexity of calculating differential matrices is $O(n^{\omega+1})$, where $n$ is the number of the states of the Markov chain and $O(n^\omega)$ 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 $\omega<2.372864$.
Keywords and phrases:
discrete markov process, the matrix of limiting states probabilities, differential matrices, matrix multiplication complexity.
Received: 04.03.2020
Citation:
Alexandru Lazari, Dmitrii Lozovanu, “New algorithms for finding the limiting and differential matrices in Markov chains”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2020, no. 1, 75–88
Linking options:
https://www.mathnet.ru/eng/basm524 https://www.mathnet.ru/eng/basm/y2020/i1/p75
|
Statistics & downloads: |
Abstract page: | 102 | Full-text PDF : | 63 | References: | 12 |
|