The following will be discussed in this chapter: Time-Reversal of Markov Chains, reversibility, truncating a reversible markov chain, burke’s theorem, queues in tandem. | Lecture Networking theory & fundamentals - Chapter 6 TCOM 501: Networking Theory & Fundamentals Lecture 6 February 19, 2003 Prof. Yannis A. Korilis 1 6-2 Topics Time-Reversal of Markov Chains Reversibility Truncating a Reversible Markov Chain Burke’s Theorem Queues in Tandem 6-3 Time-Reversed Markov Chains {Xn: n=0,1, } irreducible aperiodic Markov chain with transition probabilities Pij ∑ ∞ j =0 Pij = 1, i = 0,1,. Unique stationary distribution (πj > 0) if and only if: π j = ∑ i =0 π i Pij , ∞ j = 0,1,. Process in steady state: Pr{ X n = j} = π j = lim Pr{ X n = j | X 0 = i} n →∞ Starts at n=-∞, that is {Xn: n = ,-1,0,1, } Choose initial state according to the stationary distribution How does {Xn} look “reversed” in time? 6-4 Time-Reversed Markov Chains Define Yn=Xτ-n, for arbitrary τ>0 {Yn} is the reversed process. Proposition 1: {Yn} is a Markov chain with transition probabilities: π j Pji Pij* = , i, j = 0,1,. πi {Yn} has the same stationary distribution πj with the forward chain {Xn} 6-5 Time-Reversed Markov Chains Proof of Proposition 1: Pij* = P{Ym = j | Ym −1 = i, Ym − 2 = i2 , , Ym − k = ik } = P{ X τ − m = j | X τ − m +1 = i, X τ − m + 2 = i2 , , X τ − m + k = ik } = P{ X n = j | X n +1 = i, X n + 2 = i2 , , X n + k = ik } P{ X n = j , X n +1 = i, X n + 2 = i2 , , X n + k = ik } = P{ X n +1 = i, X n + 2 = i2 , , X n + k = ik } P{ X n + 2 = i2 , , X n + k = ik | X n = j , X n +1 = i}P{ X n = j , X n +1 = i} = P{ X n + 2 = i2 , , X n + k = ik | X n +1 = i}P{ X n +1 = i} P{ X n = j , X n +1 = i} = = P{ X n = j | X n +1 = i} = P{Ym = j | Ym −1 = i} P{ X n +1 = i} P{ X n +1 = i | X n = j}P{ X n = j} Pji π j = = P{ X n +1 = i} πi π j Pji ∑ i =0 π P = ∑ i =0 πi = π j ∑ i =0 Pji = π j ∞ * ∞ ∞ i ij πi 6-6 Reversibility Stochastic process {X(t)} is called reversible if (X(t1), X(t2), , X(tn)) and
