Networking Theory and Fundamentals - Lecture 6

Tham khảo tài liệu 'networking theory and fundamentals - lecture 6', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Networking Theory and Fundamentals - Lecture 6 TCOM 501: Networking Theory & Fundamentals Lecture 6 February 19, 2003 Prof. Yannis A. Korilis 1 Topics 6-2 Time-Reversal of Markov Chains Reversibility Truncating a Reversible Markov Chain Burke’s Theorem Queues in Tandem Time-Reversed Markov Chains 6-3 {Xn: n=0,1,…} irreducible aperiodic Markov chain with transition probabilities Pij ∑ ∞ Pij = 1, i = 0,1, ... j =0 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? Time-Reversed Markov Chains 6-4 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} Time-Reversed Markov Chains 6-5 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 Reversibility 6-6 Stochastic process {X(t)} is called reversible if (X(t1), X(t2),…, X(tn)) and (X(τ-t1), X(τ-t2),…, X(τ-tn)) have the same probability distribution, for all τ, t1,…, tn Markov chain {Xn} is reversible if and only if the transition probabilities of forward and reversed chains are equal Pij = Pij* or equivalently, if and only if π i Pij = π j Pji , i, j = 0,1, ... Detailed Balance Equations ↔ Reversibility Reversibility – Discrete-Time Chains 6-7 Theorem 1: If there exists a set of positive numbers {πj}, that sum up to 1 and satisfy: π i Pij = π j Pji , i, j = 0,1, ... Then: 1. {πj} is the unique stationary distribution 2. The Markov chain is reversible Example: Discrete-time birth-death processes are reversible, since they satisfy the DBE Example: Birth-Death Process 6-8 Sc S Pn −1,n Pn ,n +1 P01 0 1 2 n n+1 Pn ,n −1 Pn +1,n P10 Pn ,n P00 One-dimensional Markov chain with transitions only between neighboring states: Pij=0, if |i-j|>1 Detailed Balance Equations (DBE) π n Pn ,n +1 = π n +1Pn +1,n n = 0,1, ... Proof: GBE with S ={0,1,…,n} give: ∞ ∞ n n ∑∑π P =∑∑πP ⇒ π n Pn ,n +1 = π n +1Pn +1,n j ji i ij j =0 i = n +1 j = 0 i = n +1 Time-Reversed Markov Chains (Revisited) 6-9 Theorem 2: Irreducible Markov chain with transition probabilities Pij. If there exist: A set of transition probabilities Qij, with ∑j Qij=1, i ≥ 0, and A set of positive numbers {πj}, that sum up to 1, such that πi Pij = π j Q ji , i, j = 0,1, ... (1) Then: Qij are the transition probabilities of the reversed chain, and {πj} is the stationary distribution of the forward and the reversed chains Remark: Use to find the stationary distribution, by guessing the transition probabilities of the reversed chain – even if the process is not reversible Continuous-Time Markov Chains 6-10 {X(t): -∞< t 0) if and only if: p j ∑ i ≠ j q ji = ∑ i ≠ j pi ...