The Fox-Landi algorithm for identifying the ergodic subchains and transient states for a stochastic matrix

This algorithm was published in Communications of the ACM, Volume 11, Number 9, September 1968.

There is a good exposition of the structure of Markov matrices in Dynamic Programming, by A. Kaufmann and B. Cruon, Academic Press, NY 1967.

Here is a description of the algorithm.

In 1982 Tony Watts coded the algorithm in Fortran, as part of our investigation of the frequencies of occupation of congruence classes (mod m) of trajectories arising from generalised 3x+1 functions.
Experimentally we had observed that divergent trajectories were attracted to ergodic sets mod m of a Markov matrix Q(m), with predictable frequencies.

In this BCMATH version, the non-zero entries of the Markov matrix must be replaced by 1's.

This program will also be useful to students of a first course in Markov chains.

Eventually the program will hopefully be enlarged to detect periodicity of the subchains. See period program.

There is also an expanded description of the Fox-Landi algorithm in the book Markov Decision Processes, by Martin L. Puterman, 589-591, Wiley 1994.

Acknowledgment: John Campbell wrote the PHP program for entering the matrix.


Last modified 16th June 2006
Return to main page