Proposition 3.1, p. 11 — if Qv ≤ v − f for a non-negative kernel Q, f ≥ 0 and finite v ≥ 0, then Σₙ Qⁿf ≤ v
ProvedLyapDiffMC.RandomHorizon.proposition_3_1comparison-theoremlyapunov-functionmarkov-kernelp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-kernel
Let be a non-negative kernel on a measurable space , and let be measurable. Suppose is a finite-valued measurable function with
that is, for every . Then
where and .
This comparison bound drives the proof of Theorem 3.1. Applied to (3.11) it gives . Applied to (3.12) it bounds the -integrals that control the derivative.
Formalization Note The space is an arbitrary measurable space , and the kernel need not be finite. and are -valued with finite everywhere, and (3.15) is written as .
Differences from the source:
- encoding: Q = (Q(x, dy) : x, y ∈ C) a non-negative kernel, f : C → ℝ₊, v : C → ℝ₊ finite-valued → Q : Kernel S S on an arbitrary measurable space S (playing C), f v : S → ℝ≥0∞ measurable, v x ≠ ⊤; reason: C is itself a measurable space; (3.15) with v finite forces f ≤ v < ∞, so allowing f to take the value ∞ adds no instance; measurability is needed for Qv and Qⁿf to be defined
- encoding: Qv ≤ v − f (3.15) → ∫ v dQ(x, ·) + f(x) ≤ v(x) for all x, in ℝ≥0∞; reason: equivalent because v is finite
- encoding: Q⁰ = I, Qⁿ = QQⁿ⁻¹ → Qpow Q 0 = Kernel.id, Qpow Q (n+1) = Q ∘ₖ Qpow Q n; reason: the same kernel (composition is associative); Σₙ Qⁿf as a sum in ℝ≥0∞
Preamble
import Mathlib import Definitions.Def_LyapDiffMC_RandomHorizon_Model open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace LyapDiffMC.RandomHorizon
/-- Proposition 3.1 (p. 11). For a non-negative kernel `Q`, a non-negative `f` and a
finite-valued non-negative `v` with `Qv ≤ v - f` (3.15), `Σₙ Qⁿ f ≤ v` (3.16). The measurable
space `S` plays the role of the paper's `C`; (3.15) is written additively, `Qv + f ≤ v`, which is
equivalent because `v` is finite. -/
theorem proposition_3_1 {S : Type*} [MeasurableSpace S] (Q : Kernel S S)
(f v : S → ℝ≥0∞) (hf : Measurable f) (hv : Measurable v) (hv_fin : ∀ x, v x ≠ ⊤)
(h315 : ∀ x, ∫⁻ y, v y ∂(Q x) + f x ≤ v x) :
∀ x, ∑' n, ∫⁻ y, f y ∂(Qpow Q n x) ≤ v x := by sorry
end LyapDiffMC.RandomHorizon
Source
Rhee, Glynn, Lyapunov Conditions for Differentiability of Markov Chain Expectations, arXiv:1707.03870v1, p. 11, Proposition 3.1, (3.15)–(3.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.