HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Research Centre >
RC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/1642
Title: Computing the periodicity of finite Markov chains
Authors: Jarvis, James P.
Shier, Douglas R.
Keywords: Markov chain
Periodicity
State transition diagram
Breadth-first search
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.
URI: http://hdl.handle.net/1783.1/1642
Appears in Collections:RC Research Reports

Files in This Item:

File Description SizeFormat
computing.pdf1045KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.