Transcription of MARKOV CHAINS: BASIC THEORY - University of Chicago
{{id}} {{{paragraph}}}
Example: confidence
MARKOV CHAINS: BASIC THEORY - University of Chicago
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,..edare the standard unit vectors inZd. In other terms, the simple random walkmoves, at each step, to a randomly chosen nearest transpositionMarkov chain on the permutation groupSN(the set of allpermutations ofNcards) is a MARKOV chain whose transition probabilities arep(x, x)=1/ N2 for all transpositions ;p(x,y)= a permutation that exchanges two cards.
Communication is an equivalence relation. In particular, it is transitive: if icommunicates with j and j communicates with k then i communicates with k. 4 MARKOV CHAINS: BASIC THEORY The proof is an exercise. It follows that the state space Xis uniquely partitioned into commu-nicating classes ...
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: