Burke's Theorem(continued) The state sequence, run backward in time, in steady state, is a Markov chain again and it can be easily shown that (e.g, M/M/1(Pn)=(Pn+)u A Markov chain is reversible if P*j=Pi Forward transition probabilities are the same as the backward probabilities If reversible, a sequence of states run backwards in time is statistically indistinguishable from a sequence run forward A chain is reversible iff p Pi=p Pji All birth/death processes are reversible Detailed balance equations must be satisfiedBurke’s Theorem (continued) • The state sequence, run backward in time, in steady state, is a Markov chain again and it can be easily shown that piP*ij = pj Pji (e.g., M/M/1 (p n)λ=(pn+1)µ) • A Markov chain is reversible if P*ij = Pij – Forward transition probabilities are the same as the backward probabilities – If reversible, a sequence of states run backwards in time is statistically indistinguishable from a sequence run forward • A chain is reversible iff pi Pij=pj Pji • All birth/death processes are reversible – Detailed balance equations must be satisfied Eytan Modiano Slide 3