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 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}\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,\dots ,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}.$

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}=\frac{{\pi }_i{p}_{ij}}{{\pi }_j}$.

Now assume that the equality is fulfilled. Fix states $s$ and $t$. Then

$\text{P}(X_{n+1}=t,X_n=i_n,\dots ,X_0=s|X_0=s)$$=p_{s{i}_1}{p}_{i_1{i}_2}\cdots p_{i_{n}t}$$=\frac{p_{st}}{p_{ts}}{p}_{t{i}_n}{p}_{i_n{i}_{n-1}}\cdots p_{i_{1}s}$$=\frac{p_{st}}{p_{ts}}\text{P}(X_{n+1}$$=s,X_n$$=i_1,\dots ,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,\dots ,i_n$. Thus we obtain $p_{st}^{(n)}=\frac{p_{st}}{p_{ts}}{p}_{ts}^{(n)}$ so $\frac{p_{st}^{(n)}}{p_{ts}^{(n)}}=\frac{p_{st}}{p_{ts}}$. Send $n$ to $\mathrm{\infty }$ on the left side of the last. From the properties of the chain follows that $\underset{n\to \mathrm{\infty }}{\lim }{p}_{ij}^{(n)}={\pi }_j$, hence $\frac{{\pi }_t}{{\pi }_s}=\frac{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}\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,\dots ,j_n\in S.$

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