TCOM 501: Networking Theory & FundamentalsTopicsTime-Reversed Markov ChainsTime-Reversed Markov ChainsTime-Reversed Markov ChainsReversibilityReversibility – Discrete-Time ChainsExample: Birth-Death ProcessTime-Reversed Markov Chains (Revisited)Continuous-Time Markov ChainsReversed Continuous-Time Markov ChainsReversibility – Continuous-Time ChainsExample: Birth-Death ProcessReversed 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 ServersExample: M/M/2 Queue with Heterogeneous ServersMultidimensional Markov ChainsExample: Two Independent M/M/1 QueuesExample: Two Independent M/M/1 QueuesTruncation of a Reversible Markov ChainExample: Two Queues with Joint BufferBurke’s TheoremBurke’s TheoremBurke’s TheoremBurke’s TheoremSingle-Server Queues in TandemSingle-Server Queues in TandemQueues 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,...jiijiPj∞===∑01, 0,1, ...ijjPi∞===∑0Pr{ } lim Pr |π {}nnnjXXX 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,...πjjiijiPPij==6-5Time-Reversed Markov ChainsProof of Proposition 1:*12212212212212222{| , ,, }{| , ,, }{| , ,, }{, , ,, }{, ,, }{,, |,ij m m m m k kmm m mkknn n nkknn n nkknn nkknnkknnPPY jY iY i Y iPX j X iX i X iPX j X iX i X iPX jX iX i X iPX iX i X iPX i X i X jXττ τ τ−− −−−+−+ −+++ +++ +++ +++ +== = = === = = === = = ==== ==== =====………………1122 1 1111111}{ , }{,, |}{}{, }{}π{|}{}{| } |}{} π{nnnnkknnnnnn mnji jnmnnniiPX jX iPX i XPX j X i PYiX iPX iPX jX iPX iPPX i X jPjXYijPX i++++++++++−============== ====== = ==…*00 0ππππ ππjjiiij i j ji jii iiPPP∞∞ ∞== ====∑∑ ∑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 ijPP=ππ, , 0,1,...iij j jiPPij==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,...iij j jiPPij==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,1nnP+1,nnP+,nnP,1nnP−1,nnP−01P10P00PSSc,1 1 1,ππ 0,1,...nnn n n nPPn+++==,1 1 1,01 01ππππnnjji iij nnn n n njin jinPPP 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 ∑jQij=1, i ≥ 0, and A set of positive numbers {πj}, that sum up to 1, such that Then: Qijare 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)iij j jiPQij==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,...jji iijij ijpq pqj≠≠==∑∑limPr{ ( ) Pr{ ( ) | (0)} }tjXXt tXpjij→∞=====π /, , 0,1,...π /jjjjjiijiiipqjννν≠=≡=∑∑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,...,jjiijipqqijijp==≠*, 0,1,...jji i ijji jiij ij iji jiiipq p qqqippν≠≠≠≠=====∑∑∑∑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 ijqq=, , 0,1,...,iij j jipq p q ijij==≠, , 0,1,...,iij j jipq p q ijij==≠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+1n20λ1µnλ1nµ+1λ2µ1nλ−nµ,1 ,1,,0,||1ii i ii i ijqqqijλµ+−===−>11, 0,1,...nn n nppnλµ++==1101 01nnjji i ij n n n njin jinpqpqppλµ∞∞++==+ ==+=⇒=∑∑ ∑∑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≠iqij, i ≥ 0, and A set of positive numbers {pj}, that sum up