Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.11.2 — asymptotic growth rates of a monotone–homogeneous recurrence

Proved
PalmQueueing.Recurrence.growth_rates

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

couplingqueueingstationary-processstochastic-recurrencesubadditive-ergodic

Theorem 2.11.2. For all monotone and homogeneous stochastic recurrences such that for all nnn, Xn[0]X^{[0]}_nXn[0]​ is integrable and E[Xn[0]]>−CnE[X^{[0]}_n] > -CnE[Xn[0]​]>−Cn for some positive CCC, there exist constants γ‾,γ‾∈R\overline{\gamma}, \underline{\gamma} \in \mathbb{R}γ​,γ​∈R such that for all Y∈RKY \in \mathbb{R}^KY∈RK with E0[∥Y∥∞]<∞E^0[\|Y\|_\infty] < \inftyE0[∥Y∥∞​]<∞,

lim⁡nmax⁡i(Xn[Y])in=γ‾  P0-a.s.,lim⁡nE0[max⁡i(Xn[Y])i]n=γ‾,(2.11.6)\lim_n \frac{\max_i (X^{[Y]}_n)^i}{n} = \overline{\gamma}\ \ P^0\text{-a.s.}, \qquad \lim_n \frac{E^0[\max_i (X^{[Y]}_n)^i]}{n} = \overline{\gamma} , \tag{2.11.6}nlim​nmaxi​(Xn[Y]​)i​=γ​  P0-a.s.,nlim​nE0[maxi​(Xn[Y]​)i]​=γ​,(2.11.6) lim⁡nmin⁡i(Xn[Y])in=γ‾  P0-a.s.,lim⁡nE0[min⁡i(Xn[Y])i]n=γ‾.(2.11.7)\lim_n \frac{\min_i (X^{[Y]}_n)^i}{n} = \underline{\gamma}\ \ P^0\text{-a.s.}, \qquad \lim_n \frac{E^0[\min_i (X^{[Y]}_n)^i]}{n} = \underline{\gamma} . \tag{2.11.7}nlim​nmini​(Xn[Y]​)i​=γ​  P0-a.s.,nlim​nE0[mini​(Xn[Y]​)i]​=γ​.(2.11.7)

Four limits, not two. Each of (2.11.6) and (2.11.7) asserts both an almost-sure limit and the corresponding limit of expectations, and both constants are named. Stating only the maximum, or only the almost-sure halves, would be a strictly weaker theorem; the L1L^1L1 halves are what the saturation rule of §2.11.4 goes on to use.

The hypothesis E[Xn[0]]>−CnE[X^{[0]}_n] > -CnE[Xn[0]​]>−Cn is a one-sided linear lower bound, not an integrability condition — integrability is assumed separately — and it is what rules out the growth rate being −∞-\infty−∞.

The proof, for Y=0Y = 0Y=0, is Property 2.11.2 and Kingman's sub-additive ergodic theorem (Theorem 1.6.2 of Chapter 1). For any other finite initial condition YYY, Exercise 2.11.3 gives lim⁡nXn[Y]/n=lim⁡nXn[0]/n\lim_n X^{[Y]}_n/n = \lim_n X^{[0]}_n/nlimn​Xn[Y]​/n=limn​Xn[0]​/n P0P^0P0-a.s., and the L1L^1L1 limit follows in the same way.

Formalization Note. YYY ranges over RK\mathbb{R}^KRK-valued random variables with E0[∥Y∥∞]<∞E^0[\|Y\|_\infty] < \inftyE0[∥Y∥∞​]<∞ (Integrable Y, the norm on Fin K → ℝ being the sup norm); the driving variables are measurable and hhh is measurable in ξ\xiξ. max⁡i\max_imaxi​ and min⁡i\min_imini​ are the finite ⨆/⨅ over Fin K.

Example 2.11.3 applies it to the multiserver queue of §2.2.3: the limit lim⁡nmax⁡iXni/n=γ‾\lim_n \max_i X^i_n/n = \overline{\gamma}limn​maxi​Xni​/n=γ​ exists and is positive and finite whether or not the stability condition E0[σ]<sE0[τ]E^0[\sigma] < sE^0[\tau]E0[σ]<sE0[τ] holds, and since max⁡iXni=Tn+Wns\max_i X^i_n = T_n + W^s_nmaxi​Xni​=Tn​+Wns​, lim⁡nWns/n=γ‾−λ−1\lim_n W^s_n/n = \overline{\gamma} - \lambda^{-1}limn​Wns​/n=γ​−λ−1 P0P^0P0-a.s.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Recurrence_MonotoneHomogeneous
Formal statement
/-!
# Theorem 2.11.2: asymptotic growth rates of a monotone-homogeneous recurrence (§2.11.2, p.158)
-/

namespace PalmQueueing.Recurrence

open MeasureTheory Filter Topology

variable {Ω : Type*} [MeasurableSpace Ω]

/-- **Theorem 2.11.2** (p.158). For all monotone and homogeneous stochastic recurrences such that
for all `n`, `X_n^{[0]}` is integrable and `E[X_n^{[0]}] > −Cn` for some positive `C`, there exist
constants `γ̄, γ_ ∈ ℝ` such that for all `Y ∈ ℝ^K` with `E⁰[‖Y‖_∞] < ∞`,

`(2.11.6)  lim_n max_i (X_n^{[Y]})^i / n = γ̄  P⁰-a.s.,   lim_n E⁰[max_i (X_n^{[Y]})^i] / n = γ̄`,

`(2.11.7)  lim_n min_i (X_n^{[Y]})^i / n = γ_  P⁰-a.s.,  lim_n E⁰[min_i (X_n^{[Y]})^i] / n = γ_`.

**Four limits, not two.** Each of (2.11.6) and (2.11.7) asserts both an almost-sure limit and the
corresponding limit of expectations, and both constants are named. Stating only the maximum, or
only the a.s. halves, would be a strictly weaker theorem; the `L¹` halves are what the saturation
rule of §2.11.4 later uses.

The hypothesis `E[X_n^{[0]}] > −Cn` is a **one-sided linear lower bound**, not an integrability
condition: integrability is assumed separately. It is what rules out the growth rate being `−∞`.

`Y` ranges over `ℝ^K`-valued **random variables** with `E⁰[‖Y‖_∞] < ∞`, i.e. `Integrable Y P⁰`
(the norm on `Fin K → ℝ` is the sup norm); `{ξ_n}` are random variables and `h` is measurable in
`ξ`, as the section's setting requires.

The proof is Kingman's sub-additive ergodic theorem for `Y = 0`, plus the fact that the limit does
not depend on the finite initial condition. -/
theorem growth_rates {K : ℕ} {F : Type*} [MeasurableSpace F] (P0 : Measure Ω) [IsProbabilityMeasure P0]
    (θ : Ω ≃ᵐ Ω) (herg : Ergodic θ P0)
    (h : (Fin K → ℝ) → F → Fin K → ℝ) (hMH : IsMHRecurrence h)
    (hh : ∀ x : Fin K → ℝ, Measurable (h x))
    (xi : ℕ → Ω → F) (xi0 : Ω → F) (hxi0 : Measurable xi0)
    (hxi : ∀ (n : ℕ) (ω : Ω), xi n ω = xi0 ((θ : Ω → Ω)^[n] ω))
    (hint : ∀ n : ℕ, ∀ i : Fin K,
      Integrable (fun ω => mhIterate h xi (fun _ => (0 : Fin K → ℝ)) n ω i) P0)
    (Cst : ℝ) (hCst : 0 < Cst)
    (hlb : ∀ n : ℕ, ∀ i : Fin K,
      -(Cst * n) < ∫ ω, mhIterate h xi (fun _ => (0 : Fin K → ℝ)) n ω i ∂P0) :
    ∃ gbar glow : ℝ, ∀ Y : Ω → Fin K → ℝ, Integrable Y P0 →
      ((∀ᵐ ω ∂P0, Tendsto
          (fun n : ℕ => (⨆ i : Fin K, mhIterate h xi Y n ω i) / (n : ℝ)) atTop (𝓝 gbar)) ∧
       Tendsto
          (fun n : ℕ => (∫ ω, (⨆ i : Fin K, mhIterate h xi Y n ω i) ∂P0) / (n : ℝ))
          atTop (𝓝 gbar)) ∧
      ((∀ᵐ ω ∂P0, Tendsto
          (fun n : ℕ => (⨅ i : Fin K, mhIterate h xi Y n ω i) / (n : ℝ)) atTop (𝓝 glow)) ∧
       Tendsto
          (fun n : ℕ => (∫ ω, (⨅ i : Fin K, mhIterate h xi Y n ω i) ∂P0) / (n : ℝ))
          atTop (𝓝 glow)) := by sorry

end PalmQueueing.Recurrence
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 158, Theorem 2.11.2
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