Kirchhoff's node law from the random-walk game
ProvedKellyStochasticNetworks.kirchhoff_from_random_walkSection 4.1 opens with a game. You perform a symmetric random walk on a graph with transition rates until you hit a set of vertices, and you are then paid a reward depending on the vertex you hit. Let be the expected reward starting from . Conditioning on the first vertex the walk jumps to gives, for every ,
This is exactly Kirchhoff's node law. For every ,
Reading as the voltage at node and as the conductance — the inverse resistance — of the edge , each term is the current flowing into node along that edge, and the identity says the currents into any interior node sum to zero.
The equivalence is the first instance of the chapter's theme: a purely local rule, here the random walk, produces a global pattern that is the solution of a network-wide problem. The symmetry , which is what makes the walk reversible, is exactly what turns the averaging identity into a conservation law.
Formalization Note The vertex set is a finite index type and is a finite subset of it; edges that are absent are represented by a zero rate, as in the book. The hypothesis that the total rate out of an interior vertex is positive is what makes the averaging identity meaningful. The probabilistic derivation of the averaging identity is not part of the statement, which is the implication from it to the node law.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop
namespace KellyStochasticNetworks
theorem kirchhoff_from_random_walk {n : ℕ} (γ : Fin n → Fin n → ℝ) (p : Fin n → ℝ)
(S : Finset (Fin n)) (hsym : ∀ i j, γ i j = γ j i)
(hdeg : ∀ j, j ∉ S → 0 < ∑ k, γ j k)
(hp : ∀ j, j ∉ S → p j = ∑ i, (γ j i / ∑ k, γ j k) * p i) :
∀ j, j ∉ S → (∑ i, γ i j * (p i - p j)) = 0 := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.