Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/1642

Computing the periodicity of finite Markov chains

Authors Jarvis, James P.
Shier, Douglas R.
Issue Date 1993-07
Summary Determining the period of a finite irreducible Markov chains involves finding the greatest common divisor of the number of transitions that carry any state back to itself with non-zero probability. This is equivalent to finding the greatest common divisor of the lengths of all cycles in the directed graph defined by the state transition diagram. A linear-time algorithm based on a breadth-first search of this directed graph can be used to determine the period of the chain without examining all cycles in the graph.
Subjects
Language English
Format Research report
Access
Files in this item:
File Description Size Format
computing.pdf 1.05 MB Adobe PDF