Proof of Theorem 2.2, p. 5 — Λ_k[F^{|C*|+1}] ≤ 1 − (1 − α₁)α₂^{|C*|} < 1 for every unit row k ∈ S₂
ProvedSubSuperStoch.SubSpec.unit_rows_power_boundmatrix-powernonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1row-sumsub-stochastic-matrix
Let be an sub-stochastic matrix with and non-empty. Suppose that for each a non-zero element chain starting at some is given, and let
be the largest number of elements among these chains. With and as in Theorem 2.2, every satisfies
This is the step of the proof of Theorem 2.2 that passes from the bound at the end of each chain to a single power of common to all rows of sum one.
Formalization Note The chosen chain for has length len k (one chain per , as the hypothesis of Theorem 2.2 provides), and is C with IsGreatest {m | ∃ k, rowSum F k = 1 ∧ m = len k} C.
Preamble
import Mathlib import Definitions.Def_SubSuperStoch_SubSpec_Setting
Formal statement
namespace SubSuperStoch.SubSpec
theorem unit_rows_power_bound {n : ℕ} (F : Matrix (Fin n) (Fin n) ℝ) (hF : IsSubStochastic F)
(hS₁ : ∃ s, rowSum F s < 1) (hS₂ : ∃ s, rowSum F s = 1)
(len : Fin n → ℕ)
(hchain : ∀ k, rowSum F k = 1 → ∃ i, rowSum F i < 1 ∧
∃ c : ℕ → Fin n, c 0 = i ∧ c (len k) = k ∧ 1 ≤ len k ∧ IsChain F c (len k))
(α₁ : ℝ) (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 : ℕ) (hC : IsGreatest {m | ∃ k, rowSum F k = 1 ∧ m = len k} C) :
∀ k, rowSum F k = 1 →
rowSum (F ^ (C + 1)) k ≤ 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 Λ_k[F^{|C*|+1}] after "According to the definition of |C*|")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.