On effective algorithms solving regularity of Markov chains

We propose algorithms deciding whether a Markov chain with an n_n transition matrix M is regular. The lowest complexity of such an algorithm can be not greater than O(n 3 ) and we argue that it cannot be essentially diminished.

---

W pracy proponujemy algorytmy rozstrzygające regularność łańcuchów Markowa o macierzy przejść rozmiaru n x n. Najniższa złożoność takiego algorytmu może być nie większa niż O(n 3 i podana jest argumentacja, że nie można jej istotnie obniżyć.

---

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).