Kelly's lemma

In probability theory, Kelly's lemma states that for a stationary continuous time Markov chain, a process defined as the time-reversed process has the same stationary distribution as the forward-time process.^[1] The theorem is named after Frank Kelly.^[2]^[3]^[4]^[5]

Statement

For a continuous time Markov chain with state space S and transition rate matrix Q (with elements q_ij) if we can find a set of numbers q'_ij and π_i summing to 1 where^[1]

{\begin{aligned}\sum _{j\neq i}\pi _{i}q'_{ij}&=\sum _{j\neq i}q_{ij}\quad \forall i\in S\\\pi _{i}q_{ij}&=\pi _{j}q_{ji}'\quad \forall i,j\in S\end{aligned}}

then q'_ij are the rates for the reversed process and π_i are the stationary distribution for both processes.

Proof

Given the assumptions made on the q_ij and π_i we can see

\sum _{i\neq j}\pi _{i}q_{ij}=\sum _{i\neq j}\pi _{j}q'_{ji}=\pi _{j}\sum _{i\neq j}q_{ji}=-\pi _{j}q_{jj}

so the global balance equations are satisfied and the π_i are a stationary distribution for both processes.

References

1 2 Boucherie, Richard J.; van Dijk, N. M. (2011). Queueing Networks: A Fundamental Approach. Springer. p. 222. ISBN 144196472X.
↑ Kelly, Frank P. (1979). Reversibility and Stochastic Networks. J. Wiley. p. 22. ISBN 0471276014.
↑ Walrand, Jean (1988). An introduction to queueing networks. Prentice Hall. p. 63 (Lemma 2.8.5). ISBN 013474487X.
↑ Kelly, F. P. (1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.
↑ Asmussen, S. R. (2003). "Markov Jump Processes". Applied Probability and Queues. Stochastic Modelling and Applied Probability. 51. pp. 39–59. doi:10.1007/0-387-21525-5_2. ISBN 978-0-387-00211-8.

This article is issued from Wikipedia - version of the 9/3/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.