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]

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

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.

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}}.

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]

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

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

References

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

This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.