Theorem 3, p. 9 — small gain theorem: a cycle of arrows with γ₁⋯γ_m < 1 bounds ‖s¹‖^λ_F
ProvedDIGing.Undir.theorem_3ergodic-normlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1small-gain
Let , let , and let be sequences of matrices. Suppose that for every positive integer and every there is an arrow , that is,
where the gains are nonnegative and . Then
This is the small gain theorem in the ergodic norm, the organizing principle of the paper: the convergence proof establishes the four arrows of a cycle and then reads off a bound on , i.e. an R-linear rate.
Formalization Note. Indices are -based: is s ⟨0, hm⟩ and the successor is finRotate m i. The bound is . The supremum, which may be infinite in general, is stated pointwise: for every .
Preamble
import Mathlib import Definitions.Def_DIGing_Undir_Common
Formal statement
namespace DIGing.Undir
theorem theorem_3 {n p m : ℕ} (hm : 0 < m) (s : Fin m → ℕ → Stack n p) (lam : ℝ)
(hlam0 : 0 < lam) (hlam1 : lam < 1) (γ ω : Fin m → ℝ) (hγ : ∀ i, 0 ≤ γ i)
(hprod : ∏ i, γ i < 1)
(harrow : ∀ K : ℕ, 0 < K → ∀ i : Fin m,
ergK lam K (fun k => frob (s (finRotate m i) k)) ≤ γ i * ergK lam K (fun k => frob (s i k)) + ω i) :
∀ k : ℕ, frob (s ⟨0, hm⟩ k) / lam ^ k ≤
(1 - ∏ i, γ i)⁻¹ * ∑ j, ω j * ∏ l ∈ Finset.univ.filter (fun l => j < l), γ l := by sorry
end DIGing.Undir
Source
Nedić, Olshevsky & Shi, arXiv:1607.03218v3, Theorem 3, display (7), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.