Let Xtt0 be a Markov chain with state space S 0 1 2 3 4 5 a

Let {Xt}t?0 be a Markov chain with state space S = {0, 1, 2, 3, 4, 5} and transition matrix

(a) Classify each state as either transient, null recurrent, or positive recurrent.

(b) Determine the stationary distributions.

(c) For each state, determine its expected time of return.

(d) For each state, determine the proportion of time the chain spend in it, in the long run.

(e) Determine the period of each state.

(f) Is there a steady state distribution?

Solution

Definition: A Markov chain for which there is only one communication class is called an irreducible Markov chain: all states communicate.

An irreducible Markov chain with a finite state space is always recurrent: all states are recurrent. Finally observe (from the argument that if two states communicate and one is recurrent then so is the other) that for an irreducible recurrent chain, even if we start in some other state X0 6= i, the chain will still visit state i an infinite number of times: For an irreducible recurrent Markov chain, each state j will be visited over and over again (an infinite number of times) regardless of the initial state X0 = i. For example, if the rat in the closed maze starts off in cell 3, it will still return over and over again to cell 1. 2.2 Expected return time to a given state: positive recurrence and null recurrence A recurrent state j is called positive recurrent if the expected amount of time to return to state j given that the chain started in state j has finite first moment: E(jj ) < . A recurrent state j for which E(jj ) = is called null recurrent. In general even for i 6= j, we define ij def = min{n 1 : Xn = j |X0 = i}, the time (after time 0) until reaching state j given X0 = i.

Suppose i 6= j are both recurrent. If i and j communicate and if j is positive recurrent (E(jj ) < ), then i is positive recurrent (E(ii) < ) and also E(ij ) < . In particular, all states in a recurrent communication class are either all together positive recurrent or all together null recurrent. Proof : Assume that E(jj ) < and that i and j communicate. Choose the smallest n 1 such that P n j,i > 0. With X0 = j, let A = {Xk 6= j, 1 k n, Xn = i}; P(A) > 0. Then E(j,j ) E(j,j |A)P(A) = (n + E(i,j ))P(A); hence E(i,j ) < (for otherwise E(j,j ) = , a contradiction). With X0 = j, let {Ym : m 1} be iid distributed as j,j denote the interarrival times between visits to state j. Thus the n th revisit of the chain to state j is at time tn = Y1 + · · · + Yn, and E(Y ) = E(j,j ) < . Let p = P({Xn} visits state i before returning to state j | X0 = j). p P(A) > 0, where A is defined above. Every time the chain revisits state j, there is, independent of the past, this probability p that the chain will visit state i before revisiting state j again. Letting N denote the number of revisits the chain makes to state j until first visiting 4 state i, we thus see that N has a geometric distribution with “success” probability p, and so E(N) < . N is a stopping time with respect to the {Ym}, and j,i X N m=1 Ym, and so by Wald’s equation E(j,i) E(N)E(Y ) < . Finally, E(i,i) E(i,j ) + E(j,i) < .