Chapter 8: Markov Chains - Auckland

1 149 Chapter 8: Markov far, we have examined several stochastic processes usingtransition diagrams and First-Step processes can be written as{X0, X1, X2, ..},whereXtis thestate at the transition diagram,Xtcorresponds towhich box we are in at the Gambler s Ruin (Section ),Xtis the amount of money the gamblerpossesses after tosst. In the model for gene spread (Section ),Xtis thenumber of animals possessing the harmful allele A in processes that we have looked at via the transition diagram have a crucialproperty in common:Xt+1depends only does notdepend uponX0, X1, .. , Xt like this are calledMarkov :Random Walk (see Chapter 4)time tnone of these steps matter for time t+1??time t+1In a Markov chain , thefuture depends onlyupon the present:NOT upon the text-book imageof a Markov chain hasa flea hopping about atrandom on the verticesof the transition diagram,according to the probabilities transition diagram above shows a system with 7 possible states:state spaceS={1,2,3,4,5,6,7}.

2 Questions of interest Starting from state 1, what is the probability of ever reaching state 7? Starting from state 2, what is the expected time taken to reach state 4? Starting from state 2, what is the long-run proportion of time spent instate 3? Starting from state 1, what is the probability of being in state 2 at timet? Does the probability converge ast , and if so, to what?We have been answering questions like the first two using first-step analysissince the start of STATS 325. In this Chapter we develop a unified approachto all these questions using the matrix of transition probabilities, called thetransition Markov chain is the processX0, X1, X2, ..Definition:Thestateof a Markov chain at timetis thevalue example, ifXt= 6, we saythe process is in state6at :Thestate spaceof a Markov chain ,S, is the set of values that eachXtcan take. For example,S={1,2,3,4,5,6,7}.LetShave sizeN(possibly infinite).

3 Definition:Atrajectoryof a Markov chain isa particular set of values forX0, X1, X2, ..For example, ifX0= 1,X1= 5, andX2= 6, then the trajectory up to timet= 2 is 1,5, generally, if we refer to the trajectorys0, s1, s2, s3, .., we mean thatX0=s0,X1=s1,X2=s2,X3=s3, .. Trajectory is just a word meaning path . Markov PropertyThe basic property of a Markov chain is thatonly the most recent point in thetrajectory affects what happens is called theMarkov means thatXt+1depends uponXt, but it does not depend uponXt 1,.. , X1, formulate the Markov Property in mathematical notation as follows:P(Xt+1=s|Xt=st, Xt 1=st 1, .. , X0=s0) =P(Xt+1=s|Xt=st),for allt= 1,2,3, ..and for all statess0, s1, .. , st, :P(Xt+1=s|Xt=st, Xt 1=st 1, Xt 2=st 2, .. , X1=s1, X0=s0) |{z}distribution ofXt+1depends onXtbut whatever happened before timetdoesn t :Let{X0, X1, X2, ..}be a sequence of discrete random variables.

4 Then{X0, X1, X2, ..}is aMarkov chainifit satisfies the Markov property:P(Xt+1=s|Xt=st, .. , X0=s0) =P(Xt+1=s|Xt=st),for allt= 1,2,3, ..and for all statess0, s1, .. , st, Transition MatrixWe have seen many examples oftransition diagramsto describe Markovchains. The transition diagram is so-called because it shows the transitionsbetween different can also summarize the probabilitiesin amatrix: HotColdXtHot Coldz}|{Xt+1153 The matrix describing the Markov chain is called thetransition is the most important tool for analysing Markov Matrix listallstatesXtlist all states- z}|{Xt+1?6insertprobabilitiespijrows add to 1 rows add to 1 The transition matrix is usually given the symbolP= (pij).In the transition matrixP: the ROWS represent NOW, or FROM (Xt); the COLUMNS represent NEXT, or TO (Xt+1); entry(i, j)is the CONDITIONAL probability that NEXT=j, given thatNOW=i: the probability of going FROM stateiTO (Xt+1=j|Xt=i).

5 Notes:1. The transition matrixPmust listallpossible states in the state asquare matrix(N N), becauseXt+1andXtboth take values in thesame state spaceS(of sizeN).3. TherowsofPshould eachsum to 1:NXj=1pij=NXj=1P(Xt+1=j|Xt=i) =NXj=1P{Xt=i}(Xt+1=j) = simply states thatXt+1musttake one of the listed ThecolumnsofPdonotin general sum to :Let{X0, X1, X2, ..}be a Markov chain with state spaceS, whereShas sizeN(possibly infinite). Thetransition probabilitiesof the Markovchain arepij=P(Xt+1=j|Xt=i)fori, j S, t= 0,1,2, ..Definition:Thetransition matrixof the Markov chain isP= (pij). : setting up the transition matrixWe can create a transition matrix for any of the transition diagrams we haveseen in problems throughout the course. For example, check the matrix :Tennis game at (W)VENUSAHEAD (A)VENUSBEHIND (B)pqppqqVENUSLOSES (L)DEUCE (D)DABWLDABWL 0pq0 0q0 0p0p0 0 0q0 0 0 1 00 0 0 0 1 RevisionNotationcol jaijrow iNNbyALetAbe anN writeA= (aij), (i, j) element ofAis written both asaijand (A) for matrixA2we might write (A2) multiplication=LetA= (aij) andB= (bij)beN product matrix isA B=AB, with elements (AB)ij=NXk= notation for a matrix squaredLetAbe anN Nmatrix.

6 Then(A2)ij=NXk=1(A)ik(A)kj=NXk= of a matrix by a vectorLetAbe anN Nmatrix, and let be anN 1 column vector: = N .We can pre-multiplyAby Tto get a 1 Nrow vector, TA= ( TA)1, .. ,( TA)N , with elements( TA)j=NXi=1 transition probabilitiesLet{X0, X1, X2, ..}be a Markov chain with state spaceS={1,2, .. , N}.Recall that the elements of the transition matrixPare defined as:(P)ij=pij=P(X1=j|X0=i) =P(Xn+1=j|Xn=i) for the probability of making a transition FROM stateiTO statejin aSINGLE :what is the probability of making a transition from stateito statejovertwosteps? what isP(X2=j|X0=i)?156We are seekingP(X2=j|X0=i). Use thePartition Theorem:P(X2=j|X0=i) =Pi(X2=j)(notation of Ch 2)=NXk=1Pi(X2=j|X1=k)Pi(X1=k)(Partition Thm)=NXk=1P(X2=j|X1=k, X0=i)P(X1=k|X0=i)=NXk=1P(X2=j|X1=k)P(X1= k|X0=i)( Markov Property)=NXk=1pkjpik(by definitions)=NXk=1pikpkj(rearranging)= (P2)ij.(see Matrix Revision)The two-step transition probabilities are therefore givenbythe matrixP2:P(X2=j|X0=i) =P(Xn+2=j|Xn=i) = P2 ijfor transitions:We can findP(X3=j|X0=i) similarly, but conditioning onthe state at time 2:P(X3=j|X0=i) =NXk=1P(X3=j|X2=k)P(X2=k|X0=i)=NXk=1pkj P2 ik= (P3) three-step transition probabilities are therefore given by the matrixP3:P(X3=j|X0=i) =P(Xn+3=j|Xn=i) = P3 ijfor case:t-step transitionsThe above working extends to show that thet-step transition probabilities aregiven by the matrixPtfor anyt:P(Xt=j|X0=i) =P(Xn+t=j|Xn=i) = Pt ijfor have proved the following :Let{X0, X1, X2.}

7 }be a Markov chain withN NtransitionmatrixP. Then thet-step transition probabilities are given by the is,P(Xt=j|X0=i) = Pt also follows thatP(Xn+t=j|Xn=i) = Pt ijfor anyn. ofXtLet{X0, X1, X2, ..}be a Markov chain with state spaceS={1,2, .. , N}.Now eachXtis a random variable, so it has aprobability can write the probability distribution ofXtas anN example, considerX0. Let be anN 1 vector denoting the probabilitydistribution ofX0: = 1 N = P(X0= 1)P(X0= 2)..P(X0=N) 158In the flea model, this corresponds tothe flea choosing at random which vertexit starts offfrom at time 0, such thatP(flea chooses vertexito start) = :we will writeX0 Tto denote that the row vector of probabilitiesis given by the row vector distribution ofX1 Use the Partition Rule, conditioning onX0:P(X1=j) =NXi=1P(X1=j|X0=i)P(X0=i)=NXi=1pij iby definitions=NXi=1 ipij= TP j.(pre-multiplication by a vector from Section ).

8 This shows thatP(X1=j) = TP jfor row vector TPis thereforethe probability distribution ofX1:X0 TX1 distribution ofX2 Using the Partition Rule as before, conditioning again onX0:P(X2=j) =NXi=1P(X2=j|X0=i)P(X0=i) =NXi=1 P2 ij i= TP2 row vector TP2is therefore the probability distribution ofX2:X0 TX1 TPX2 results are summarized in the following :Let{X0, X1, X2, ..}be a Markov chain withN NtransitionmatrixP. If the probability distribution ofX0is given by the 1 Nrow vector T, then the probability distribution ofXtis given by the 1 Nrow vector TPt. That is,X0 T Xt :The distribution ofXtisXt distribution ofXt+1isXt+1 TPt+ one step in the Markov chain corresponds tomultiplying byPon :Thet-step transition matrix isPt(Theorem ).The (t+ 1)-step transition matrix isPt+ , taking one step in the Markov chain corresponds tomultiplying byPonthe that a trajectory is a sequenceof values forX0, X1.

9 , of the Markov Property,we can find the probability of anytrajectory by multiplying togetherthe starting probability and allsubsequent single-step :LetX0 (34,0,14,0,0,0,0). What is the probability of the trajectory1, 2, 3, 2, 3, 4?P(1,2,3,2,3,4) =P(X0= 1) p12 p23 p32 p23 p34=34 35 1 23 1 13= in formal notation using the Markov Property:LetX0 T. We wish to find the probability of the trajectorys0, s1, s2, .. , (X0=s0, X1=s1, .. , Xt=st)=P(Xt=st|Xt 1=st 1, .. , X0=s0) P(Xt 1=st 1, .. , X0=s0)=P(Xt=st|Xt 1=st 1) P(Xt 1=st 1, .. , X0=s0) ( Markov Property)=pst 1,stP(Xt 1=st 1|Xt 2=st 2, .. , X0=s0) P(Xt 2=st 2, .. , X0=s0)..=pst 1,st pst 2,st 1 .. ps0,s1 P(X0=s0)=pst 1,st pst 2,st 1 .. ps0,s1 Example: distribution ofXtand trajectory zooms aroundthe vertices of the transitiondiagram opposite. LetXtbePurpose-flea s state at timet(t= 0,1, ..).(a) Find the transition matrix, :P= 0 (b) FindP(X2= 3|X0= 1).

10 P(X2= 3|X0= 1) = P2 13= = + + : we only need one element of the matrixP2, so don t lose exam time byfinding the whole matrix.(c) Suppose that Purpose-flea is equally likely to start on any vertex at time the probability distribution this info, the distribution ofX0is T= 13,13,13 . We needX1 TP. TP=(131313) 0 = 131313 .ThusX1 13,13,13 and thereforeX1is also equally likely to be 1, 2, or (d) Suppose that Purpose-flea begins at vertex 1 at time 0. Find the probabilitydistribution distribution ofX0is now T= (1,0,0). We needX2 TP2. TP2=(1 0 0) 0 0 =( ) 0 = ( ).ThusP(X2= 1) = ,P(X2= 2) = ,P(X2= 3) = that it is quickest to multiply the vector by the matrix first: we don t need tocomputeP2in entirety.(e) Suppose that Purpose-flea is equally likely to start on any vertex at time the probability of obtaining the trajectory (3, 2, 1, 1,3).