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 ³ ) 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 ³ i podana jest argumentacja, że nie można jej istotnie obniżyć.