Misplaced Pages

Kelly's lemma

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Theorem in probability theory

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. The theorem is named after Frank Kelly.

Statement

For a continuous time Markov chain with state space S and transition-rate matrix Q (with elements qij) if we can find a set of non-negative numbers q'ij and a positive measure π that satisfy the following conditions:

∑ j ∈ S q i j = ∑ j ∈ S q i j ′ ∀ i ∈ S π i q i j = π j q j i ′ ∀ i , j ∈ S , {\displaystyle {\begin{aligned}\sum _{j\in S}q_{ij}&=\sum _{j\in S}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 π is proportional to the stationary distribution for both processes.

Proof

Given the assumptions made on the qij and π we have

∑ i ∈ S π i q i j = ∑ i ∈ S π j q j i ′ = π j ∑ i ∈ S q j i ′ = π j ∑ i ∈ S q j i = π j , {\displaystyle \sum _{i\in S}\pi _{i}q_{ij}=\sum _{i\in S}\pi _{j}q'_{ji}=\pi _{j}\sum _{i\in S}q'_{ji}=\pi _{j}\sum _{i\in S}q_{ji}=\pi _{j},}

so the global balance equations are satisfied and the measure π is proportional to the stationary distribution of the original process. By symmetry, the same argument shows that π is also proportional to the stationary distribution of the reversed process.

References

  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. Vol. 51. pp. 39–59. doi:10.1007/0-387-21525-5_2. ISBN 978-0-387-00211-8.
Categories: