Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.8 — Kolmogorov's criterion and the canonical invariant measure

Proved
SerfozoStochasticNetworks.kolmogorov_criterion

by naimengye · Sep 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainprobabilitystochastic-systems

Let qqq be a non-negative rate function on a state space with the two-way communication property — q(x,y)>0q(x,y)>0q(x,y)>0 exactly when q(y,x)>0q(y,x)>0q(y,x)>0 — and suppose qqq is irreducible, every state being reachable from every other along a path of positive rates. Write ρ(x,y)=q(x,y)/q(y,x)\rho(x,y)=q(x,y)/q(y,x)ρ(x,y)=q(x,y)/q(y,x).

Then all of the following hold.

  1. qqq is reversible if and only if Kolmogorov's criterion holds: for every nnn and every sequence x0,…,xnx_0,\dots,x_nx0​,…,xn​ with xn=x0x_n=x_0xn​=x0​,
∏i=1nq(xi−1,xi)=∏i=1nq(xi,xi−1).\prod_{i=1}^{n}q(x_{i-1},x_i)=\prod_{i=1}^{n}q(x_i,x_{i-1}).i=1∏n​q(xi−1​,xi​)=i=1∏n​q(xi​,xi−1​).
  1. qqq is reversible if and only if the rate ratios are path-independent: for any two paths with the same initial state and the same final state, the products ∏iρ(xi−1,xi)\prod_i\rho(x_{i-1},x_i)∏i​ρ(xi−1​,xi​) along them agree.
  2. **If qqq is reversible then, for every choice of origin x0x^0x0, there is a strictly positive π\piπ with π(x0)=1\pi(x^0)=1π(x0)=1 satisfying the detailed balance equations and given by
π(x)=∏i=1nρ(xi−1,xi)\pi(x)=\prod_{i=1}^{n}\rho(x_{i-1},x_i)π(x)=i=1∏n​ρ(xi−1​,xi​)

for every path x0=x0,…,xn=xx^0=x_0,\dots,x_n=xx0=x0​,…,xn​=x from the origin to xxx.**

The criterion is a condition on the rates alone, with no reference to an unknown measure, and the third part turns it into a construction: the invariant measure is read off as a product of rate ratios along any path.

Formalization Note Kolmogorov's criterion is asserted for arbitrary closed sequences, not merely for closed paths, exactly as the book states it. Under two-way communication the two readings coincide: if some rate along the sequence vanishes, so does its reverse, and both products are zero.

In the third part the measure is produced rather than defined: the conclusion asserts the existence of a π\piπ that agrees with the ratio product along every path from the origin, which is the content of expression (2.9) without having to choose a path for each state. A path of length zero gives the empty product 111, consistent with π(x0)=1\pi(x^0)=1π(x0)=1.

Irreducibility is used for the third part, to reach every state from the origin, and for the implication from the criterion to reversibility. Reversibility here means the existence of some positive measure satisfying detailed balance; no normalization is claimed, and whether π\piπ can be normalized to a probability distribution is not part of the statement.

The state space is an arbitrary type and qqq an arbitrary non-negative function, so the statement applies verbatim to a discrete-time chain with qqq read as transition probabilities, as the book points out.

Preamble
import Mathlib
import Definitions.Def_SerfozoStochasticNetworks_Reversible
Formal statement
namespace SerfozoStochasticNetworks

theorem kolmogorov_criterion {E : Type*} (q : E → E → ℝ)
    (hq : ∀ x y, 0 ≤ q x y) (htw : TwoWay q) (hirr : IsIrreducible q) :
    (IsReversible q ↔ KolmogorovCriterion q) ∧ (IsReversible q ↔ RatioInvariance q) ∧
    (IsReversible q → ∀ x₀ : E, ∃ π : E → ℝ, (∀ x, 0 < π x) ∧ π x₀ = 1 ∧ DetailedBalance q π ∧
      ∀ (n : ℕ) (p : Fin (n + 1) → E), IsPath q p → p 0 = x₀ →
        π (p (Fin.last n)) = pathRatio q p) := by sorry

end SerfozoStochasticNetworks
Source
Serfozo, Introduction to Stochastic Networks, Springer 1999, p. 50 (PDF p. 63), Theorem 2.8: "The following statements are equivalent. (i) The transition function q is reversible. (ii) (Kolmogorov Criterion) For each n and x0, x1, ..., xn in E with xn = x0, prod_{i=1}^n q(x_{i-1}, x_i) = prod_{i=1}^n q(x_i, x_{i-1}). (iii) For each path x0, x1, ..., xn in E, the product prod_{i=1}^n rho(x_{i-1}, x_i) depends on x0, ..., xn and n only through x0, xn. If q is reversible, then an invariant measure for it is pi(x) = prod_{i=1}^n rho(x_{i-1}, x_i), x in E\{x0}, (2.9) and pi(x0) = 1, where x0, x1, ..., xn = x is any path and x0 is an arbitrary state viewed as an origin." sha256 919f20ee082ec19faa80bdd923a5529fce9c4b6d3264fdb77c5efa64256bb463
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me