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.

gollark: I wonder why they decided to make TOSLINK optical. I don't know of any other consumer fiber-optic connection things around.

gollark: The description on the Amazon page I found implies they do the opposite thing.

gollark: It's not like it's busy and active every minute of the day or something.

gollark: It would make sense for multiple choice. But with just five questions that's an impractical amount of multiple choices.

gollark: Put in "I'm very lucky, or you wouldn't have picked up this resume in the first place".

References

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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[bou-1] Boucherie, Richard J.; van Dijk, N. M. (2011). Queueing Networks: A Fundamental Approach. Springer. p. 222. ISBN 144196472X.

[2] Kelly, Frank P. (1979). Reversibility and Stochastic Networks. J. Wiley. p. 22. ISBN 0471276014.

[3] Walrand, Jean (1988). An introduction to queueing networks. Prentice Hall. p. 63 (Lemma 2.8.5). ISBN 013474487X.

[4] Kelly, F. P. (1976). "Networks of Queues". Advances in Applied Probability. 8 (2): 416–432. doi:10.2307/1425912. JSTOR 1425912.

[5] 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.