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.

2 , 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}.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?

3 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.

4 For example,S={1,2,3,4,5,6,7}.LetShave sizeN(possibly infinite).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.

5 , 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. 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.

6 , 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).

7 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).

8 : 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.

9 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?

10 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.