Proof of Theorem 2.2, p. 5 — Λ_i[F^{|C*|+1}] ≤ 1 − (1 − α₁)α₂^{|C*|} < 1 for every row i ∈ S₁
ProvedSubSuperStoch.SubSpec.deficient_rows_power_boundmatrix-powernonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1row-sumsub-stochastic-matrix
Let be an sub-stochastic matrix, and let and (both sets non-empty). For every natural number (in the paper, ) and every row with ,
In the proof of Theorem 2.2 this is the bound for the rows of ; together with the bound for the rows of it controls every row of .
Formalization Note The page states this for ; the argument does not use the chains, so the statement is given for an arbitrary natural number , which contains the page's case.
Preamble
import Mathlib import Definitions.Def_SubSuperStoch_SubSpec_Setting
Formal statement
namespace SubSuperStoch.SubSpec
theorem deficient_rows_power_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} α₂)
(C : ℕ) :
∀ i, rowSum F i < 1 →
rowSum (F ^ (C + 1)) i ≤ 1 - (1 - α₁) * α₂ ^ C ∧ 1 - (1 - α₁) * α₂ ^ C < 1 := by sorry
end SubSuperStoch.SubSpec
Source
Shi, Zheng, Shao, Cheng, arXiv:2004.01867v2, p. 5, proof of Theorem 2.2 (display Λ_i[F^{|C*|+1}] after "In addition, for any i ∈ S₁")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.