6.041 / 6.431 16. Markov Chains - I

LECTURE 16 Markov Processes – I • Readings: Sections 7.1–7.2 Lecture outline • Checkout counter example • Markov process definition • n-step transition probabilities • Classification of states Checkout counter model • Discrete time n =0, 1,... • Customer arrivals: Bernoulli(p) – geometric interarrival times • Customer service times: geometric(q) • “State” Xn: number of customers at time n 30 9 1021 ...Finite state Markov chains • Xn: state after n transitions – belongs to a finite set, e.g., {1, . . . , m} – X0 is either given or random • Markov property/assumption: (given current state, the past does not matter) pij = P(Xn+1 = j | Xn = i) = P(Xn+1 = j | Xn = i, Xn−1, . . . , X0) • Model specification: – identify the possible states – identify the possible transitions – identify the transition probabilities n-step transition probabilities • State occupancy probabilities, given initial state i: rij(n)= P(Xn = j | X0 = i) 1 k j m ... i r i1(n-1) ... Time 0 Time n-1 Time n r ik(n-1) r im(n-1) p1j pkj pmj – Key recursion: rij(n)= m! k=1 rik(n − 1)pkj – With random initial state: P(Xn = j)= m! i=1 P(X0 = i)rij(n) Example 21 0.5 0.5 0.8 0.2 n =0 n =1 n =2 n = 100 n = 101 r11(n) r12(n) r21(n) r22(n) Generic convergence questions: • Does rij(n) converge to something? 1 2 3 0.5 0.5 1 1 r22(n)=n odd: r22(n)=n even: • Does the limit depend on initial state? 1 2 3 4 0.3 0.3 0.4 r11(n)= r31(n)= r21(n)= Recurrent and transient states State i is recurrent if:• starting from i,and from wherever you can go,there is a way of returning to i• If not recurrent, called transient 21 3 4 6 7 5 8 – i transient:P(Xn = i) 0,"i visited finite number of times Recurrent class:• collection of recurrent states that “communicate” with each other and with no other state MIT OpenCourseWarehttp://ocw.mit.edu 6.041 /6.431 Probabilistic Systems Analysis and Applied ProbabilityFall 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.