4. Markov Chains - Statistics

1 4. Markov Chains A discrete time process{Xn, n= 0,1,2, ..}with discretestate spaceXn {0,1,2, ..}is aMarkov chainif it has theMarkov property:P[Xn+1=j|Xn=i, Xn 1=in 1, .. , X0=i0]=P[Xn+1=j|Xn=i] In words, the past is conditionally independentof the future given the present state of theprocess or given the present state, the pastcontains no additional information on the futureevolution of the system. The Markov property is common in probabilitymodels because, by assumption, one supposesthat the important variables for the system beingmodeled are all included in the state space. We considerhomogeneousMarkov Chains forwhichP[Xn+1=j|Xn=i] =P[X1=j|X0=i].1 Example:physical systems. If the state spacecontains the masses, velocities and accelerations ofparticles subject to Newton s laws of mechanics,the system in Markovian (but not random!)

2 Example:speech recognition. Context can beimportant for identifying words. Context can bemodeled as a probability distrubtion for the nextword given the most recentkwords. This can bewritten as a Markov chain whose state is a vectorofkconsecutive :epidemics. Suppose each infectedindividual has some chance of contacting eachsusceptible individual in each time interval, beforebecoming removed (recovered or hospitalized).Then, the number of infected and susceptibleindividuals may be modeled as a Markov DefinePij=P Xn+1=j|Xn=i .LetP= [Pij]denote the (possibly infinite)transition matrixof theone-step transitionprobabilities. WriteP2ij=P k=0 PikPkj, corresponding tostandard matrix multiplication.

3 ThenP2ij=XkP Xn+1=k|Xn=i P Xn+2=j|Xn+1=k =XkP Xn+2=j, Xn+1=k|Xn=i (via the Markov property. Why?)=P [k Xn+2=j, Xn+1=k Xn=i =P Xn+2=j|Xn=i Generalizing this calculation:The matrix powerPnijgives then-step transi-tion The matrix multiplication identityPn+m=PnPmcorresponds to theChapman-KolmogorovequationPn+mij=P k=0 PnikPmkj. Let (n)be the (possibly infinite) row vector ofprobabilities at timen, so (n)i=P Xn=i .Then (n)= (0)Pn, using standardmultiplication of a vector and a matrix. Why?4 Example. SetX0= 0,and letXnevolves as aMarkov chain with transi-tion matrixP= 1/2 1/2 00 0 11 0 0 .021 1/2 1/2 1 1 Find (n)0=P[Xn= 0]by(i) using a probabilistic argument5(ii) using linear of States StatejisaccessiblefromiifPkij>0for somek 0.]

4 The transition matrix can be represented as adirected graphwith arrows corresponding topositive one-step transition probabilitiesjisaccessible fromiif there is a path example,01234.. Here,4is accessible from0, but not vice versa. iandjcommunicateif they are accessiblefrom each other. This is writteni j, and is anequivalence relation, meaning that(i)i i[reflexivity](ii) Ifi jthenj i[symmetry](iii) Ifi jandj ktheni k[transitivity]7 An equivalence relation divides a set (here, thestate space) into disjoint classes of equivalentstates (here, calledcommunication classes). A Markov chain isirreducibleif all the statescommunicate with each other, , if there isonly one communication class.

5 The communication class containingiisabsorbingifPjk= 0wheneveri jbuti6 k( , whenicommunicates withjbut not withk). An absorbing class can never be left. Apartial converse is..Example: Show that a communication class,once left, can never be StateihasperioddifPnii= 0whennis not amultiple ofdand ifdis the greatest integer withthis property. Ifd= : Show that all states in the samecommunication class have the same : This is obvi-ous by considering ageneric directed graphfor a periodic state:ii+1i+2i+d-1 .. 9 StateiisrecurrentifP re-enteri|X0=i] = 1,where{re-enteri}is the eventS n=1{Xn=i, Xk6=ifork= 1, .. , n 1}.Ifiis not recurrent, it istransient. LetS0= 0andS1, S2, ..be times of successivereturns toi, withNi(t) = max{n:Sn t}beingthe corresponding counting process.

6 Ifiis recurrent, thenNi(t)is a renewal process,since the Markov property gives independence ofinterarrival timesXAn=Sn Sn ii=E[XA1], theexpected returntimefori, we then have the following fromrenewal theory: P limt Ni(t)/t= 1/ ii|X0=i = 1 Ifi j,limn Pnk=1 Pkij/n= 1/ jj Ifiis aperiodic,limn Pnij= 1/ jjforj i Ifihas periodd,limn Pndii=d/ ii10 Ifiis transient, thenNi(t)is adefectiverenewal process. This is a generalization ofrenewal processes whereXA1, XA2, ..are still iid,abut we allowP[XA1= ]> :iis recurrent if and only ifP n=1 Pnii= .11 Example: Show that ifiis recurrent andi jthenjis : Ifiis recurrent andi j, show thatP never enter statej|X0=i = Ifiis transient, then ii= . Ifiis recurrentand ii< theniis said to bepositiverecurrent.

7 Otherwise, if ii= , : Ifi jandiis recurrent, theneitheriandjare both positive recurrent, or bothnull recurrent ( , positive/null recurrence is aproperty of communication classes).13 Random Walks Thesimple random walkis a Markov chainon the integers,Z={.. , 1,0,1,2, ..}withX0= 0andP Xn+1=Xn+ 1 =p,P Xn+1=Xn 1 = 1 : IfXncounts the number of successesminus the number of failures for a new medicalprocedure,Xncould be modeled as a randomwalk, withpthe success rate of the should the trial be stopped? Ifp= 1/2, the random walk issymmetric. The symmetric random inddimensions is avector valued Markov chain , with state spaceZd,X(d)0= (0, .. ,0). Two possible definitions are(i) LetX(d)n+1 X(d)ntake each of the2dpossibilities( 1, 1.)

8 , 1)with equalprobability.(ii) LetX(d)n+1 X(d)ntake one of the2dvalues( 1,0, .. ,0),(0, 1,0, .. ,0), ..with equalprobability. This is harder to : A biological signaling moleculebecomes separated from its receptor. It startsdiffusing, due to themal noise. Suppose thediffusion is well modeled by a random walk. Willthe molecule return to the receptor? If themolecule is constrained to a one-dimensional line?A two-dimensional surface? Three-dimensionalspace?Proposition: The symmetric random walk isnull recurrent whend= 1andd= 2, buttransient ford : The method is to employ Stirling sformula,n! nn+1/2e n 2 wherean bnmeanslimn (an/bn) = 1, to approximateP X(d)n=X(d)0 .Note: This is in HW 5. You are expected to solvethe simpler case (i), though you can solve (ii) ifyou want a bigger Distributions ={ i, i= 0,1.}

9 }is astationarydistributionforP= [Pij]if j=P i=0 iPijwith i 0andP i=0 i= 1. In matrix notation, j=P i=0 iPijis = Pwhere is a row : An irreducible, aperiodic, positiverecurrent Markov chain has a unique stationarydistribution, which is also thelimitingdistribution j= limn Pnij. Such Markov Chains are continued17 Irreducible Chains which are transient or nullrecurrent have no stationary distribution. Why? Chains which are periodic or which havemultiple communicating classes may havelimn Pnijnot existing, or depending oni. A chain started in a stationary distribution willremain in that distribution, , will result in astationaryprocess. If we can find any probability distributionsolving the stationarity equations = Pandwe check that the chain is irreducible andaperiodic, then we know that(i) The chain is positive recurrent.

10 (ii) is the unique stationary distribution.(iii) is the limiting :Monte Carlo Markov chain Suppose we wish to evaluateE h(X) whereXhas distribution ( ,P X=i = i). TheMonte Carloapproach is to generateX1, X2, .. Xn and estimateE h(X) 1nPni=1h(Xi) If it is hard to generate an iid sample from ,we may look to generate a sequence from aMarkov chain with limiting distribution . This idea, calledMonte Carlo MarkovChain (MCMC), was introduced byMetropolis and Hastings (1953). It has become afundamental computational method for thephysical and biological sciences. It is alsocommonly used for Bayesian statistical Algorithm(i) Choose a transition matrixQ= [qij](ii) SetX0= 0(iii) forn= 1,2, .. generateYnwithP Yn=j|Xn 1=i =qij.