MARKOV CHAINS: BASIC THEORY

← Back to document page

MARKOV CHAINS: BASIC THEORY1. MA R KOVCH A INS A ND T H EIRTR A NSI T IO NPRO BA B ILIT I and First (discrete-time) MARKOV chain with (finite or countable) state spaceXis a se-quenceX0,X1, . . . ofX valued random variables such that for all statesi,j,k0,k1, and alltimesn=0, 1, 2, . . . ,(1)P(Xn+1=j Xn=i,Xn 1=kn 1, . . .)=p(i,j)wherep(i,j)depends only on the statesi,j, and not on the timenor the previous stateskn 1,n 2, . . . .The numbersp(i,j)are called thetransition probabilitiesof the random walkon the integer latticeZdis the MARKOV chain whose tran-sition probabilities arep(x,x ei)=1/(2d) x Zdwheree1,e2.

A stochastic matrix is a square nonnegative matrix all of whose row sums are 1. A substochastic matrix is a square nonnegative matrix all of whose row sums are 1. A doubly stochastic matrix is a stochastic matrix all of whose column sums are 1. Observe that if you start with a stochastic matrix and delete the rows and columns indexed

  Stochastic