Math 312 Lecture Notes Markov Chains - Colgate University

1 Math312 LectureNotesMarkov ChainsWarrenWeckesserDepartment of MathematicsColgateUniversityUpdated,30 April2005 Markov ChainsA ( nite) Markov chainis a processwitha nitenumber of states(oroutcomes,or events)in whichtheprobability of beingin a particularstateat stepn+ 1 ; S2; : : : ; Srgbe ~pn= (1)be thevectorof probabilitiesof each stateat stepn. Thatis, theith entryof~pnis theprobabilitythattheprocessis in stateSiat stepn. For such a probability vector,p1+p2+ +pr= Prob(Staten+ 1 isSijStatenisSj);(2)andletP=26664p11p12 p1rp21p22 (3)Thatis,pijis the(conditional)probability of beingin stateSiatstepn+ 1 giventhattheprocesswas in stateSjat theMarkov canbe usefulto label therowsandcolumnsofPwiththestates,as in thisexamplewiththreestates:Statenz}|{S1S 2S3 Staten+ 18> <>:S1S2S3264p11p12p13p21p22p23p31p32p33375 1 Thefundamentalproperty of a Markov chainis that~pn+1=P~pn:(4)Givenaninitialprobabil ity vector~p0, we candeterminetheprobability vectorat any stepnbycomputingtheiteratesof a thetransitionmatrixcanalsobe representedin atransitiondiagram.

2 In a transitiondiagram,thestatesarearrangedin a diagram,typicallywitha \bubble"aroundeach >0, thenanarrow is drawnfromstatejto statei, andthearrow islabeledwithpij. Examplesaregivenin thesenotes,we willconsidertwo specialcasesof Markov Chains :regularMarkov chainsandabsorbingMarkov Markov Chains ,includingcontinuoustimeMarkovproc essesandin nitedimensionalMarkov processes,arewidelystudied,butwe willnotdiscussthemin ChainsDe Markov chainis aregularMarkov chainif somepower of thetransitionmatrixhasonlypositive , if we de nethe(i; j) entryofPnto bep(n)ij, thentheMarkov chainis regularif thereis somensuch thatp(n)ij>0 forall(i; j).If a Markov chainis regular,thennomatterwhattheinitialstate, innstepsthereis a positiveprobability thattheprocessis inanyof factsabout regularMarkov !

3 Wasn!1, whereWis a constant Thereis a uniqueprobability vector~wsuch thatP~w=~ :(a)~wis a xedpoint of thelinearmap~xi+1=P~xi.(b)~wis aneigenvectorassociatedwiththeeigenvalue = 1.(Theclaimimpliesthatthetransitionmatri xPof a regularMarkov chainmusthave theeigenvalue = 1. Then~wis theeigenvectorwhoseentriesaddupto 1.)(c)ThematrixWisW= ~w~w ~w . ~p0!~wasn! 1foranyinitialprobability vector~p0. Thus~wgives thelong-termprobability distributionof thestatesof theMarkov :Sunny or meteorologiststudyingtheweatherin a regiondecidestoclassifyeach day as simplysunnyorcloudy. Afteranalyzingseveralyearsof weatherrecords,he nds: theday aftera sunny day is sunny 80%of thetime,andcloudy20%of thetime;and theday aftera cloudyday is sunny 60%of thetime,andcloudy40%of cansetupupa Markov chainto states:S1=sunny,andS2=cloudy.

4 ThetransitiondiagramisState 1 SunnyState 0:80:60:20:4 :(5)We seethatallentriesofParepositive, so theMarkov chainis regular.(Theconditionsof thede nitionaresatis edwhenn= 1.)To ndthelong-termprobabilitiesof sunny andcloudydays,we must ndtheeigenvectorofPassociatedwiththeeige nvalue = 1. We know fromLinearAlgebrathatif~vis aneigenvector,thenso isc~vforany constantc6= vector~wis theeigenvectorthatis alsoaprobability , thesumof theentriesof thevector~wmustbe solveP~w=~w(P I)~w=~0(6)NowP I= 0:20:60:2 0:6 (7)If youhave recentlystudiedLinearAlgebra,youcouldpro bablywritetheanswer downwithnofurtherwork,butwe willshow formtheaugmentedmatrixanduseGaussianelim ination:24 0:20 00:2 0 035!241 035(8)which tellsusw1= 3w2, orw1= 3s,w2=s, wheresis arbitrary, or~w=s 31 (9)Thevector~wmustbe a probability vector,sow1+w2= 1.

5 Thisimplies4s= 1 ors= 1=4. Thus~w= 3=41=4 :(10)Thisvectortellsus thatin thelongrun,theprobability is 3=4 thattheprocesswillbe in state1,and1=4 thattheprocesswillbe in otherwords,in thelongrun75%of thedays aresunny and25%of thedays :Regularor not?Herearea fewexamplesof determiningwhetheror nota Markovchainis SupposethetransitionmatrixisP= 1=302=31 :(11)We ndP2= (1=3)20(2=3)(1+ 1=3)1 ;P3= (1=3)30(2=3)(1+ 1=3 + (1=3)2) 1 ;(12)and,in general,Pn= (1=3)n0(2=3)(1+ 1=3 + + (1=3)n 1) 1 :(13)Theupper right entryinPnis 0 foralln, so theMarkov Here'sa simpleexamplethatis 0110 (14)ThenP2=I;P3=P;etc.(15)SincePn=Iifnis evenandPn=Pifnis odd,Palways hastwo chainis LetP=241=51=52=502=53=54=52=5035(16)Thet ransitionmatrixhastwo entriesthatarezero,butP2=249=257=255=251 2=2510=256=254=258=2514=2535:(17)Sinceal ltheentriesofP2arepositive, theMarkov chainis ChainsWe consideranotherimportant classof Markov stateSkof a Markov chainis calledanabsorbingstateif, oncetheMarkov chainsentersthestate,it otherwords,theprobability of leavingthestateis 1, andpjk= 0 forj6= Markov chainis calledanabsorbingchainif(i)it hasat leastoneabsorbingstate;and(ii)foreveryst atein thechain,theprobability of reachinganabsorbingstatein a nitenumberof stepsis chainis thatit willeventuallyenteran absorbingstate.

6 (Thisis a consequenceof thefactthatif a randomevent hasa probabilityp >0 of occurring,thentheprobability thatit does notoccuris 1 p, andtheprobability thatit does notoccurinntrialsis (1 p)n. Asn! 1, theprobability thattheevent does notoccurgoes to zero.)Thenon-absorbingstatesin anabsorbingMarkov chainhaskabsorbingstatesand`transient , in oursetof states,we listtheabsorbingstates rst,we seethatthetransitionmatrixhastheformAbso rbingStatesTransient Statesz}|{S1S2 Skz}|{Sk+1 Sk+` + +`266666666666410 0p1;k+1 p1;k+` 01pk;k+1 pk;k+`0 0pk+1;k+1 pk+1;k+`..0 0pk+`;k+1 pk+`;k+`3777777777775 Thatis, we may partitionPasP= IR0Q (18)whereIisk k,Risk `,0is` kandQis` `.Rgives theprobabilitiesof transitionsfromtransient statesto absorbingstates,whileQgives theprobabilitiesof transitionsfromtransientstatesto transient :P2= IR(I+Q)0Q2 ;P3= IR(I+Q+Q2)0Q3 ;(19)and,in general,Pn= IR(I+Q+Q2+ +Qn 1)0Qn = IRPn 1i=0Qi0Qn ;(20)5 Now I claimthat1limn!

7 1Pn= IR(I Q) 100 (21)Thatis, we !0asn!1, (I Q) rstclaim,Qn!0, meansthatin thelongrun,theprobability is 0 thattheprocesswillbein a transient otherwords,theprobability is 1 canderive thesecondclaimas +Q+Q2+ (22)ThenQU=Q1Xi=0Qi=Q+Q2+Q3+ = (I+Q+Q2+Q3+ ) I=U I:(23)ThenQU=U IimpliesU U Q=IU(I Q) =IU= (I Q) 1;(24)which is thesecondclaim.(Theclaimscanbe rigorouslyjusti ed,butforourpurposes,theabovearguments willsu ce.)ThematrixR(I Q) (I Q) 1gives theprobabilitiesof endingupin each of theabsorbingstates,giventhattheprocessst artedin theithtransient moreinformationthatwe cangleanfrom(I Q) 1. For convenience,callthetransientstatesT1,T2, .. ,T`. (SoTj=Sk+j.) LetV(Ti; Tj) be theexpectednumber of timesthattheprocessis in stateTi, given thatit startedinTj. (Vstandsforthenumber of \visits".)

8 AlsorecallthatQgives theprobabilitiesof transitionsfromtransient statesto transient states,soqij= Prob(Staten+ 1 isTijStatenisTj)(25)I claimthatV(Ti; Tj) satis esthefollowingequation:V(Ti; Tj) =eij+qi1V(T1; Tj) +qi2V(T2; Tj) + +qi`V(T`; Tj)(26)whereeij=(1ifi=j0otherwise(27)1 Thereis a slight abuseof notationin usethesymbol0to mean\amatrixof zerosof theappropriatesize".Thetwo0's in thelower leftis` k, whilethe0in thelower right is` `.6 Why?Considerjustthetermqi1V(T1; Tj). GiventhattheprocessstartedinTj,V(T1; Tj) givestheexpectednumber of timesthattheprocesswillbe inT1. Thenumberqi1gives theprobabilityof makinga transitionfromT1toTi. Therefore,theproductqi1V(T1; Tj) gives theexpected numberof transitionsfromT1toTi, giventhattheprocessstartedinTj. Similarly,qi2V(T2; Tj) gives theexpectednumber of transitionsfromT2toTi, andso of expectedtransitiontoTiisqi1V(T1; Tj) +qi2V(T2; Tj) + +qi`V(T`; Tj).)

9 Theexpectednumber of transitionsinto a stateis thesameas theexpectednumber of timesthattheprocessis in a state,exceptin theprocessstarted,sincethereis no\transition"into why thetermeijis includedin (26). Whenwe considerV(Ti; Ti), we have to add1 to theexpectednumber oftransitionsintoTito getthecorrectexpectednumber of timesthattheprocesswas (26)is actuallya setof`2equations,oneforeach possible(i; j). In fact,it is justonecomponent of a (T1; T1)V(T1; T2) V(T1; T`)V(T2; T1)V(T2; T2)..V(T`; T1)V(T`; T`)37775(28)Thenequation(26)is the(i; j) entryin thematrixequationN=I+QN:(29)(Youshouldch eck thisyourself!) Solving(29)givesN QN=I(I Q)N=IN= (I Q) 1(30)Thus the(i; j) entryof (I Q) 1gives theexpectednumber of timesthattheprocessis in theithtransient state,giventhatit startedin thejthtransient followsthatthesumof theithcolumnofNgives theexpectednumber of timesthattheprocesswillbe in sometransient state,giventhattheprocessstartedin thejthtransient :TheCoinand Die thisgametherearetwo players, coin,andDiehasa : Whenit isCoin's turn,heor she thecointurnsupheads, thecointurnsuptails, it isDie's turn.

10 Whenit isDie's turn,he or thedieturnsup1, thedieturnsup6, it isCoin's , isCoin's turn,theprobability is 1=2 thatCoinwillwinand1=2 thatit willbecomeDie' isDie's turn,theprobabilitiesare 1=6 thatDiewillrolla1andwin,7 1=6 thatDiewillrolla6andit willbecomeCoin's turn,and 2=3 thatDiewillrolla2,3,4, or5andhave describe thisprocessas a Markov chain ,we de nefourstatesof theprocess: State1:Coinhaswonthegame. State2:Diehaswonthegame. State3: It isCoin's turn. State4: It isDie's represent thepossibleoutcomesin thefollowingtransitiondiagram:State 1 Coin WinsState 3 Coin s TurnState 2 Die WinsState 4 Die s Turn112/31/21/61/21/6 Thisis anabsorbingMarkov andState2, in which oneoftheplayershaswonthegame,andthetrans ient statesareState3 1= : : : : : : : : : : : : : : : : : 1=22=33777777775= IR0Q (31)whereR= 1=2001=6 andQ= 01=61=22=3 :(32)We ndI Q= 1 1=6 1=21=3 ;(33)8soN= (I Q) 1= 4=32=324 ;(34)andR(I Q) 1= 2=31=31=32=3 (35)Recallthatthe rstcolumnofR(I Q) 1gives theprobabilitiesof enteringState1 or State2 iftheprocessstartsin State3.