Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Chapter XI, Theorem 3 (corrected) — xi(n)∼a yiλnx_i(n)\sim a\,y_i\lambda^nxi​(n)∼ayi​λn for the recurrence x(n+1)=max⁡qA(q)x(n)x(n+1)=\max_q A(q)x(n)x(n+1)=maxq​A(q)x(n)

Proved
BellmanDP.Markovian.discrete_growth_asymptotics

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

dynamic-programmingmarkov-decision-processp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1perron-frobenius

Assume the setting and conditions (10.3) of Theorem 2 (with N≥1N \ge 1N≥1), and assume in addition that the Perron root φ(q)\varphi(q)φ(q) attains its maximum over SSS at exactly one joint parameter q∗q^*q∗. Let c∈RNc \in \mathbb R^Nc∈RN with ci≥0c_i \ge 0ci​≥0 for all iii and c≠0c \ne 0c=0, and define

xi(0)=ci,xi(n+1)=max⁡q∑j=1Naij(q) xj(n),i=1,…,N, n≥0.x_i(0) = c_i, \qquad x_i(n+1) = \max_q \sum_{j=1}^N a_{ij}(q)\, x_j(n), \qquad i = 1,\dots,N,\ n \ge 0 .xi​(0)=ci​,xi​(n+1)=qmax​j=1∑N​aij​(q)xj​(n),i=1,…,N, n≥0.

Let λ>0\lambda > 0λ>0 and yyy with yi>0y_i > 0yi​>0 be the solution of the homogeneous system of Theorem 2. Then there is a constant a=a(c1,…,cN)>0a = a(c_1,\dots,c_N) > 0a=a(c1​,…,cN​)>0 with

xi(n)∼a yi λn(n→∞),x_i(n) \sim a\, y_i\, \lambda^n \qquad (n \to \infty),xi​(n)∼ayi​λn(n→∞),

that is, xi(n)/λn→a yix_i(n)/\lambda^n \to a\, y_ixi​(n)/λn→ayi​ for every iii.

The theorem describes the long-run growth of the optimally controlled discrete process: it grows geometrically at the maximal Perron root, in the direction of the positive eigenvector of Theorem 2.

Formalization Note The book prints "a unique qqq for which the maximum value of qqq is assumed"; a parameter has no maximum value, and the proof works with "q∗q^*q∗ \dots the value of qqq for which λ=φ(q∗)\lambda = \varphi(q^*)λ=φ(q∗)", so the hypothesis is read as uniqueness of the maximizer of φ\varphiφ (condition (10.3c)). The book takes ci≥0c_i \ge 0ci​≥0 and then "ci>0c_i > 0ci​>0, without loss of generality"; for c=0c = 0c=0 the sequence is identically zero and xi(n)∼ayiλnx_i(n) \sim a y_i \lambda^nxi​(n)∼ayi​λn with a>0a > 0a>0 fails, so c≠0c \ne 0c=0 is assumed. Asymptotic equivalence with a positive limit is stated as convergence of the ratio.

Preamble
import Mathlib
import Definitions.Def_BellmanDP_Markovian_Discrete
Formal statement
namespace BellmanDP.Markovian

open Filter Topology

/-- Bellman, *Dynamic Programming*, Ch. XI, Theorem 3, p. 330 (corrected: the printed "unique
q for which the maximum value of q is assumed" is read as the maximum of the Perron root `φ(q)`,
as in (10.3c) and the proof). Under (10.3a)–(c), if `φ` has a unique maximizer on `S` and the
initial vector `c ≥ 0` is not zero, then for the positive solution `(λ, y)` of (10.2) the sequence
(10.1) satisfies `x_i(n) ~ a y_i λⁿ` with a constant `a = a(c) > 0`, i.e.
`x_i(n) / λⁿ → a y_i` for every `i`. -/
theorem discrete_growth_asymptotics {N : ℕ} (hN : 0 < N) {Q : Fin N → Type*}
    (a : (i : Fin N) → Q i → Fin N → ℝ) (S : (i : Fin N) → Set (Q i)) (m : ℝ)
    (h : MarkovHyp a S m)
    (huniq : ∃! qs, qs ∈ Set.pi Set.univ S ∧ ∀ q ∈ Set.pi Set.univ S,
      perronRoot (matOf a q) ≤ perronRoot (matOf a qs))
    (c : Fin N → ℝ) (hc : ∀ i, 0 ≤ c i) (hc0 : c ≠ 0)
    (lam : ℝ) (y : Fin N → ℝ) (hlam : 0 < lam) (hy : ∀ i, 0 < y i)
    (hey : IsMaxEigenpair a S lam y) :
    ∃ α : ℝ, 0 < α ∧ ∀ i : Fin N,
      Tendsto (fun n : ℕ => maxIter a S c n i / lam ^ n) atTop (𝓝 (α * y i)) := by sorry

end BellmanDP.Markovian
Source
Bellman, Dynamic Programming, Princeton University Press (1957; Princeton Landmarks ed. 2010), DOI 10.2307/j.ctv1nxcw0f, Chapter XI, Theorem 3, p. 330 (with Eqs. (10.1), (10.3), pp. 328-329; proof pp. 331-332)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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