Theorem 9.10 -- Thomson's principle
ProvedMarkovMixing.thomson_principleLet be a network on a finite vertex set: a symmetric nonnegative conductance function with total conductance at every vertex, whose associated walk is irreducible. Fix distinct vertices . A flow from to is an antisymmetric edge function vanishing wherever does, satisfying the node law at every vertex except and ; its strength is the net flux out of , and a flow of strength one is a unit flow. The energy of a flow is
each undirected edge counted once. The effective resistance is defined through the voltage and the current as .
The theorem (Thomson's Principle, Theorem 9.10 of Levin–Peres–Wilmer) asserts:
- ;
- the infimum is attained — some unit flow (the current flow) has energy exactly .
Resistance is a variational quantity: any unit flow certifies an upper bound on it, which is the source of all flow-based hitting-time estimates.
import Definitions.Def_mm_network
namespace MarkovMixing
/-- **Theorem 9.10, Thomson's Principle** (LPW): for a connected network,
the effective resistance is the minimal energy of a unit flow from `a` to
`z`, and the minimum is attained. -/
theorem thomson_principle {V : Type*} [Fintype V] [DecidableEq V]
(c : V → V → ℝ) (hc : IsConductance c)
(hpos : ∀ x : V, 0 < vertexConductance c x)
(hirr : Irreducible (networkWalk c)) (a z : V) (haz : a ≠ z) :
effectiveResistance c a z =
sInf {r : ℝ | ∃ θ : V → V → ℝ,
IsFlow c θ a z ∧ flowStrength θ a = 1 ∧ r = flowEnergy c θ} ∧
∃ θ : V → V → ℝ, IsFlow c θ a z ∧ flowStrength θ a = 1 ∧
effectiveResistance c a z = flowEnergy c θ := by
sorry
end MarkovMixing