Proof of Theorem 2.2, p. 5 — at the end of a chain of L non-zero entries, Λ_k[F^{L+1}] ≤ 1 − (1 − α₁)α₂^L < 1
ProvedSubSuperStoch.SubSpec.chain_rowSum_boundmatrix-powernonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1row-sumsub-stochastic-matrix
Let be an sub-stochastic matrix. Let
be the largest row sum below one and the smallest positive entry of (both sets are assumed non-empty). Let be a row with , and let be a non-zero element chain from to with elements. Then
In the paper's indexing () this is ; the cases are the displayed bounds and .
This is the first step of the proof of Theorem 2.2: the deficit of a row of sum below one propagates along the chain, shrinking by at most a factor per entry.
Formalization Note The chain is c : ℕ → Fin n with c 0 = i, 1 ≤ L and IsChain F c L; its endpoint is c L. The maxima and minimum are passed as values with IsGreatest/IsLeast hypotheses over exactly the printed sets.
Preamble
import Mathlib import Definitions.Def_SubSuperStoch_SubSpec_Setting
Formal statement
namespace SubSuperStoch.SubSpec
theorem chain_rowSum_bound {n : ℕ} (F : Matrix (Fin n) (Fin n) ℝ) (hF : IsSubStochastic F)
(α₁ : ℝ) (hα₁ : IsGreatest {x | ∃ s, rowSum F s < 1 ∧ x = rowSum F s} α₁)
(α₂ : ℝ) (hα₂ : IsLeast {x | ∃ i j, 0 < F i j ∧ x = F i j} α₂)
(i : Fin n) (hi : rowSum F i < 1)
(c : ℕ → Fin n) (L : ℕ) (hc0 : c 0 = i) (hL : 1 ≤ L) (hc : IsChain F c L) :
rowSum (F ^ (L + 1)) (c L) ≤ 1 - (1 - α₁) * α₂ ^ L ∧ 1 - (1 - α₁) * α₂ ^ L < 1 := by sorry
end SubSuperStoch.SubSpec
Source
Shi, Zheng, Shao, Cheng, arXiv:2004.01867v2, p. 5, proof of Theorem 2.2 (first block of displays, Λ_{i₁}[F²], Λ_{i₂}[F³], …, Λ_k[F^{r+2}])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.