Proof of Kolmogorov's Cycle Criterion

From Local Balance to Cycle Products

Detailed balance compares transitions one edge at a time: the weight assigned to a state, multiplied by the probability of leaving along an edge, must match the corresponding quantity for the reversed edge. Kolmogorov’s cycle criterion turns this local condition into a test around closed paths. Its converse is useful too: when all cycle products match, ratios along paths can be used to build a reversible measure. The key issue in that construction is ensuring that the answer does not depend on which path is chosen.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with finite or countable state space \(S\) and transition matrix \(P=(p_{ij})\). Assume throughout the main criterion that the chain is irreducible: for every \(i,j\in S\), there is an \(n\ge0\) such that \(p_{ij}^{(n)}>0\). A finite path \(v_0,v_1,\ldots,v_\ell\) is allowed if each transition along it has positive probability, meaning \(p_{v_{r-1}v_r}>0\) for \(1\le r\le\ell\). A cycle is an allowed path with \(v_\ell=v_0\); intermediate states may repeat. Its forward product is the product of the probabilities along the path, and its reverse product is the product along the path traversed in reverse.

For a cycle, the reverse product is meaningful even before reverse transitions have been shown positive: it is the product of the corresponding entries of \(P\), and may be zero. Under irreducibility, the cycle condition itself will force the reverse transitions of every positive edge to be positive.

Proof. Consider a cycle \(v_0,v_1,\ldots,v_\ell=v_0\). Detailed balance on each step gives \(m_{v_{r-1}}p_{v_{r-1}v_r}=m_{v_r}p_{v_rv_{r-1}}\). Multiply these \(\ell\) equalities. The product of the measure factors on the left is \(\prod_{r=1}^{\ell}m_{v_{r-1}}\), while on the right it is \(\prod_{r=1}^{\ell}m_{v_r}\); these are equal because the lists of states differ only by a cyclic shift. The remaining factors are the forward and reverse transition products, respectively. Cancelling the common positive measure product proves the cycle condition. This argument also applies when states repeat, since each equality is included with its multiplicity. \(\square\)

Constructing a Reversible Measure from Cycles

The proposition proves necessity. For sufficiency, choose a reference state \(o\), assign it weight \(m_o=1\), and define the weight of another state by multiplying transition-probability ratios along a path from \(o\). This only works if every edge has a reverse edge, and it defines a single weight only if different paths give the same ratio. The cycle condition supplies both facts.

Proof. Necessity is the proposition. To prove sufficiency, assume the cycle condition holds on every finite cycle.

Step 1: positive transitions have positive reverses. Suppose \(p_{ij}>0\). Irreducibility gives an allowed path from \(j\) back to \(i\). Prepending the edge \(i\to j\) makes a cycle whose forward product is positive. By the cycle condition, its reverse product is positive too. That reverse product contains the factor \(p_{ji}\), so \(p_{ji}>0\). Thus every positive transition has a positive reverse.

Step 2: define weights and establish path independence. Fix \(o\in S\). For any allowed path \(v_0=o,v_1,\ldots,v_\ell=i\), define its ratio by \(R(v_0,\ldots,v_\ell)=\prod_{r=1}^{\ell}(p_{v_{r-1}v_r}/p_{v_rv_{r-1}})\). Every denominator is positive by Step 1. Set \(m_i=R(v_0,\ldots,v_\ell)\). For \(i=o\), the path of length zero gives \(m_o=1\). For any two allowed paths \(A,B\) from \(o\) to \(i\), follow \(A\) by the reverse of \(B\). This is an allowed cycle by Step 1. Its forward product is the forward product of \(A\) times the reverse product of \(B\); its reverse product is the reverse product of \(A\) times the forward product of \(B\). Equality of these products implies \(R(A)=R(B)\). Therefore \(m_i\) is independent of the chosen path, is positive and finite, and is well-defined.

Step 3: verify detailed balance. If \(p_{ij}>0\), append the edge \(i\to j\) to a path from \(o\) to \(i\). By the definition and path independence, \(m_j=m_i p_{ij}/p_{ji}\), so \(m_i p_{ij}=m_jp_{ji}\). If \(p_{ij}=0\), Step 1 implies \(p_{ji}=0\), so the same balance equality holds with both sides zero. Hence \(m\) is a positive reversible measure.

Step 4: uniqueness up to scale. Let \(\widetilde m\) be another positive reversible measure. On every allowed edge \(i\to j\), detailed balance gives \(\widetilde m_j/\widetilde m_i=p_{ij}/p_{ji}=m_j/m_i\). Along any allowed path from \(o\) to \(i\), multiplying these ratios gives \(\widetilde m_i/\widetilde m_o=m_i/m_o=m_i\), because \(m_o=1\). Thus \(\widetilde m_i=\widetilde m_o m_i\) for every state \(i\), as required. \(\square\)

The construction gives a measure, not automatically a probability distribution. When \(Z=\sum_{i\in S}m_i<\infty\), define \(\pi_i=m_i/Z\). Then \(\sum_i\pi_i=1\) and \(\pi_i p_{ij}=\pi_jp_{ji}\). Summing over \(i\) gives \(\sum_i\pi_i p_{ij}=\pi_j\sum_i p_{ji}\) only if the sum is over the wrong index; instead, detailed balance gives \(\sum_i\pi_i p_{ij}=\pi_j\sum_i p_{ji}\) with \(p_{ji}\) interpreted as transitions out of \(j\) to \(i\), whose sum over \(i\) is \(1\). Hence \(\pi P=\pi\). If \(Z=\infty\), the constructed reversible measure still satisfies detailed balance, but cannot be normalized to a probability distribution.

Why Irreducibility Matters

The irreducibility assumption prevents one-way transitions from escaping the cycle tests. For instance, on \(S=\{1,2\}\), take \(p_{11}=0\), \(p_{12}=1\), \(p_{21}=0\), and \(p_{22}=1\). Both rows sum to \(1\). There is no allowed cycle using the edge \(1\to2\): once the chain reaches \(2\), it stays there. The cycle condition on allowed cycles therefore holds vacuously, but detailed balance for the pair \((1,2)\) would require \(m_1\cdot1=m_2\cdot0\), impossible for positive \(m_1\). Irreducibility was used in the proof to complete each positive edge into a cycle and thereby force its reverse to be positive.

Common mistake. A cycle-product check on one convenient cycle is not enough to establish reversibility unless the criterion has been checked for every cycle, or an argument establishes that the checked cycles determine all others. In the failed-chain example, using only the path \(1\to3\) suggested \(m_3=3\), but the path \(1\to2\to3\) suggested \(m_3=6\). Treating either path as authoritative would conceal the contradiction. Always check that path ratios are consistent; the cycle condition is precisely what guarantees that consistency for an irreducible chain.