15 Markov Chains: Limiting Probabilities

1 15 Markov CHAINS: Limiting PROBABILITIES16715 Markov Chains: Limiting ProbabilitiesExample that the transition matrix is given byP= 00 1 0 .Recall that then-step transition Probabilities are given by powers ofP. So let s look at somelarge powers ofP, beginning withP4= .Then, to four decimal placesP8 .and subsequent powers are the same to this matrix elements appear to converge and the rows become almost identical. Why? Whatdetermines the limit? These questions will be answered in this say that a statei Shasperiodd 1 if (1)Pnii>0 implies thatd|n, and (2)dis thelargest positive integer that satisfies (1).Example random walk onZ, withp (0,1).

2 The period of any state is 2 becausethe walker can return to her original position in any even number of steps, but in no odd numberof walk on vertices of a square. Again, the period of any state is 2, forthe same walk on vertices of triangle. The period of any state is 1 because thewalker can return in two steps (one step out and then back) or three steps (around the triangle).Example cycle. In a chain withnstates 0,1, .. , n 1, which moves fromiti (i+ 1) modnwith probability 1, has periodn. So, any period is , if the following two transition Probabilities arechanged:P01= andP00= ,then the chain has period 1. In fact, the period of any stateiwithPii>0 is trivially can be shown that a period is the same for all states in the same class.

3 If a state, andtherefore its class, has period 1, it is calledaperiodic. If the chain is irreducible, we call theentire chain aperiodic if all states have period Markov CHAINS: Limiting PROBABILITIES168 For a statei S, letRi= min{n 1 :Xn=i}be the first time, after time 0, that the chain is ini S. Also, letf(n)i=P(Ri=n|X0=i)be the p. m. f. ofRiwhen the starting state isiitself (in which case we may callRithereturntime). We can connect these to a familiar quantity,fi=P(ever reenteri|X0=i) = Xn=1f(n)i,so that the stateiis recurrent exactly whenP n=1f(n)i= 1. Then we definemi=E[Ri|X0=i] = Xn=1nf(n) the above series converges, ,mi< , then we say thatiispositive recurrent.

4 It can beshown that positive recurrence is also a class property: a state shares it with all members of itsclass. Thus an irreducible chain is positive recurrent if each of its states is not hard to show that a finite irreducible chain is positive recurrent. In this case theremust exist am 1 and an >0 so thatican be reached from anyjinmsteps with probabilityat least . ThenP(Ri n) (1 ) n/m , which goes to 0 geometrically now state the key theorems. Some of these have rather involved proofs (although noneare all that difficult), which we will merely sketch or omit of the time spent that the chain is irreducible and positive recurrent. LetNn(i)be the number of visits toiin the time interval from 0 throughn.

5 Then,limn Nn(i)n=1mi,in idea is quite simple: once the chain visitsi, it returns on the average once permitime steps, hence the proportion of time spent there is 1/mi. We skip a more detailed vector of Probabilities , i,i S, such thatPi S i= 1 is called aninvariant, orstationary,distributionfor a Markov chain with transition matrixPifXi S iPij= jfor allj Markov CHAINS: Limiting PROBABILITIES169In matrix form, if we put into a row vector [ 1, 2, ..], then[ 1, 2, ..] P= [ 1, 2, ..],thus [ 1, 2, ..] is theleft eigenvectorofP, for eigenvalue 1. More important for us is theprobabilistic interpretation. If iis the p. m. f. forX0, that is,P(X0=i) = i, for alli S, itis also p.

6 M. f. forX1, and then for all otherXn, that is,P(Xn=i) = i, for and uniqueness of invariant irreducible positive recurrent Markov chain has a uniqueinvariant distribution, which isgiven by i= fact, an irreducible chain is positive recurrent if and only if a stationary distribution formula for should not be a surprise: if the probability that the chain isiniis always i, then one should expect the proportion of time spent ati, which we already know to be 1/mi,to be equal to i. We will not, however, go deeper into the to invariant a Markov chain is irreducible, aperiodic, and positive recurrent, then, for everyi, j S,limn Pnij= thatPnij=P(Xn=j|X0=i), and note that the limit is independent of the initialstate.

7 Thus the rows ofPnare more and more similar to the row vector asnbecomes most elegant proof of this theorem usescoupling, an important idea first developed bya young French probabilist Wolfgang Doeblin in the late 1930s. (Doeblin s life is a very sadstory. An immigrant from Germany, he died as a soldier in the French army in 1940, at theage of 25. He made significant mathematical contributions during his army service.) Start withtwoindependentcopies of the chain two particles moving from state to stateaccording totransition Probabilities one started fromi, the other using initial distribution . Under thestated assumptions, they will eventually meet. Afterwards, the two particles move together inunison, that is, they arecoupled.

8 Thus the difference between the two Probabilities at timenisbounded above by twice the probability that coupling does not happen by timen, which goesto 0. We will not go into greater details, but, as we will see inthe next example, periodicity cycle witha= 3 has transition matrixP= 0 1 00 0 11 0 0 .15 Markov CHAINS: Limiting PROBABILITIES170 This is an irreducible chain, with invariant distribution 0= 1= 2=13(as it is very easy tocheck). MoreoverP2= 0 0 11 0 00 1 0 ,P3=I,P4=P, etc. Although the chain does spend 1/3 of the time at each state, the transitionprobabilities are a periodic sequence of 0 s and 1 s and do not final theorem is mostly a summary of results for the special, and for us the most common, theorem for finite state the Markov chain with a finite state space is There exists a unique invariant distribution given by i= For everyi, and irrespective of the initial state,1nNn(i)

9 I,in If the chain is also aperiodic, then for alliandj,Pnij If the chain is periodic with periodd, then for every pairi, j S, there exists an integerr,0 r d 1, so thatlimm Pmd+rij=d jand so thatPnij= 0for allnsuch thatn6= begin by our first example, Example That was clearly an irreducible,and also aperiodic (note thatP00>0) chain. The invariant distribution [ 1, 2, 3] is given 1+ 2= 1+ 2+ 3= 1= 3 This system has infinitely many solutions, and we need to use 1+ 2+ 3= 115 Markov CHAINS: Limiting PROBABILITIES171to get the unique solution 1=2037 , 2=1537 , 3=237 two-state Markov chain. HereS={1,2}andP= 1 1 ,and we assume that 0< , <1.

10 1+ 2= 1(1 ) 1+ (1 ) 2= 2 1+ 2= 1and after a little algebra, 1= 1 + 2=1 1 + Here are a few common follow-up questions: Start the chain at 1. In the long run, what proportion of time does the chain spend at 2?Answer: 2(and does not depend on the starting state). Start the chain at 2. What is the expected return time to 2? Answer:1 2. In the long run, what proportion of time is the chain at 2, while at the previous time itwas at 1? Answer: 1P12, as it needs to be at 1 at the previous time, and then make atransition to 2 (again, the answer does not depend on the starting state).Example that a machine can be in 4 states labeled 1, 2, 3, and 4. In states1 and 2, the machine is up, working properly.