Kelly’s Lemma

Kelly’s Lemma provides a way of using the time reversal of a Markov chain to calculate its stationary distribution. In theory, it is just a rewrite of the stationary distribution and time-reversal results for continuous-time chains. However, in application, it is different; you can take a guess at the time reversal of a chain $Q’$, and if you are right, i.e., if it checks out in Kelly’s Lemma, you get the stationary distribution as a consequence.

Theorem (Kelly’s Lemma). Let X be a continuous-time Markov chain with Q-matrix Q = (q(x,y) : x,y \in \mathcal{X}). Suppose we can find positive rates Q' = (q'(x,y) : x,y \in \mathcal{X}) and a probability distribution \pi = (\pi(x) : x \in \mathcal{X}) such that

  • \sum_x \pi(x) = 1
  • q'(x) = q(x) for all x \in \mathcal{X}
  • \pi(x)\, q'(x,y) = \pi(y)\, q(y,x) for all x \ne y

Then Q' is the Q-matrix of the time-reversed process, and \pi is the stationary distribution.

The idea of Kelly’s Lemma is that we can sometimes guess the time reversal of a Markov chain and use this to compute the stationary distribution.

Proof.

\displaystyle \sum_{k \ne j} \pi(k)\, q(k,j) = \sum_{k \ne j} \pi(j)\, q'(j,k) = \pi(j)\, q'(j) = \pi(j)\, q(j)

Thus \pi is a stationary distribution for X. By a similar argument, \pi is also stationary for the chain with rates q'.

The process X is Markov, so conditioning on the present separates past and future. This implies that the reversed process X^R is also Markov.

We now compute the transition rates of the time-reversed process:

\displaystyle \frac{1}{h} \mathbb{P}(X^R(t+h) = j \mid X^R(t) = i) = \frac{1}{h} \mathbb{P}(X(-t-h) = j \mid X(-t) = i)

\displaystyle = \frac{1}{h} \frac{\mathbb{P}(X(-t-h) = j)}{\mathbb{P}(X(-t) = i)} \mathbb{P}(X(-t) = i \mid X(-t-h) = j)

\displaystyle = \frac{1}{h} \frac{\pi(j)}{\pi(i)} \mathbb{P}(X(-t+h) = i \mid X(-t) = j)

\displaystyle \longrightarrow \frac{\pi(j)}{\pi(i)} q(j,i) \quad \text{as } h \to 0

\square

Leave a comment