Consider a Markov chain with some transient and some

Chapter , Problem 7

(choose chapter or problem)

Consider a Markov chain with some transient and some recurrent states. (a) Show that for some numbers c and " with c > 0 and 0 < I < 1, we have P(Xn is transient I Xo = i) :5 C/n , for all i and n 1. (b) Let T be the first time n at which Xn is recurrent. Show that such a time is certain to exist (Le., the probability of the event that there exists a time n at which Xn is recurrent is equal to 1) and that E[T] < 00. Solution. (a) For notational convenience, let qi(n) = P(Xn transient I Xo = i). A recurrent state that is accessible from state i can be reached in at most m steps, where m is the number of states. Therefore, qi (m) < 1. Let {3 = , max qi(m) t=I , ... ,m and note that for all i, we have qi (m) :5 {3 < 1. If a recurrent state has not been reached by time m, which happens with probability at most {3, the conditional probability that a recurrent state is not reached in the next m steps is at most {3 as well, which suggests that qi(2m) :5 {3 2 . Indeed, conditioning on the possible values of Xm, we obtain qi(2m) = P(X2m transient I Xo = i) L P(X2m transient I Xm = j, Xo = i) P(Xm = j I Xo = i) j transient L P(X2m transient I Xm = j) P(Xm = j I Xo = i) J transient L P(Xm transient I Xo = j) P(Xm = j I Xo = i) j transient {3 L P(Xm = j I Xo = i) j transient = {3 P(Xm transient I Xo = i) {3 2. Continuing similarly, we obtain for all i and k 1. Let n be any positive integer, and let k be the integer such that km < n < (k + l)m. Then, we have Thus, the desired relation holds with c = {3- 1 and 'Y = {31/m. (b) Let A be the event that the state never enters the set of recurrent states. Using the result from part (a) , we have P(A) P(Xn transient) C"f n . Since this is true for every n and since 'Y < 1, we must have P(A) = O. This establishes that there is certainty (probability equal to 1) that there is a finite time T that a recurrent state is first entered. We then have DC E[T] = L nP(Xn- 1 transient, Xn recurrent) n=1 00 L nP(Xn- 1 transient) n=1 n=1 00 = c_ n(1 _ 'Y)'Y n-l 1 - 'Y L n=1 c where the last equality is obtained using the expression for the mean of the geometric distribution.