A reversible Markov chain is an electrical network: states are nodes, and the conductance turns hitting probabilities into voltages and hitting times into resistances. This dictionary, going back to Kakutani and popularized by Doyle and Snell, converts probabilistic estimates into the physical laws of circuits — series/parallel reduction, energy minimization, monotonicity under edge removal. Chapters 9–11 of Levin–Peres–Wilmer, Markov Chains and Mixing Times (AMS, 2009) develop the dictionary and its two crown results: the commute time identity of Chandra–Raghavan–Ruzzo–Smolensky–Tiwari, , and the Matthews method bounding cover times by hitting times with harmonic-number precision.
A network is a symmetric nonnegative conductance function on pairs of vertices; the associated walk moves with probabilities
where , and . A function is harmonic at if . The voltage with boundary values at and at is , the harmonic extension of its boundary data; the current flowing out of has strength , and the effective resistance is . A flow from to is an antisymmetric edge function obeying the node law off ; its energy is . Hitting times , their expectations, the Green's function , the maximal hitting time , and the cover time (expected time to visit every state, maximized over starts) all use the trajectory calculus of Mission I.
This is Proposition 10.6, the commute time identity — the exact bridge between the probabilistic and electrical sides, and the engine of the transience/recurrence theory of Mission XII.
Reversibility and stationarity of the network walk with (§9.1); Proposition 9.1 (existence and uniqueness of harmonic extensions with given boundary values, ); Lemma 9.6 (the Green's function identity ); Theorem 9.10 (Thomson's principle: is the minimal energy of a unit flow, attained); Theorem 9.12 (Rayleigh monotonicity: lowering conductances raises effective resistance); Lemma 10.1 (the random target lemma: does not depend on ); Corollary 10.8 (the resistance triangle inequality); Theorem 11.2 (Matthews: ); Proposition 11.4 (the matching Matthews lower bound over subsets).
The results. The commute time identity computes hitting times from circuit reductions — this is how hitting times on trees, tori and glued graphs are actually evaluated — and, through Thomson and Rayleigh, makes them monotone under graph operations, something invisible probabilistically. The Matthews bounds pin cover times up to a factor in complete generality; they are the tool behind cover-time results for lamplighter groups in Mission XI's sequel. Green's function identities feed Mission XII's recurrence theory, where decides transience.
Formalizing them. Mathlib has graph Laplacians but no electrical network theory: no effective resistance, no flows, no energy, no Thomson/Rayleigh, no hitting or cover times. This mission publishes that layer over the trajectory calculus of Mission I. It is the most reusable single block of the series outside Missions I–II: effective resistance on finite networks is of independent interest to combinatorics (spanning trees, spectral sparsification) well beyond mixing times.
The identity chain behind the goal runs: Green's function of the stopped walk escape probability (via harmonic uniqueness) the Aldous–Fill occupation identity for stopping times with — each step is a manipulation of infinite series of trajectory sums whose exchange steps (splitting a path at its first visit, last-exit decompositions) need summability from Mission I's Lemma 1.13. Thomson's principle is a finite-dimensional convex minimization: existence of the minimizer needs a compactness or completing-the-square argument, and the identification of the minimizer with the current flow needs the cycle law; the naive "differentiate the energy" route must be made exact. Matthews' method is a clean but genuinely clever argument — a uniformly random ordering of targets and the harmonic-number telescoping; the formal cost is the exchangeability of the randomized order against the chain, handled combinatorially.
Networks are functions with a symmetry-and-nonnegativity predicate; loops are permitted; connectivity enters as irreducibility of the induced walk. The voltage is defined probabilistically as (the book's harmonic characterization is Proposition 9.1); is the reciprocal of the explicit current strength, with total division junk when are disconnected — statements carry irreducibility so this does not arise. Energy counts each undirected edge once, formalized as half the ordered double sum, and handles absent edges. Cover times are tail sums of the explicit event "some state unvisited". The Matthews lower bound is stated with an arbitrary lower bound for the pairwise hitting times of the subset — equivalent to the book's min over pairs and easier to instantiate.
Welcome contributions: series/parallel reduction laws, the cycle and node law API for flows, escape-probability lemmas — all reused in Mission XII's infinite-network arguments.
namespace MarkovMixing
/-- **Proposition 10.6, the Commute Time Identity** (LPW), the capstone of
Chapters 9–11: for the random walk on a network,
`E_a(τ_b) + E_b(τ_a) = c_G · R(a ↔ b)`. -/
theorem commute_time_identity {V : Type*} [Fintype V] [DecidableEq V]
(c : V → V → ℝ) (hc : IsConductance c)
(hpos : ∀ x : V, 0 < vertexConductance c x)
(hirr : Irreducible (networkWalk c)) (a b : V) (hab : a ≠ b) :
expSetHitTime (networkWalk c) a {b} + expSetHitTime (networkWalk c) b {a} =
totalConductance c * effectiveResistance c a b := by
sorry
end MarkovMixing
Let be a network on a finite vertex set : a symmetric nonnegative conductance function with total vertex conductance everywhere, carrying the irreducible walk . Write for the total conductance of the network, for the expected number of steps for the walk started at to first reach , and for the effective resistance, defined through the voltage and current as .
The theorem (the Commute Time Identity, Proposition 10.6 of Levin–Peres–Wilmer, the capstone of Chapters 9–11) asserts: for any two distinct vertices ,
The expected round-trip time between two vertices is exactly the total conductance times the effective resistance between them. This single identity converts the entire electrical toolkit — series/parallel reduction, Thomson's principle, Rayleigh monotonicity — into exact computations and bounds for hitting and cover times of reversible chains.
No open leaves. Every sub-goal is proved or awaiting decomposition.