# Kolmogorov's criterion

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 a stationary Markov chain with transition matrix P is reversible if and only if its transition probabilities satisfy[1]

${\displaystyle p_{j_{1}j_{2}}p_{j_{2}j_{3}}\cdots p_{j_{n-1}j_{n}}p_{j_{n}j_{1}}=p_{j_{1}j_{n}}p_{j_{n}j_{n-1}}\cdots p_{j_{3}j_{2}}p_{j_{2}j_{1}}}$

for all finite sequences of states

${\displaystyle j_{1},j_{2},\ldots ,j_{n}\in S.}$

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

### 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,

${\displaystyle p_{ij}p_{jl}p_{lk}p_{ki}=p_{ik}p_{kl}p_{lj}p_{ji}.}$

## Continuous-time Markov chains

The theorem states that a continuous-time Markov chain with transition rate matrix Q is reversible if and only if its transition probabilities satisfy[1]

${\displaystyle q_{j_{1}j_{2}}q_{j_{2}j_{3}}\cdots q_{j_{n-1}j_{n}}q_{j_{n}j_{1}}=q_{j_{1}j_{n}}q_{j_{n}j_{n-1}}\cdots q_{j_{3}j_{2}}q_{j_{2}j_{1}}}$

for all finite sequences of states

${\displaystyle j_{1},j_{2},\ldots ,j_{n}\in S.}$

## References

1. ^ a b Kelly, Frank P. (1979). Reversibility and Stochastic Networks (PDF). Wiley, Chichester. pp. 21–25.