graph_idle_measure_eq_mix
For α < 1 and any β, μ_x^β = λ μ_x^α + (1 − λ) δ_x with λ = (1 − β)/(1 − α).
Statement
theorem graph_idle_measure_eq_mix {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x : V) (α β : ℝ) (hα : α < 1) : graph_idle_measure G β x = fun v => (1 - β) / (1 - α) * graph_idle_measure G α x v + (1 - (1 - β) / (1 - α)) * (if v = x then 1 else 0)
- Source
- Helper for graph_lly_curvature_le_two_div_dist (OP-164, arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature)).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_idle_measureThe lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
- Used by 1
- graph_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
The proof, explained
The theorem expresses the lazy random walk measure μ_x^β as an affine mixture of μ_x^α and the point mass δ_x with weight λ = (1 - β) / (1 - α). By function extensionality, the proof checks equality at each vertex v by case analysis. At v = x, the equation reduces to the linear identity β = λ α + (1 - λ), which holds because 1 - α ≠ 0; at all other vertices, δ_x(v) vanishes and the idle measure scales proportionately by λ on neighbors and vanishes on non-neighbors.
1 - α ≠ 0
Because α < 1, linear arithmetic (linarith) proves that 1 - α > 0, so the denominator 1 - α is nonzero.
have hne : (1 - α) ≠ 0 := by linarith
It suffices to verify the equality pointwise for any vertex v ∈ V under the definition of graph_idle_measure
By function extensionality (funext), two measures are equal if they agree at every vertex v. Unfolding the definition of graph_idle_measure expresses each measure explicitly as a piecewise function depending on whether v = x, v is adjacent to x, or neither.
funext v unfold graph_idle_measure
The identity holds when v = x
When v = x, the if conditions evaluate to true (using if_true), reducing the Dirac mass to 1, μ_x^β(x) to β, and μ_x^α(x) to α. The goal becomes the scalar identity β = ((1 - β) / (1 - α)) * α + (1 - (1 - β) / (1 - α)). Clearing denominators via field_simp (using 1 - α ≠ 0) and simplifying with ring verifies this identity.
uses
if_trueby_cases hvx : v = x · simp only [hvx, if_true] field_simp ring
When v ≠ x, the Dirac mass vanishes and the identity reduces to μ_x^β(v) = ((1 - β) / (1 - α)) * μ_x^α(v)
When v ≠ x, the indicator if v = x then 1 else 0 simplifies to 0 by if_false. Multiplying by 0 yields 0 (mul_zero), and adding 0 is an identity (add_zero), eliminating the Dirac term completely.
uses
if_false,mul_zero,add_zero· simp only [hvx, if_false, mul_zero, add_zero]When v ≠ x and v is adjacent to x, the identity holds
When G.Adj x v holds, the adjacency branches evaluate to true (if_true), so μ_x^β(v) = (1 - β) / deg(x) and μ_x^α(v) = (1 - α) / deg(x). If deg(x) = 0, both sides evaluate to 0 in Lean's real division. Otherwise, field_simp cancels 1 - α ≠ 0 to show (1 - β) / deg(x) = ((1 - β) / (1 - α)) * ((1 - α) / deg(x)).
uses
if_trueby_cases hadj : G.Adj x v · simp only [hadj, if_true] by_cases hD : (G.degree x : ℝ) = 0 · simp [hD] · field_simp
When v ≠ x and v is not adjacent to x, the identity holds
Since v ≠ x and x is not adjacent to v, both graph_idle_measure G β x v and graph_idle_measure G α x v are defined to be 0, making both sides identically 0.
· simp [hadj]
if_true- An `if` conditional whose test is true evaluates to its `then` branch.
if_false- An `if` conditional whose test is false evaluates to its `else` branch.
mul_zero- Multiplying any element by zero yields zero.
add_zero- Adding zero to any element leaves it unchanged.
- In the subcase where x has degree 0, the proof relies on Lean's convention that division by zero in ℝ evaluates to 0. In simple graphs without self-loops, an adjacent vertex implies non-zero degree, but handling the degree-zero case algebraically avoids having to construct this graph-theoretic contradiction.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem graph_idle_measure_eq_mix {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x : V) (α β : ℝ) (hα : α < 1) : graph_idle_measure G β x = fun v => (1 - β) / (1 - α) * graph_idle_measure G α x v + (1 - (1 - β) / (1 - α)) * (if v = x then 1 else 0) := by have hne : (1 - α) ≠ 0 := by linarith funext v unfold graph_idle_measure by_cases hvx : v = x · simp only [hvx, if_true] field_simp ring · simp only [hvx, if_false, mul_zero, add_zero] by_cases hadj : G.Adj x v · simp only [hadj, if_true] by_cases hD : (G.degree x : ℝ) = 0 · simp [hD] · field_simp · simp [hadj]