Proposition 3.4, p. 12 — a nonnegative summable sequence tends to 0, has averages O(1/k) and running minima o(1/k)
ProvedExtraConsensus.Sublinear.proposition_3_4convergence-ratelittle-op2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1summable-sequence
Let be a real sequence with for all and . Then
- ;
- ;
- as .
This elementary fact converts the summability of the progress and residual sequences into the ergodic and running-best rates of Theorem 3.5.
Formalization Note Summability is over all , which is equivalent to the page's . The running minimum ranges over , the same indices as the sums; its value at is irrelevant.
Preamble
import Mathlib import Definitions.Def_ExtraConsensus_Sublinear_Model
Formal statement
namespace ExtraConsensus.Sublinear
open Matrix Filter Topology Asymptotics
/-- Proposition 3.4, p. 12. If `aₖ ≥ 0` for all `k` and `Σₜ aₜ < ∞`, then (i) `aₖ → 0`;
(ii) `(1/k) Σ_{t=1}^{k} aₜ = O(1/k)`; (iii) `min_{1≤t≤k} aₜ = o(1/k)`. -/
theorem proposition_3_4 (a : ℕ → ℝ) (ha : ∀ k, 0 ≤ a k) (hsum : Summable a) :
Tendsto a atTop (𝓝 0) ∧
(fun k : ℕ => (1 / (k : ℝ)) * ∑ t ∈ Finset.Icc 1 k, a t) =O[atTop]
(fun k : ℕ => (1 : ℝ) / k) ∧
(fun k : ℕ => runMin a k) =o[atTop] (fun k : ℕ => (1 : ℝ) / k) := by sorry
end ExtraConsensus.Sublinear
Source
Shi, Ling, Wu & Yin, arXiv:1404.6264v4, Proposition 3.4, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.