Rahul Sharma (Editor)

Kolmogorov's criterion

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
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.

Contents

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

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 , … , j n ∈ S .

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

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 i j p j l p l k p k i = p i k p k l p l j p j i .

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

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 , … , j n ∈ S .

References

Kolmogorov's criterion Wikipedia
(Text) CC BY-SA