Efficient algorithm for finding period of Markov chain What is the least time consuming way to find a period of state of irreducible Markov chain? I wondering if there is an algorithm which does not use matrix multiplication?

There is an efficient algorithm based on breadth-first search here:
http://cecas.clemson.edu/~shierd/Shier/markov.pdf
Given a dense N x N matrix the algorithm would be worst-case O(n^2) whereas computing all matrix powers would be O(n^4) which is most likely much slower for matrices of any significant size.
