Markov Chains (II)

MASSACHUSETTS INSTITUTE OF TECHNOLOGY Fall 2018 6.436J/15.085J Lecture 22 MARKOV CHAINS II Contents 1. Markov chains with a single recurrence class 2. Uniqueness of Stationary Distributions 1 Markov chains with a single recurrence class Recall the relations →, ↔ introduced in the previous lecture for the class of finite state Markov chains. Recall that we defined a state i to be recurrent if whenever i → j we also have j → i, namely i ↔ j. We have observed that ↔ is an equivalency relation, so that set of recurrent states is partitioned into equivalency classes R1 , . . . , Rr . The remaining states T are transient. Lemma 1. For every l = 1, . . . , r and every i ∈ Rl , j ∈ / Rl we must have pi,j = 0. This means that once the chain is in some recurrent class R it stays there forever. Proof. The proof is simple: pi,j > 0 implies i → j. Since i is recurrent then also j → i implying j ∈ R - contradiction. Introduce the following basic random quantities. Given states i, j let Ti = min{n ≥ 1 : Xn = i|X0 = i}. In case no such n exists, we set Ti = ∞. Thus the range of Ti is N ∪ {∞}. The quantity is called the the first passage time. Let µi = E[Ti ], possibly with µi = ∞. This is called mean recurrence time of the state i. 1 Lemma 2. For every state i ∈ T , P(Xn = i, i.o.) = 0. Namely, almost surely, after some finite time n0 , the chain will never return to i. In addition E[Ti ] = ∞ . Proof. By definition there exists a state j such that i → j, but j 9 i. It then follows that P(Ti = ∞) > 0 implying E[Ti ] = ∞. Now, let us establish the first part. Let Ii,m be the indicator of the event that the M.c. returned to state i at least m times. Notice that P(Ii,1 ) = P(Ti < ∞) < 1. Also by M.c. property we have P(Ii,m |Ii,m−1 ) = P(Ti < ∞), as conditioning that at some point the M.c. returned to state i m−1 times does not impact its likelihood to return to this state again. Also notice Ii,m ⊂ Ii,m−1 . Thus P(Ii,m ) = P(Ii,m |Ii,m−1 )P(Ii,m−1 ) = P(Ti < ∞)P(Ii,m−1 ) = · · · = Pm (Ti < ∞). Since P(Ti < ∞) < 1, then by continuity of probability property we obtain P(∩m Ii,m ) = limm→∞ P(Ii,m ) = limm→∞ Pm (Ti < ∞) = 0. Notice that the event ∩m Ii,m is precisely the event Xn = i, i.o. Exercise 1. Show that T 6= X . Namely, in every finite state M.c. there exists at least one recurrent state. Exercise 2. Let i ∈ T and let ˇ be an arbitrary stationary distribution. Establish that ˇi = 0. Exercise 3. Suppose M.c. has one recurrent class R. Show that for every i ∈ R P(Xn = i, i.o.) = 1. Moreover, show that there exists 0 < q < 1 and C > 0 such that P(Ti > t) ≤ Cq t for all t ≥ 0. As a result, show that E[Ti ] < ∞. We now focus on the family of Markov chains with only one recurrent class. Namely X = T ∪R. If in addition T = Ø, then such a M.c. is called irreducible. 2 Uniqueness of the stationary distribution We now establish a fundamental result on M.c. with a single recurrence class. Theorem 1. A finite state M.c. with a single recurrence class has a unique stationary distribution ˇ, which is given as ˇi = µ1i for all states i. Specifically, ˇi > 0 iff the state i is recurrent. 2 Proof. Let P be the transition matrix of the chain. We let the state space be X = {1, . . . , N }. We fix an arbitrary recurrent state k. We know that one exists by Exercise 1. Assume X0 = k. Let Ni be the number of visits to state i between two successive visits to state k. In case i = k, the last visit is counted but the initial is not. Namely, in the special case i = k the number of visits is 1 with probability one. Let ˆi (k) = E[N Pi ]. Consider the event P{Xn = i, Tk ≥ n} and consider the indicator function n≥1 IXn =i,Tk ≥n = 1≤n≤Tk IXn =i . Notice that this sum is precisely Ni . Namely, X P(Xn = i, Tk ≥ n|X0 = k). (1) ˆi (k) = n≥1 P Then using the formula E[Z] = n≥1 P(Z ≥ n) for integer valued r.v., we obtain X X ˆi (k) = P(Tk ≥ n|X0 = k) = E[Tk ] = µk . (2) i n≥1 Since k is recurrent, then by Exercise 3, µk < ∞ implying ˆi (k) < ∞. We let ˆ(k) denote the vector with components ˆi (k). Lemma 3. ˆ(k) satisfies ˆT (k) = ˆT (k)P . In particular, for every recurrent state k, ˇi = ˆiµ(k) , 1 ≤ i ≤ N defines a stationary distribution. k Proof. The second part follows from (2) and the fact that µk < ∞. Now we prove the first part. We have for every n ≥ 2 X P(Xn = i, Tk ≥ n|X0 = k) = P(Xn = i, Xn−1 = j, Tk ≥ n|X0 = k) j6=k = X (3) P(Xn−1 = j, Tk ≥ n − 1|X0 = k)pj,i (4) j6=k Observe that P(X1 = i, Tk ≥ 1|X0 = k) = pk,i . We now sum the (3) over n and apply it to (1) to obtain XX P(Xn−1 = j, Tk ≥ n − 1|X0 = k)pj,i ˆi (k) = pk,i + j6=k n≥2 3 P We recognize n≥2 P(Xn−1 = j, Tk ≥ n − 1|X0 = k) as ˆj (k). Using ˆk (k) = 1 we obtain X X ˆi (k) = ˆk (k)pk,i + ˆj (k)pj,i = ˆj (k)pj,i j6=k j which is in vector form precisely ˆT (k) = ˆT (k)P . We now return to the proof of the theorem. Let ˇ denote an arbitrary stationary distribution of our M.c. We know one exists by Lemma 3 and, independently by our linear programming based proof. By Exercise 2 we already know that ˇi = 1/µi = 0 for every transient state i. We now show that in must be that ˇk = 1/µk for every recurrent state k. In particular, the stationary distribution is unique. Assume that at time zero we start with distribution ˇ. Namely P(X0 = i) = ˇi for all i. Of course this implies that P(Xn = i) is also ˇi for all n. On the other hand, fix any recurrent state k and consider µk ˇk = E[Tk |X0 = k]P(X0 = k) X = P(Tk ≥ n|X0 = k)P(X0 = k) n≥1 = X P(Tk ≥ n, X0 = k). n≥1 On the other hand P(Tk ≥ 1, X0 = k) = P(X0 = k) and for n ≥ 2 6 k, 1 ≤ j ≤ n − 1) P(Tk ≥ n, X0 = k) = P(X0 = k, Xj = 6 k, 1 ≤ j ≤ n − 1) − P(Xj = 6 k, 0 ≤ j ≤ n − 1) = P(Xj = (∗) = P(Xj 6= k, 0 ≤ j ≤ n − 2) − P(Xj 6= k, 0 ≤ j ≤ n − 1) = an−2 − an−1 , where an = P(Xj = 6 k, 0 ≤ j ≤ n) and (*) follows from stationarity of ˇ. Now a0 = P(X0 6= k). Putting together, we obtain X µk ˇk = P(X0 = k) + (an−2 − an−1 ) n≥2 = P(X0 = k) + P(X0 6= k) − lim an n = 1 − lim an n 4 But by continuity of probabilities limn an = P(Xn 6= k, ∀n). By Exercise 3, the state k, being recurrent is visited infinitely often with probability one. We conclude that limn an = 0, which gives µk ˇk = 1, implying that ˇk is uniquely defined as 1/µk . 3 Ergodic theorem Let Ni (t) denote the number of times the state i is visited during the times 0, 1, . . . , t. What can be said about the behavior of Ni (t)/t when t is large? The answer turns out to be very simple: it is ˇi . These type of results are called ergodic properties, as they show how the time average of the system, namely Ni (t)/t relates to the spatial average, namely ˇi . Theorem 2. For arbitrary starting state X0 = k and for every state i, Ni (t) = ˇi t→∞ t lim almost surely. Also E[Ni (t)] = ˇi . t→∞ t lim Proof. Suppose X0 = k. If i is a transient state, then, as we have established, almost surely after some finite time, the chain will never enter i, meaning limt Ni (t)/t = 0 almost surely. Since also ˇi = 0, then we have established the required equality for the case when i is a transient state. Suppose now i is a recurrent state. Let T1 , T2 , T3 , . . . denote the time of successive visits to i. Then the sequence Tn , n ≥ 2 is i.i.d. Also T1 is independent from the rest of the sequence, although it distribution is different from the one of Tm , m ≥ 2 since we have started the chain from k which is in general different from i. By the definition of Ni (t) we have X X Tm Tm ≤ t < 1≤m≤Ni (t) from which we obtain P 1≤m≤Ni (t) Tm Ni (t) t ≤ < Ni (t) 1≤m≤Ni (t)+1 P 1≤m≤Ni (t)+1 Ni (t) + 1 5 Tm Ni (t) + 1 Ni (t) . (5) We know from Exercise 3 that E[Tm ] < ∞, m ≥ 2. Using a similar approach it can be shown that E[T1 ] < ∞, in particular T1 < ∞ a.s. Applying SLLN we have that almost surely P P 2≤m≤n Tm 2≤m≤n Tm n − 1 lim = lim = E[T2 ] n→∞ n→∞ n n−1 n which further implies P lim n→∞ 1≤m≤n n Tm = lim P 2≤m≤n Tm n n→∞ + lim n→∞ T1 = E[T2 ] n almost surely. Since i is a recurrent state then by Exercise 3, Ni (t) → ∞ almost surely as t → ∞. Combining the preceding identity with (5) we obtain lim t→∞ t = E[T2 ] = µi , Ni (t) from which we obtain limt Ni (t)/t = µ−1 i = ˇi almost surely. To establish the convergence in expectation, notice that Ni (t) ≤ t almost surely, implying Ni (t)/t ≤ 1. Applying bounded convergence theorem, we obtain that limt E[Ni (t)]/t = ˇi , and the proof is complete. 4 Markov chains with multiple recurrence classes How does the theory extend to the case when the M.c. has several recurrence classes R1 , . . . , Rr ? The summary of the theory is as follows (the proofs are very similar to the case of single recurrent class case and is omitted). It turns out i ), 1 ≤ that such a M.c. chain possesses r stationary distributions ˇ i = (ˇ1i , . . . , ˇN i ≤ r, each ”concentrating” on the class Ri . Namely for each i and each state k ∈ / Ri we have ˇki = 0. The i-th stationary distribution is described by ˇki = 1/µk for all k ∈ Ri and where µk is the mean return time from state k ∈ Rj into itself. Intuitively, the stationary distribution ˇ i corresponds to the case when the M.c. ”lives” entirely in the class Ri . One can prove that the family of all of the stationary distributions of such a M.c. can be obtained by taking all possible convex combinations of ˇ i , 1 ≤ i ≤ r, but we omit the proof. (Exercise: show that a convex combination of stationary distributions is a stationary distribution). 6 References [1] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, 3rd edition, 2001. [2] D. P. Bertsekas and J. N. Tsitsiklis, Introduction to probability, Athena Scientific, 2002. 7