6.041/6.431 17. Markov Chains - II

LECTURE 17 Markov Processes – II • Readings: Section 7.3 Lecture outline • Review • Steady-State behavior – Steady-state convergence theorem – Balance equations • Birth-death processes Review • Discrete state, discrete time, time-homogeneous – Transition probabilities pij – Markov property • rij(n)= P(Xn = j | X0 = i) • Key recursion: rij(n)= � k rik(n − 1)pkj Warmup 21 3 4 6 7 5 8 9 P(X1 =2,X2 =6,X3 =7 | X0 =1)= P(X4 =7 | X0 =2)= 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 • Recurrent class: collection of recurrent states that “communicate” to each other and to no other state Periodic states • The states in a recurrent class are periodic if they can be grouped into d> 1 groups so that all transitions from one group lead to the next group 12 3 4 7 5 6 8 9 Steady-State Probabilities • Do the rij(n) converge to some πj? (independent of the initial state i) • Yes, if: – recurrent states are all in a single class, and – single recurrent class is not periodic • Assuming “yes,” start from key recursion rij(n)=� k rik(n −1)pkj – take the limit as n →∞ πj =� k πkpkj, for all j – Additional equation: � j πj =1 Visit frequency interpretation πj =� k πkpkj • (Long run) frequency of being in j: πj • Frequency of transitions k →j: πkpkj • Frequency of transitions into j:� k πkpkj 1 2 j m ...... j pjj 1p1j 2p2j m pmj Example 21 0.5 0.5 0.8 0.2 Birth-death processes 30 m21 ...p0 1-p0 p1 1-p1-q1 q1 q2 qm 1-qm i+1i pi qi+1 πipi = πi+1qi+1 • Special case: pi = p and qi = q for all i ρ = p/q =load factor πi+1 = πi p q = πiρ πi = π0ρi , i =0, 1,...,m • Assume p