HKUST Institutional Repository >
Research Centre >
RC Research Reports >
Please use this identifier to cite or link to this item:
|Title: ||Computing the periodicity of finite Markov chains|
|Authors: ||Jarvis, James P.|
Shier, Douglas R.
|Keywords: ||Markov chain|
State transition diagram
|Issue Date: ||Jul-1993 |
|Series/Report no.: ||Research Centre Publications 93-06|
|Abstract: ||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.|
|Appears in Collections:||RC Research Reports|
Files in This Item:
All items in this Repository are protected by copyright, with all rights reserved.