|
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 |
Size | Format |
|---|
| computing.pdf | | 1045Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
