(21)–(22), p. 403 — Pr[|x_n − θ| ≤ A_n] = 1
ProvedRobbinsMonroSA.Conv.eq_22p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robbins-monrostochastic-approximation
Under (4) with constant , positive step sizes , and the process (7)–(8) started at , let
Then for every ,
The almost-sure bound (22) localises the iterates, so that only the behaviour of on matters at step .
Formalization Note Indices are 0-based: bigA x1 θ C α a n is the paper's , the bound for Lean's x n (the paper's ). Only the positivity half of (6) is assumed. The conclusion is "almost surely".
Preamble
import Mathlib import Definitions.Def_RobbinsMonroSA_Conv_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RobbinsMonroSA.Conv
/-- (21)–(22), p. 403. From (4) and (7), `Pr[|x_n - θ| ≤ A_n] = 1` for every `n`
(0-based: `bigA x1 θ C α a n` is the paper's `A_{n+1}`). -/
theorem eq_22 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(H : Kernel ℝ ℝ) [IsMarkovKernel H] (C : ℝ) (h4 : BoundedResponse H C) (α θ : ℝ)
(a : ℕ → ℝ) (x1 : ℝ) (x y : ℕ → Ω → ℝ) (hxy : IsRMProcess P H a α x1 x y)
(hpos : ∀ n, 0 < a n) :
∀ n, ∀ᵐ ω ∂P, |x n ω - θ| ≤ bigA x1 θ C α a n := by sorry
end RobbinsMonroSA.Conv
Source
Robbins and Monro, A stochastic approximation method, Ann. Math. Statist. 22 (1951), p. 403, (21)–(22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.