Discrete-Time Markov Chains: State Classifications 2.3 2002/09/16 2002/12/02 Bart Sinclair bs@rice.edu Charlet Reedstrom charlet@rice.edu Bart Sinclair bs@rice.edu aperiodic first passage time Markov chain periodic recurrent recurrent nonnull recurrent null state classification transient (Blank Abstract) 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 i to state j is the number of transitions to reach state j the first time from state i. 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 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 i is 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 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 ( 2 ) 1 2 f 0 0 ( 3 ) 1 2 1 3 1 6 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 ) 1 n 1 1 n The probability of eventually returning to state 0 is 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 1 n 1 n 1 k 1 k and hence 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 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 1 2 3 … n k m Otherwise, i 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 ( 2 ) 1 p f 0 0 ( 3 ) 0 f 0 0 ( 4 ) p 1 p f 0 0 ( 5 ) 0 f 0 0 ( 6 ) p 2 1 p ⋮ In general, for j 1 2 3 … , f 0 0 ( 2 j ) p j 1 1 p 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).