Proposition 2 — supermartingale convergence theorem: , ⇒ , converges
ProvedIncProx.Randomized.proposition2Let be a probability space with a filtration , and let , , be real random variables such that:
- , , are nonnegative and -measurable;
- for each , almost surely,
- with probability 1, .
Then, with probability 1, , and the sequence converges to a nonnegative (finite) random variable .
This is the special case of the Robbins–Siegmund theorem that the paper cites from the literature and uses in the analysis of the randomized methods: applied with it turns the conditional descent inequality (58) into the almost sure statement (59).
Formalization Note The paper's "sets of random variables " are read as the -algebras they generate, i.e. a filtration, and "functions of the random variables in " as adaptedness. Integrability of each is an added hypothesis: Lean's conditional expectation of a non-integrable function is , so without it condition 2 would not express the paper's inequality. In the application is integrable. Nonnegativity is required pointwise.
import Mathlib
namespace IncProx.Randomized
open Filter Topology MeasureTheory
/-- Proposition 2 (Supermartingale Convergence Theorem, p. 8). `Y`, `Z`, `W` are nonnegative and
adapted to the filtration `𝓕` (F_k ⊂ F_{k+1}); `E{Y_{k+1} | F_k} ≤ Y_k − Z_k + W_k`;
`Σ W_k < ∞` with probability 1. Then with probability 1 `Σ Z_k < ∞` and `Y_k` converges to a
nonnegative random variable. Integrability of each `Y_k` is an added hypothesis (Lean's conditional
expectation of a non-integrable function is `0`). -/
theorem proposition2 {Ω : Type*} {m0 : MeasurableSpace Ω} (μ : Measure Ω) [IsProbabilityMeasure μ]
(𝓕 : Filtration ℕ m0) (Y Z W : ℕ → Ω → ℝ)
(hYad : Adapted 𝓕 Y) (hZad : Adapted 𝓕 Z) (hWad : Adapted 𝓕 W)
(hY0 : ∀ k s, 0 ≤ Y k s) (hZ0 : ∀ k s, 0 ≤ Z k s) (hW0 : ∀ k s, 0 ≤ W k s)
(hYint : ∀ k, Integrable (Y k) μ)
(h2 : ∀ k, μ[Y (k + 1) | 𝓕 k] ≤ᵐ[μ] fun s => Y k s - Z k s + W k s)
(h3 : ∀ᵐ s ∂μ, Summable fun k => W k s) :
(∀ᵐ s ∂μ, Summable fun k => Z k s) ∧
∃ Yinf : Ω → ℝ, Measurable Yinf ∧
∀ᵐ s ∂μ, 0 ≤ Yinf s ∧ Tendsto (fun k => Y k s) atTop (𝓝 (Yinf s)) := by sorry
end IncProx.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.