Discrete-Time Markov Chains: State Classifications

We classify states in Markov chains according to several key state properties, and then classify Markov chains according to properties that are shared by all states in the chain. Several of the classification properties are based of the idea of first passage times. The first passage time from state ii to state jj is the number of transitions to reach state jj the first time from state ii. f i j ( n ) =Prfirst passage time i → j is n f i j ( n ) first passage time i → j is n Using this definition, we can identify states as transient or recurrent. state i is recurrent⇔∑n=1∞ f i j ( n ) =1 ⇔ state i is recurrent n 1 f i j ( n ) 1 state i is transient⇔∑n=1∞ f i j ( n ) <1 ⇔ state i is transient n 1 f i j ( n ) 1 A state is transient if there is a non-zero probability that once the chain leaves that state, it will not return.

The mean time to return to recurrent state ii is ∑n=1∞ f i j ( n ) n 1 f i j ( n ) .

If a state is recurrent, it can be recurrent nonnull or recurrent null. recurrent state i is recurrent nonnull⇔∑n=1∞n f i j ( n ) <∞ ⇔ recurrent state i is recurrent nonnull n 1 n f i j ( n ) recurrent state i is recurrent null⇔∑n=1∞n f i j ( n ) =∞ ⇔ recurrent state i is recurrent null n 1 n f i j ( n ) The following is an example of a Markov chain with states that are recurrent null.

Consider state 0. It is easy to see that f 0 0 ( 1 ) =0 f 0 0 ( 1 ) 0 f 0 0 ( 2 ) =12 f 0 0 ( 2 ) 1 2 f 0 0 ( 3 ) =1213=16 f 0 0 ( 3 ) 1 2 1 3 1 6 f 0 0 ( 4 ) =122314=1314=112 f 0 0 ( 4 ) 1 2 2 3 1 4 1 3 1 4 1 12 and in general ∀n,n>1: f 0 0 ( n ) =1n-11n n n 1 f 0 0 ( n ) 1 n 1 1 n The probability of eventually returning to state 0 is ∑n=1∞ f 0 0 ( n ) =∑n=2∞1n-11n=∑n=1∞1n1n+1 n 1 f 0 0 ( n ) n 2 1 n 1 1 n n 1 1 n 1 n 1 Using induction, we can verify that ∑n=1∞1n1n+1=k-1k n 1 1 n 1 n 1 k 1 k and hence ∑n=1∞ f 0 0 ( n ) =limk→∞k-1k=1 n 1 f 0 0 ( n ) k k 1 k 1 Thus, state 0 is recurrent. To determine if it is recurrent nonnull or recurrent null, compute the expected time to return: ∑n=1∞n f 0 0 ( n ) =∑n=2∞n1n-11n=∑n=1∞1n=∞ n 1 n f 0 0 ( n ) n 2 n 1 n 1 1 n n 1 1 n Since the expected time to return to state 0 is infinite, the state must be recurrent null.

Recurrent nonnull states can be periodic or aperiodic. recurrent state i is periodic with period k>1⇔ f i j ( n ) ≠0⇔∀m,m∈123…:n=km ⇔ recurrent state i is periodic with period k>1 ⇔ f i j ( n ) 0 m m 1 2 3 … n k m Otherwise, ii is aperiodic.

In other words, a state is periodic if the probability of returning to the state is zero except at regular intervals. An example of a Markov chain with states that are periodic is the following:

f 0 0 ( 1 ) =0 f 0 0 ( 1 ) 0 f 0 0 ( 2 ) =1-p f 0 0 ( 2 ) 1 p f 0 0 ( 3 ) =0 f 0 0 ( 3 ) 0 f 0 0 ( 4 ) =p1-p f 0 0 ( 4 ) p 1 p f 0 0 ( 5 ) =0 f 0 0 ( 5 ) 0 f 0 0 ( 6 ) =p21-p f 0 0 ( 6 ) p 2 1 p ⋮ ⋮ In general, for j∈123… j 1 2 3 … , f 0 0 ( 2 j ) =pj-11-p f 0 0 ( 2 j ) p j 1 1 p f 0 0 ( 2 j - 1 ) =0 f 0 0 ( 2 j - 1 ) 0 Hence state 0 is periodic with period 2.

If all of the states of a Markov chain are recurrent nonnull, we say that the chain is recurrent nonnull. If all states are periodic (aperiodic), the chain is periodic (aperiodic).