Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
SubSuperStoch.SubSpec.chain_rowSum_bound

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

matrix-powernonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1row-sumsub-stochastic-matrix

Let FFF be an n×nn\times nn×n sub-stochastic matrix. Let

α1=max⁡{Λs[F]∣Λs[F]<1},α2=min⁡{[F]ij>0∣i,j=1,…,n}\alpha_1=\max\{\Lambda_s[F]\mid \Lambda_s[F]<1\},\qquad \alpha_2=\min\{[F]_{ij}>0\mid i,j=1,\dots,n\}α1​=max{Λs​[F]∣Λs​[F]<1},α2​=min{[F]ij​>0∣i,j=1,…,n}

be the largest row sum below one and the smallest positive entry of FFF (both sets are assumed non-empty). Let iii be a row with Λi[F]<1\Lambda_i[F]<1Λi​[F]<1, and let [F]kir,…,[F]i2i1,[F]i1i[F]_{k i_r},\dots,[F]_{i_2 i_1},[F]_{i_1 i}[F]kir​​,…,[F]i2​i1​​,[F]i1​i​ be a non-zero element chain from iii to kkk with L=r+1≥1L=r+1\ge 1L=r+1≥1 elements. Then

Λk[FL+1]≤1−(1−α1)α2L<1.\Lambda_k[F^{L+1}]\le 1-(1-\alpha_1)\alpha_2^{L}<1 .Λk​[FL+1]≤1−(1−α1​)α2L​<1.

In the paper's indexing (L=r+1L=r+1L=r+1) this is Λk[Fr+2]≤1−(1−α1)α2r+1<1\Lambda_k[F^{r+2}]\le 1-(1-\alpha_1)\alpha_2^{r+1}<1Λk​[Fr+2]≤1−(1−α1​)α2r+1​<1; the cases L=1,2L=1,2L=1,2 are the displayed bounds Λi1[F2]≤1−(1−α1)α2\Lambda_{i_1}[F^2]\le 1-(1-\alpha_1)\alpha_2Λi1​​[F2]≤1−(1−α1​)α2​ and Λi2[F3]≤1−(1−α1)α22\Lambda_{i_2}[F^3]\le 1-(1-\alpha_1)\alpha_2^2Λi2​​[F3]≤1−(1−α1​)α22​.

This is the first step of the proof of Theorem 2.2: the deficit 1−Λi[F]1-\Lambda_i[F]1−Λi​[F] of a row of sum below one propagates along the chain, shrinking by at most a factor α2\alpha_2α2​ per entry.

Formalization Note The chain is c : ℕ → Fin n with c 0 = i, 1 ≤ L and IsChain F c L; its endpoint kkk 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
  • Endorsed by Shuze Chen · Oct 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me