Proof of Theorem 1, p. 22 — ‖Δ‖_∞ ≤ 1 − d
ProvedDirectedOpinion.Typical.delta_norm_lecontractionopinion-dynamicsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a vertex-weighted directed graph whose weights lie in and sum to at every vertex with , where , and . Let be the operator (10), . If for every vertex , then for every vertex
Taking gives : the operator is a contraction of , which drives both the stationarity of Theorem 1 and the error propagation in Theorem 2.
Formalization Note The page writes ; the absolute value is meant. The bound is stated for every bound on instead of through an operator norm on .
Preamble
import Mathlib import Definitions.Def_DirectedOpinion_Typical_Model
Formal statement
namespace DirectedOpinion.Typical
/-- Proof of Theorem 1, p. 22: `|Δf(i)| ≤ Σ_r c(i, r)‖f‖_∞ + (1 − c − d)‖f‖_∞ ≤ (1 − d)‖f‖_∞` for
every vertex `i`, i.e. `‖Δ‖_∞ ≤ 1 − d`, stated for any bound `M` on `|f|`. -/
theorem delta_norm_le {V : Type*} (G : WDigraph V) (c d : ℝ) (hc0 : 0 ≤ c) (hc1 : c < 1)
(hd0 : 0 < d) (hd1 : d ≤ 1) (hcd : c + d ≤ 1) (hG : G.Valid c) (f : V → ℝ) (M : ℝ)
(hf : ∀ v, |f v| ≤ M) (i : V) :
|Δ G c d f i| ≤ (1 - d) * M := by sorry
end DirectedOpinion.Typical
Source
Fraiman, Lin and Olvera-Cravioto, Opinion dynamics on directed complex networks, arXiv:2209.00969v2, p. 22, proof of Theorem 1, display after the definition of ‖Δ‖_∞
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.