finite_variance_recurrence_additive
If partition functions and the first two unnormalized moments satisfy the independent-component recurrences with nonzero denominators, the total variance is the sum of the component variances.
Statement
theorem finite_variance_recurrence_additive {C : Type*} [DecidableEq C] (Z A B : Finset C → ℝ) (s m₁ m₂ : C → ℝ) (hZ : ∀ T, Z T ≠ 0) (hs : ∀ c, 1 + s c ≠ 0) (hbase : A ∅ = 0 ∧ B ∅ = 0) (hZstep : ∀ c T, c ∉ T → Z (insert c T) = (1+s c) * Z T) (hAstep : ∀ c T, c ∉ T → A (insert c T) = (1+s c) * A T + m₁ c * Z T) (hBstep : ∀ c T, c ∉ T → B (insert c T) = (1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T) (T : Finset C) : B T / Z T - (A T / Z T)^2 = ∑ c ∈ T, (m₂ c / (1+s c) - (m₁ c / (1+s c))^2)
- Source
- Component decomposition for op_1355_clique_components_variance_ge_bound.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_1355_clique_components_variance_ge_boundFor any finite simple graph G on a finite type V with decidable equality whose connected components are all cliques, and for all positive…
The proof, explained
The theorem is proved by induction on the finite set T using Finset.induction_on. The base case T = ∅ is straightforward because the unnormalized moments vanish on the empty set. For the inductive step, the recurrence relations express the moments and partition function on T ∪ {c} in terms of those on T. A purely algebraic identity (hstep) shows that the variance of the combined system decomposes into the variance of T plus the variance contribution of the new component c, which completes the induction.
The variance identity holds for the empty set T = ∅.
We induct on the finite set T using Finset.induction_on. In the base case T = ∅, the base hypothesis hbase gives A(∅) = 0 and B(∅) = 0. Substituting these values into the left-hand side yields 0 / Z(∅) - (0 / Z(∅))² = 0. The right-hand side is an empty sum, which is also 0.
uses
Finset.induction_oninduction T using Finset.induction_on with | empty => simp [hbase.1, hbase.2]
In the inductive step, the recurrence relations and sum splitting express both sides for T ∪ {c} in terms of T and c.
For the inductive step, we assume the identity holds for T (the induction hypothesis ih) and consider adding an element c ∉ T. Applying the recurrence relations hZstep, hAstep, and hBstep rewrites Z(T ∪ {c}), A(T ∪ {c}), and B(T ∪ {c}) on the left-hand side. On the right-hand side, Finset.sum_insert splits the summation over T ∪ {c} into the summand at c plus the sum over T.
uses
Finset.sum_insert| @insert c T hc ih => rw [hZstep c T hc, hAstep c T hc, hBstep c T hc, Finset.sum_insert hc]The variance of T ∪ {c} decomposes into the variance of T plus the variance contribution of c.
We prove the algebraic transition identity (hstep). Since 1 + s(c) ≠ 0 by hypothesis hs and Z(T) ≠ 0 by hZ, their product (1 + s(c)) * Z(T) is nonzero by mul_ne_zero. Clearing denominators across all rational terms with field_simp reduces the identity to an equality between two polynomials, which ring verifies.
uses
mul_ne_zerohave hstep : ((1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T) / ((1+s c) * Z T) - (((1+s c) * A T + m₁ c * Z T) / ((1+s c) * Z T))^2 = (B T / Z T - (A T / Z T)^2) + (m₂ c / (1+s c) - (m₁ c / (1+s c))^2) := by have h1 : (1 + s c) * Z T ≠ 0 := mul_ne_zero (hs c) (hZ T) field_simp [hZ T, hs c] ring
The inductive step is completed.
Rewriting the goal using the transition identity (hstep) and the induction hypothesis (ih) replaces the variance at T by the sum over T. Both sides now consist of the sum over T plus the term for c, and the ring tactic verifies that the two sides are equal by commutativity of addition.
rw [hstep, ih] ring
Finset.induction_on- To prove a property for all finite sets, it suffices to prove it for the empty set and show that if it holds for a finite set s, it also holds for s with any new element inserted.
Finset.sum_insert- The sum of a function over a finite set with a new element inserted equals the value at that element plus the sum over the original set.
mul_ne_zero- In a type without zero divisors (such as ℝ), the product of two nonzero elements is nonzero.
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.
open scoped Classicaltheorem finite_variance_recurrence_additive {C : Type*} [DecidableEq C] (Z A B : Finset C → ℝ) (s m₁ m₂ : C → ℝ) (hZ : ∀ T, Z T ≠ 0) (hs : ∀ c, 1 + s c ≠ 0) (hbase : A ∅ = 0 ∧ B ∅ = 0) (hZstep : ∀ c T, c ∉ T → Z (insert c T) = (1+s c) * Z T) (hAstep : ∀ c T, c ∉ T → A (insert c T) = (1+s c) * A T + m₁ c * Z T) (hBstep : ∀ c T, c ∉ T → B (insert c T) = (1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T) (T : Finset C) : B T / Z T - (A T / Z T)^2 = ∑ c ∈ T, (m₂ c / (1+s c) - (m₁ c / (1+s c))^2) := by induction T using Finset.induction_on with | empty => simp [hbase.1, hbase.2] | @insert c T hc ih => rw [hZstep c T hc, hAstep c T hc, hBstep c T hc, Finset.sum_insert hc] have hstep : ((1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T) / ((1+s c) * Z T) - (((1+s c) * A T + m₁ c * Z T) / ((1+s c) * Z T))^2 = (B T / Z T - (A T / Z T)^2) + (m₂ c / (1+s c) - (m₁ c / (1+s c))^2) := by have h1 : (1 + s c) * Z T ≠ 0 := mul_ne_zero (hs c) (hZ T) field_simp [hZ T, hs c] ring rw [hstep, ih] ring