1

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?

Hlib
  • 111
  • You might want to review this previous Question and its Answers to make sure the definitions of period of a state and period of a Markov chain are clear. Asking for the "least time consuming way" to do something is a bit subjective, and algorithms that use matrix multiplication might be put in some other terms, such as finding cycles in graphs, that hide the essential operations. – hardmath May 09 '17 at 10:50
  • hardmath, thank you for your response. You are right. I meant period of the state when the chain is irreducible. – Hlib May 09 '17 at 11:04
  • Irreducible case also considered at the reference suggested above by hardmath – Lella May 09 '17 at 11:24
  • L.V.Rao, thank you. But "this previous Question" uses matrix multiplication. I need something that does not use it. – Hlib May 09 '17 at 12:22
  • Some of my confusion is from the requirement not to use matrix multiplication. A (finite) Markov chain is associated with a probability transition matrix. While this may contain more information than we need to find periods, if you wish to avoid using it, you should say how the information will instead be presented. – hardmath May 09 '17 at 14:56

1 Answers1

0

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.

Oscar Benjamin
  • 186