Theorem 2.11.2 — asymptotic growth rates of a monotone–homogeneous recurrence
ProvedPalmQueueing.Recurrence.growth_ratesTheorem 2.11.2. For all monotone and homogeneous stochastic recurrences such that for all , is integrable and for some positive , there exist constants such that for all with ,
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 halves are what the saturation rule of §2.11.4 goes on to use.
The hypothesis 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 .
The proof, for , 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 , Exercise 2.11.3 gives -a.s., and the limit follows in the same way.
Formalization Note. ranges over -valued random variables with
(Integrable Y, the norm on Fin K → ℝ being the sup norm); the
driving variables are measurable and is measurable in . and are the
finite ⨆/⨅ over Fin K.
Example 2.11.3 applies it to the multiserver queue of §2.2.3: the limit exists and is positive and finite whether or not the stability condition holds, and since , -a.s.
import Mathlib import Definitions.Def_PalmQueueing_Recurrence_MonotoneHomogeneous
/-!
# 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.