TCOM 501: Networking Theory & FundamentalsTopicsTime-Reversed Markov ChainsSlide 4Slide 5ReversibilityReversibility – Discrete-Time ChainsExample: Birth-Death ProcessTime-Reversed Markov Chains (Revisited)Continuous-Time Markov ChainsReversed Continuous-Time Markov ChainsReversibility – Continuous-Time ChainsSlide 13Reversed Continuous-Time Markov Chains (Revisited)Reversibility: TreesKolmogorov’s Criterion (Discrete Chain)Kolmogorov’s Criterion (Continuous Chain)Kolmogorov’s Criterion (proof)Example: M/M/2 Queue with Heterogeneous ServersSlide 20Multidimensional Markov ChainsExample: Two Independent M/M/1 QueuesSlide 23Truncation of a Reversible Markov ChainExample: Two Queues with Joint BufferBurke’s TheoremSlide 27Slide 28Slide 29Single-Server Queues in TandemSlide 31Queues in TandemQueues in Tandem: State-Dependent Service Rates1TCOM 501: Networking Theory & FundamentalsLecture 6February 19, 2003Prof. Yannis A. Korilis6-2TopicsTime-Reversal of Markov ChainsReversibilityTruncating a Reversible Markov ChainBurke’s TheoremQueues in Tandem6-3Time-Reversed Markov Chains{Xn: n=0,1,…} irreducible aperiodic Markov chain with transition probabilities PijUnique stationary distribution (πj > 0) if and only if:Process in steady state: 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?0π π , 0,1,...j i ijiP j�== =�01, 0,1,...ijjP i�== =�0Pr{ } lim Pr |π { }nnn jX XX ij j��= = == =6-4Time-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:{Yn} has the same stationary distribution πj with the forward chain {Xn}*π, , 0,1,...πj jiijiPP i j= =6-5Time-Reversed Markov Chains*1 2 21 2 21 2 21 2 21 2 22 2{ | , , , }{ | , , , }{ | , , , }{ , , , , }{ , , , }{ , , | ,ij m m m m k km m m m k kn n n n k kn n n n k kn n n k kn n k k n nP P Y j Y i Y i Y iP X j X i X i X iP X j X i X i X iP X j X i X i X iP X i X i X iP X i X i X j Xt t t t- - -- - + - + - ++ + ++ + ++ + ++ + += = = = == = = = == = = = == = = === = == = ==KKKKKK1 12 2 1 111111 1} { , }{ , , | } { }{ , }{ }π{ | } { }{ | } | }{ }π{n nn n k k n nn nn n mnji jnmn nn ii P X j X iP X i XP X j X i P Yi X i P X iP X j X iP X iPP X i X j PjXY ijP X i++ + + ++++++-= = == = = == == === = == == = = = ==K*0 0 0ππ π π ππj jii ij i j ji ji i iiPP P� � �= = == = =� � �Proof of Proposition 1:6-6Reversibility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 equalor equivalently, if and only ifDetailed Balance Equations ↔ Reversibility*ij ijP P=π π , , 0,1,...i ij j jiP P i j= =6-7Reversibility – Discrete-Time ChainsTheorem 1: If there exists a set of positive numbers {πj}, that sum up to 1 and satisfy:Then:1. {πj} is the unique stationary distribution2. The Markov chain is reversible Example: Discrete-time birth-death processes are reversible, since they satisfy the DBEπ π , , 0,1,...i ij j jiP P i j= =6-8Example: Birth-Death ProcessOne-dimensional Markov chain with transitions only between neighboring states: Pij=0, if |i-j|>1Detailed Balance Equations (DBE)Proof: GBE with S ={0,1,…,n} give:0 1 n+1n2, 1n nP+1,n nP+,n nP, 1n nP-1,n nP-01P10P00PSSc, 1 1 1,π π 0,1,...n n n n n nP P n+ + += =, 1 1 1,0 1 0 1π π π πn nj ji i ij n n n n n nj i n j i nP P P P� �+ + += = + = = += � =�� ��6-9Time-Reversed Markov Chains (Revisited)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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π π , , 0,1,... (1)i ij j jiP Q i j= =6-10Continuous-Time Markov Chains{X(t): -∞< t <∞} irreducible aperiodic Markov chain with transition rates qij, i≠jUnique stationary distribution (pi > 0) if and only if:Process in steady state – e.g., started at t =-∞: If {πj}, is the stationary distribution of the embedded discrete-time chain:, 0,1,...j ji i iji j i jp q p q j� �= =� �limPr{ ( ) Pr{ ( ) | (0)} }tjXX t t Xp j ij��= = == =π /, , 0,1,...π /j jj j jii ji iip q jnnn�= � =��6-11Reversed Continuous-Time Markov ChainsReversed chain {Y(t)}, with Y(t)=X(τ-t), for arbitrary τ>0 Proposition 2:1. {Y(t)} is a continuous-time Markov chain with transition rates:2. {Y(t)} has the same stationary distribution {pj} with the forward chainRemark: The transition rate out of state i in the reversed chain is equal to the transition rate out of state i in the forward chain*, , 0,1,...,j jiijip qq i j i jp= = �*, 0,1,...j ji i ijj i j iij ij ij i j ii ip q p qq q ip pn� �� �= = = = =� �� �6-12Reversibility – Continuous-Time ChainsMarkov chain {X(t)} is reversible if and only if the transition rates of forward and reversed chains are equal or equivalentlyDetailed Balance Equations ↔ ReversibilityTheorem 3: If there exists a set of positive numbers {pj}, that sum up to 1 and satisfy:Then:1. {pj} is the unique stationary distribution2. The Markov chain is reversible *,ij ijq q=, , 0,1,...,i ij j jip q p q i j i j= = �, , 0,1,...,i ij j jip q p q i j i j= = �6-13Example: Birth-Death ProcessTransitions only between neighboring statesDetailed Balance EquationsProof: GBE with S ={0,1,…,n} give:M/M/1, M/M/c, M/M/∞0 1 n+1n20l1mnl1nm+1l2m1nl-nm, 1 , 1, , 0, | | 1i i i i i i ijq q q i jl m+ -= = = - >1 1, 0,1,...n n n np p nl m+ += =1 10 1 0 1n nj ji i ij n n n nj i n j i np q p q p pl m� �+ += = + = = += � =�� ��SSc6-14Reversed Continuous-Time Markov Chains (Revisited)Theorem 4: Irreducible continuous-time Markov chain with transition rates qij. If there exist:A set of transition rates φij, with ∑j≠i φij=∑j≠i