The Fox-Landi Algorithm

This algorithm identifes the ergodic subchains and transient states for a Markov matrix and was published in Communications of the ACM, Volume 11, Number 9, September 1968.
It uses the following properties of a Markov matrix [bkj]:

(a) State i is absorbing if and only if bii = 1 and bij = 0 for all j ≠ i.
(b) If state j is absorbing and bij > 0, where i ≠ j, then state i is transient.
(c) If state j is transient and bkj > 0, where k ≠ j, then state k is transient.
(d) Transience and recurrence are class properties of communicating states.

The algorithm

Input: An n×n Markov matrix [bij].

Step 1

  1. Define single element sets Si={i} for i=1,...,n
  2. Search the diagonal elements, labelling any absorbent states.
  3. If state j is absorbing, search column j, labelling all states i with bij > 0 as transient.
  4. Set r=0.
Step 2
Step 3
  1. If r=0, begin a chain of states by finding the first row j corresponding to an unlabelled state; let i1=j and increase r to 1.
  2. Extend the chain {i1,...,ir} by searching row ir for the first off-diagonal positive element birir+1.
  3. If state ir+1 is transient, label each state in Sii ∪···Sir as transient, set r = 0 and go to step 2.
    (23rd Feb 2006: Owing to my confusion about the Sij being a union in general, at one stage I programmed this by only labelling states i1,...,ir as transient. )
  4. If state ir+1 has not been labelled transient and ir+1=ik for some k < r, we have a circuit and proceed to step 4; otherwise, increment r   and extend the chain again.
Step 4
  1. Replace row ik by the union of rows ik,...,ir.
  2. Replace column ik by the union of columns ik,...,ir.
  3. Delete rows and columns ik+1,...,ir.
  4. Replace Sik by Sik ⋃ Sik+1 ⋃,...,⋃ Sir. (10th March 2006: I previously had only adjoined the elements ik+1,...,ir.)
  5. If state ik is absorbing, label each state in Sik ergodic, label each state h ≠ ik (not already labelled transient) with bhik > 0 as transient, set r = 0 and go to step 2.
  6. If state ik is not absorbing, set r=k and go to step 3.

Remarks

  1. The deletion of rows and columns is virtual and is carried out by flagging the rows and colums as having been deleted.
  2. In Step 4, part 4, one has to ensure no repetitions are in the union.
  3. The rows and columns of the input matrix are permuted so that (a) absorbing states are first, (b) other ergodic sets come next, (c) transient states come last.
  4. An implementation in BCMATH can be seen here. As there are no "goto's" in PHP, two "while" loops are instead used in the code.

Last modified 10th March 2006
Return to main page