AFTD Auto-Formalizing Theoretical Domains

graph_idle_measure_eq_mix

theoremverified

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

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. 1 - α ≠ 0

    Because α < 1, linear arithmetic (linarith) proves that 1 - α > 0, so the denominator 1 - α is nonzero.

    line 5

      have hne : (1 - α) ≠ 0 := by linarith
  2. 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.

    lines 6–7

      funext v
      unfold graph_idle_measure
  3. 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.

    lines 8–11

    uses if_true

      by_cases hvx : v = x
      · simp only [hvx, if_true]
        field_simp
        ring
  4. 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.

    line 12

    uses if_false, mul_zero, add_zero

      · simp only [hvx, if_false, mul_zero, add_zero]
  5. 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)).

    lines 13–17

    uses if_true

        by_cases hadj : G.Adj x v
        · simp only [hadj, if_true]
          by_cases hD : (G.degree x : ℝ) = 0
          · simp [hD]
          · field_simp
  6. 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.

    line 18

        · 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.

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

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]
See it in the graphDiscuss this resultChallenge it