口 Burkes theoren An interesting property of an M/M/1 queue, which greatly simplifies combining these queues into a network, is the surprising fact that the output of an M/M/1 queue with arrival rate n is a Poisson process of rate n This is part of Burke's theorem, which follows from reversibility A Markov chain has the property that P[future present, past]= P[future present] Conditional on the present state, future states and past states are ndependent PLpast present, future]= P[past present =>PDX可a+1=,Xn+22]=Px到x-=P�Burke’s Theorem • An interesting property of an M/M/1 queue, which greatly simplifies combining these queues into a network, is the surprising fact that the output of an M/M/1 queue with arrival rate λ is a Poisson process of rate λ – This is part of Burke's theorem, which follows from reversibility • A Markov chain has the property that – P[future | present, past] = P[future | present] Conditional on the present state, future states and past states are independent P[past | present, future] = P[past | present] => P[Xn=j |Xn+1 =i, Xn+2=i2,...] = P[Xn=j | Xn+1=i] = P*ij Eytan Modiano Slide 2