Theorem 2.2 — a process whose communication graph is a tree is reversible
ProvedSerfozoStochasticNetworks.tree_reversibleLet the state space be finite, let be a non-negative rate function with no self-loops and with the two-way communication property, and let be a strictly positive invariant measure of . If the communication graph of — the simple graph joining distinct whenever either rate between them is non-zero — is a tree, then satisfies the detailed balance equations.
So on a tree there is nothing to check: connectedness plus the absence of cycles forces reversibility, and the equilibrium measure is the product of rate ratios along the unique path from a fixed origin.
Formalization Note "Tree" is connected and acyclic, in the standard graph-theoretic sense. The conclusion is detailed balance for the given ; since is positive, this also makes the rate function reversible.
The state space is assumed finite. Serfozo assumes the process is ergodic, and the proof sums the balance equations over one side of a cut; on an infinite state space that rearrangement requires an integrability condition that "ergodic" leaves implicit. With finitely many states the rearrangement is unconditional. The general case is not asserted here.
Absence of self-loops, , matches the convention for a jump process and keeps the diagonal out of the cut argument; two-way communication is the standing assumption of the chapter, and without it the conclusion is false — a directed cycle with all rates positive one way and zero the other has a tree-free graph but is not reversible.
import Mathlib import Definitions.Def_SerfozoStochasticNetworks_Reversible
namespace SerfozoStochasticNetworks
theorem tree_reversible {E : Type*} [Fintype E] (q : E → E → ℝ) (π : E → ℝ)
(hq : ∀ x y, 0 ≤ q x y) (htw : TwoWay q) (hdiag : ∀ x, q x x = 0)
(hπ : ∀ x, 0 < π x) (hinv : IsInvariant q π) (htree : (commGraph q).IsTree) :
DetailedBalance q π := by sorry
end SerfozoStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.