USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Classification of States

A Markov chain is characterized by a set of states and transitions. We define some categories of states.

 

(a) A state is recurrent if the system, once in that state will return to that state through a series of transitions with probability 1.

 

(b) A state is transient if it is not recurrent.

 

(c) A recurrent state is recurrent non null if the mean time to return to the state is finite.

 

(d) A recurrent state is recurrent null if the mean time to return to the state is infinite.

 

Note. In (b) transient does not mean it cannot recur. It only means that the state is not guaranteed of recurring.

 

(e) A recurrent state is aperiodic if for some number k, there is a way to return to the state in k, k + 1, k + 2, ... ∞ transitions.

 

(f) A recurrent state is periodic if it is not aperiodic.

 

(g) A Markov chain is irreducible if all states are reachable from all other states.

 

(h) A Markov chain is transient if all its states are transient.

It is recurrent non null if all its states are recurrent non null.

It is recurrent null if all its states are recurrent null.

It is periodic if all its states are periodic.

It is aperiodic if all its states are aperiodic.

 

(i) If the Markov chain is irreducible, recurrent non null and aperiodic, it is called ergodic.

 

An ergodic Markov chain has the property that it is possible to go from one state to any other state in a finite number of steps, regardless of the present state.

 

A regular chain is a special type of ergodic chain whose transition matrix P is such that for some power of P, it has only non-zero probability elements.

 

It follows that all regular chains must be ergodic but all ergodic chains may not be regular.

 

Note. To test an ergodic chain is regular, continue square the transition matrix P sequentially until all O's disappear.

 

Example 4. Consider the discrete time Markov chain as follows :

(i) Is the state 0 recurrent or transient ?

(ii) Is the state 0 recurrent null or recurrent non null ?

(iii) Is the state 0 periodic or aperiodic ?

 

Solution. (i) It is a recurrent state. There is nowhere to go from state 0 where it cannot return.

 

(ii) It is a recurrent non null simply because there are only a finite number of states i.e., four.

(iii) The returning to state 0 in an odd number of steps is not possible. Therefore, there is no number k such that the system can return in k + 1 and k + 2 steps, since k + 1 or k + 2 must be odd. Therefore, the state 0 is periodic with period 2.

 

Example 5. Test whether the following Markov chain is ergodic and regular.

Solution. Consider the state diagram.

It is possible to go from state E1 to E2 or E3, from state E2 to E1 or E3 from state E3 to E1 or E2. Hence it is ergodic.

Then

Since all zeroes disappear, it is regular.