(15) — the Cesàro limit P* of a substochastic P exists and PP* = P*P = P*P* = P*
ProvedVeinottSensitiveDP.Sensitive.display_15cesaro-limitmarkov-chainp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an substochastic matrix (nonnegative entries, row sums at most ). Then the Cesàro means of its powers converge,
and the limit satisfies
These identities are used throughout §3: they give , the nonsingularity of , and for .
Formalization Note is the published limitMatrix P; the convergence is stated explicitly. The paper adds that uniquely satisfies (15); this is not formalized, since the zero matrix also satisfies the three identities.
Preamble
import Mathlib import Definitions.Def_BlackwellDiscreteDP_NearOne_LimitMatrix import Definitions.Def_VeinottSensitiveDP_Sensitive_Matrix open Filter Topology Matrix BlackwellDiscreteDP.NearOne
Formal statement
namespace VeinottSensitiveDP.Sensitive
/-- (15): for an `S × S` substochastic matrix `P`, the Cesàro means `(N + 1)⁻¹ Σ_{i=0}^N P^i`
converge to a matrix `P*`, and `PP* = P*P = P*P* = P*`.
Veinott, Discrete Dynamic Programming with Sensitive Discount Optimality Criteria,
Ann. Math. Statist. 40(5):1635–1660 (1969), DOI 10.1214/aoms/1177697379, p. 1642, §3, (15).
**Formalization Note.** `P*` is the published `limitMatrix P` (a `limUnder`), and `cesaroMean P N`
is exactly `(N + 1)⁻¹ Σ_{i=0}^N P^i`; the first conjunct says the limit exists. The paper's
"P* uniquely satisfies (15)" is not formalized: the zero matrix also satisfies the three
equations, so the uniqueness cannot be stated literally. -/
theorem display_15 {St : Type} [Fintype St] [DecidableEq St] (P : Matrix St St ℝ)
(hP : IsSubstochastic P) :
Tendsto (cesaroMean P) atTop (𝓝 (limitMatrix P)) ∧
P * limitMatrix P = limitMatrix P ∧ limitMatrix P * P = limitMatrix P ∧
limitMatrix P * limitMatrix P = limitMatrix P := by sorry
end VeinottSensitiveDP.Sensitive
Source
Veinott, Discrete Dynamic Programming with Sensitive Discount Optimality Criteria, Ann. Math. Statist. 40(5):1635–1660 (1969), DOI 10.1214/aoms/1177697379, p. 1642, §3, (15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.