Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Kirchhoff's node law from the random-walk game

Proved
KellyStochasticNetworks.kirchhoff_from_random_walk

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

markov-chainoperations-researchstochastic-networks

Section 4.1 opens with a game. You perform a symmetric random walk on a graph with transition rates γjk=γkj\gamma_{jk} = \gamma_{kj}γjk​=γkj​ until you hit a set SSS of vertices, and you are then paid a reward depending on the vertex you hit. Let pjp_jpj​ be the expected reward starting from jjj. Conditioning on the first vertex the walk jumps to gives, for every j∉Sj \notin Sj∈/S,

pj=∑iγji∑kγjk pi.p_j = \sum_i \frac{\gamma_{ji}}{\sum_k \gamma_{jk}}\,p_i .pj​=i∑​∑k​γjk​γji​​pi​.

This is exactly Kirchhoff's node law. For every j∉Sj \notin Sj∈/S,

∑iγij (pi−pj)=0.\sum_i \gamma_{ij}\,(p_i - p_j) = 0 .i∑​γij​(pi​−pj​)=0.

Reading pip_ipi​ as the voltage at node iii and γij\gamma_{ij}γij​ as the conductance — the inverse resistance — of the edge ijijij, each term γij(pi−pj)\gamma_{ij}(p_i - p_j)γij​(pi​−pj​) is the current flowing into node jjj 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 γij=γji\gamma_{ij} = \gamma_{ji}γij​=γji​, 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 SSS 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.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
Formal statement
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 KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, p. 87 (PDF p. 95), section 4.1.1: 'By conditioning on the first vertex i to which the random walk jumps from j, we obtain the relations p_j = sum_i (gamma_{ji} / sum_k gamma_{jk}) p_i, for j in G \ S. We can rewrite this set of equations as follows: 0 = sum_i gamma_{ij} (p_i - p_j), j in G \ S, p_j = v_j, j in S. Interpreting p_i as the voltage at vertex (node) i, and gamma_{ij} as the conductance (inverse resistance) of the edge (ij), the first line is asserting that the sum of the currents through all the edges into a given node i is 0. These are Kirchhoff's equations for an electrical network G.' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me