Kolmogorov's criterion explained

In probability theory, Kolmogorov's criterion, named after Andrey Kolmogorov, is a theorem giving a necessary and sufficient condition for a Markov chain or continuous-time Markov chain to be stochastically identical to its time-reversed version.

Discrete-time Markov chains

The theorem states that an irreducible, positive recurrent, aperiodic Markov chain with transition matrix P is reversible if and only if its stationary Markov chain satisfies^[1]

p _{j _{1} j _{2}} p _{j _{2} j _{3}} … p _{j _{n-1} j _{n}} p _{j _{n} j _{1}} = p _{j _{1} j _{n}} p _{j _{n} j _{n-1}} … p _{j _{3} j _{2}} p _{j _{2} j _{1}}

for all finite sequences of states

j _{1,} j _{2,} \ldots, j _{n} \in S .

Here p_ij are components of the transition matrix P, and S is the state space of the chain.

That is, the chain-multiplication along any cycle is the same forwards and backwards.

Example

Consider this figure depicting a section of a Markov chain with states i, j, k and l and the corresponding transition probabilities. Here Kolmogorov's criterion implies that the product of probabilities when traversing through any closed loop must be equal, so the product around the loop i to j to l to k returning to i must be equal to the loop the other way round,

p _{ij} p _{jl} p _{lk} p _{ki} = p _{ik} p _{kl} p _{lj} p _{ji} .

Proof

Let

X be the Markov chain and denote by \pi its stationary distribution (such exists since the chain is positive recurrent).

If the chain is reversible, the equality follows from the relation

p _{ji} = (\pi _{i} p _{ij})/(\pi _{j}) .

Now assume that the equality is fulfilled. Fix states

s and t . ThenP (X _{n+1} = t,X _{n} = i _{n,\ldots,X} _{0} = s|X _{0=s)} = p _{si _{1}} p _{i _{1i} _{2}} … p _{i _{nt}} = (p _{st})/(p _{ts}) p _{ti _{n}} p _{i _{n} i _{n-1}} … p _{i _{1s}} = (p _{st})/(p _{ts}) P (X _{n+1} = s,X _{n} = i _{1,\ldots,X} _{0} = t|X _{0=t)} . Now sum both sides of the last equality for all possible ordered choices of n states i _{1,i} _{2,\ldots,i} _{n} . Thus we obtain p ^{(n)} _{st} = (p _{st})/(p _{ts}) p ^{(n)} _{ts} so (p ^{(n)} _{st})/(= p ^{(n)} _{ts}) (p _{st})/(p _{ts}) . Send n to inf ty on the left side of the last. From the properties of the chain follows that \lim _{n\toinfty} p ^{(n)} _{ij} = \pi _{j} , hence (\pi _{t})/(= \pi _{s}) (p _{st})/(p _{ts}) which shows that the chain is reversible.

Continuous-time Markov chains

The theorem states that a continuous-time Markov chain with transition rate matrix Q is, under any invariant probability vector, reversible if and only if its transition probabilities satisfy

q _{j _{1} j _{2}} q _{j _{2} j _{3}} … q _{j _{n-1} j _{n}} q _{j _{n} j _{1}} = q _{j _{1} j _{n}} q _{j _{n} j _{n-1}} … q _{j _{3} j _{2}} q _{j _{2} j _{1}}

for all finite sequences of states

j _{1,} j _{2,} \ldots, j _{n} \in S .

The proof for continuous-time Markov chains follows in the same way as the proof for discrete-time Markov chains.

References

1. Book: Kelly, Frank P.. Frank P. Kelly

   . Frank P. Kelly. Reversibility and Stochastic Networks . Wiley, Chichester. 1979. 21–25.