An algorithm for finding closed and transient sets in an arbitrary Markov chain probability transition matrix

 

By Nasser Abbasi

March 9, 2008

 

The problem: Given an arbitrary matrix which represent the probability of transition from one state to another state in one step for a Markov chain, determine all closed sets of states and the transient state.

 

This small paper is an algorithm that I developed which solves this problem. The algorithm is recursive in nature and is described in detailed in the following paper.

 

A Matlab implementation can be found below. The HTML version of the paper below shows at the end an example run on 3 different matrices and how to call the matlab function.

 

Paper

[PDF] [HTML]

 

Matlab code

  1. driver function showing how to call the function itself   nmaTestMarkov.m  [DISPLY]
  2. the function implementation itself  nmaChainMarkov.m [DISPLY]

 

Example output

EDU>> clear all

EDU>> close all

EDU>> nmaTestMarkov()

***************************

 

    1.0000         0         0         0         0

         0    0.2000    0.8000         0         0

         0    0.7000    0.3000         0         0

    0.1000         0    0.1000    0.4000    0.4000

         0    0.1000    0.3000    0.2000    0.4000

 

found the following closed sets

{1}

{2,3}

found the following transient set

{4,5}

 

 

***************************

 

    0.1000    0.3000         0         0    0.6000

         0    0.2000    0.7000         0    0.1000

         0    0.7000    0.3000         0         0

    0.1000         0    0.1000    0.4000    0.4000

         0    0.1000    0.3000    0.2000    0.4000

 

found the following closed sets

{1,2,3,4,5}

No transient set found

 

 

***************************

 

    0.5000    0.5000         0         0         0         0

         0         0    1.0000         0         0         0

    0.3333         0         0    0.3333    0.3333         0

         0         0         0    0.5000    0.5000         0

         0         0         0         0         0    1.0000

         0         0         0         0    1.0000         0

 

found the following closed sets

{5,6}

found the following transient set

{1,2,3,4}

***************************

 

    1.0000         0         0         0         0         0

         0    1.0000         0         0         0         0

         0         0    1.0000         0         0         0

         0         0         0         0    0.5000    0.5000

    0.2500    0.2500         0         0         0    0.5000

    0.2500         0    0.2500         0    0.5000         0

 

found the following closed sets

{1}

{2}

{3}

found the following transient set

{4,5,6}

***************************

 

    1.0000         0      0         0         0         0         0         0         0

         0    1.0000      0         0         0         0         0         0         0

    0.2222    0.1111      0    0.0833    0.1111    0.1389    0.1389    0.1111    0.0833

    0.1389    0.1667      0    0.7500         0         0         0         0         0

    0.1111    0.1667      0         0    0.7222         0         0         0         0

    0.1389    0.1667      0         0         0    0.6944         0         0         0

    0.1389    0.1667      0         0         0         0    0.7222         0         0

    0.1111    0.1667      0         0         0         0         0    0.7222         0

    0.0833    0.1667      0         0         0         0         0         0    0.7500

 

found the following closed sets

{1}

{2}

found the following transient set

{3,4,5,6,7,8,9}

EDU>>