Proposition 10.6 -- the commute time identity
ProvedMarkovMixing.commute_time_identityLet 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.
import Definitions.Def_mm_network
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