### 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 [*b*_{kj}]:
(a) State *i* is absorbing if and only if *b*_{ii} = 1 and *b*_{ij} = 0 for all *j ≠ i*.

(b) If state *j* is absorbing and *b*_{ij} > 0, where *i ≠ j*, then state *i* is transient.

(c) If state *j* is transient and *b*_{kj} > 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 [*b*_{ij}].
**Step 1**

- Define single element sets
*S*_{i}={*i*} for *i=1,...,n*
- Search the diagonal elements, labelling any absorbent states.
- If state
*j* is absorbing, search column *j*, labelling all states *i* with *b*_{ij} > 0 as transient.
- Set
*r*=0.

**Step 2**

- If all states are labelled, stop; otherwise continue.

**Step 3**

- If
*r*=0, begin a chain of states by finding the first row *j* corresponding to an unlabelled state; let *i*_{1}=j and increase *r* to 1.
- Extend the chain {
*i*_{1},...,i_{r}} by searching row *i*_{r} for the first off-diagonal positive element *b*_{irir+1}.
- If state
*i*_{r+1} is transient, label each state in
*S*_{ii} ∪···S_{ir}
as transient, set *r* = 0 and go to step 2.

(23rd Feb 2006: Owing to my confusion about the *S*_{ij} being a union in general, at one stage I programmed this by only labelling states
*i*_{1},...,i_{r} as transient. )
- If state
*i*_{r+1} has not been labelled transient and *i*_{r+1}=i_{k} for some *k < r*, we have a circuit and proceed to step 4; otherwise, increment *r* and extend the chain again.

**Step 4**

- Replace row
*i*_{k} by the union of rows *i*_{k},...,i_{r}.
- Replace column
*i*_{k} by the union of columns *i*_{k},...,i_{r}.
- Delete rows and columns
*i*_{k+1},...,i_{r}.
- Replace
*S*_{ik} by *S*_{ik} ⋃ *S*_{ik+1} ⋃,...,⋃ *S*_{ir}.
(10th March 2006: I previously had only adjoined the elements *i*_{k+1},...,i_{r}.)
- If state
*i*_{k} is absorbing, label each state in *S*_{ik} ergodic, label each state *h ≠ i*_{k} (not already labelled transient) with *b*_{hik} > 0 as transient, set *r* = 0 and go to step 2.
- If state
*i*_{k} is not absorbing, set *r=k* and go to step 3.

### Remarks

- The deletion of rows and columns is
*virtual* and is carried out by flagging the rows and colums as having been deleted.
- In Step 4, part 4, one has to ensure no repetitions are in the union.
- 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.
- 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