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
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 {\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
j 1 , j 2 , … , j n ∈ S . {\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. 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 i j p j l p l k p k i = p i k p k l p l j p j i . {\displaystyle p_{ij}p_{jl}p_{lk}p_{ki}=p_{ik}p_{kl}p_{lj}p_{ji}.}
Proof Let X {\displaystyle X} be the Markov chain and denote by π {\displaystyle \pi } its stationary distribution (such exists since the chain is positive recurrent). If the chain is reversible, the equality follows from the relation p j i = π i p i j π j {\displaystyle p_{ji}={\frac {\pi _{i}p_{ij}}{\pi _{j}}}} . Now assume that the equality is fulfilled. Fix states s {\displaystyle s} and t {\displaystyle t} . Then
P ( X n + 1 = t , X n = i n , … , X 0 = s | X 0 = s ) {\displaystyle {\text{P}}(X_{n+1}=t,X_{n}=i_{n},\ldots ,X_{0}=s|X_{0}=s)}
… excerpt ends here. Continue reading the full article.
