6.041 / 6.431 18. Markov Chains - III

LECTURE 20 Markov Processes – III Readings: Section 6.4 Lecture outline • Review of steady-state behavior • Probability of blocked phone calls • Calculating absorption probabilities • Calculating expected time to absorption Review • Assume a single class of recurrent states, aperiodic. Then, lim n!"rij(n) = !j where !j does not depend on the initial conditions lim n!"P(Xn = j | X0) = !j • !1, . . . , !m can be found as the unique solution of the balance equations !j =!k !kpkj together with !j !j = 1 Example2 1 0.5 0.5 0.8 0.2 !1 = 2/7, !2 = 5/7 • Assume process starts at state 1. • P(X1 = 1, and X100 = 1)= • P(X100 = 1 and X101 = 2) The phone company problem • Calls originate as a Poisson process, rate ! – Each call duration is exponentially distributed (parameter µ) – B lines available • Discrete time intervals of (small) length " • Balance equations: !#i−1 = iµ#i • #i = #0 !i µii! #0 = 1/B!i=0 !i µii! LECTURE 18 Review Markov Processes – III Assume a single class of recurrent states, • aperiodic;plus transient states. Then,Readings: Section 7.4 lim rij(n)= !jn!" where !j does not depend on the initial conditions: Lecture outline lim P(Xn = j | X0= i)= !jn!" Review of steady-state behavior • Probability of blocked phone calls • !1,..., !m can be found as the unique • solution to the balance equations • Calculating absorption probabilities !j = ! !kpkj, j =1, . . . , m, k • Calculating expected time to absorption together with ! !j =1 j Example 21 0.5 0.5 0.8 0.2 !1 =2/7, !2 =5/7 • Assume process starts at state 1. • P(X1 =1, and X100 = 1)= • P(X100 = 1 and X101 = 2) The phone company problem • Calls originate as a Poisson process, rate " – Each call duration is exponentially distributed (parameter µ) – B lines available • Discrete time intervals of (small) length # 0 1 Bi!1 i B-1 "# iµ# • Balance equations: "!i−1 = iµ!i • !i = !0 "i µii! !0 =1/B! i=0 "i µii! 4 4 4 Calculating absorption probabilities • What is the probability ai that: process eventually settles in state 4, given that the initial state is i? 21 3 0.3 0.5 0.2 0.8 0.4 0.6 4 0.2 51 1 For i = 4, ai = For i = 5, ai = ai = ! j pijaj, for all other i – unique solution Expected time to absorption 21 3 0.5 0.5 0.2 0.8 0.4 0.6 4 1 • Find expected number of transitions µi, until reaching the absorbing state, given that the initial state is i? µi = 0 for i = For all other i: µi = 1 + ! j pijµj – unique solution Mean first passage and recurrencetimes• Chain with one recurrent class; fix s recurrent • Mean first passage time from i to s: ti = E[min{n $ 0 such that Xn = s}|X0= i] • t1,t2, ..., tm are the unique solution to ts =0, ti = 1+ ! pij tj, for all i =%s j Mean recurrence time of s:• t&= E[min{n $ 1 such that Xn = s}|X0= s]s t& = 1+ "j psj tj• s MIT OpenCourseWare http://ocw.mit.edu 6.041 /6.431 Probabilistic Systems Analysis and Applied Probability Fall 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.