Strong law of large numbers for positive Harris chains (Meyn–Tweedie Thm 17.0.1), from every initial state
OpenRiskSensMDP.AverageCost.harris_sllnLet be a standard Borel space and let be a Markov kernel on . Suppose the chain is positive Harris recurrent: it is Harris recurrent with respect to some nonzero -finite measure and admits an invariant probability measure (). Let be measurable with . Then for every starting state , the Markov chain with kernel and satisfies
This is the strong law of large numbers for positive Harris chains (Meyn & Tweedie, Markov Chains and Stochastic Stability, 2nd ed. 2009, Theorem 17.0.1 (i)). Bäuerle & Rieder invoke it in the proof of Theorem 5.1 to show that the average cost of a positive Harris recurrent stationary policy converges almost surely to .
Formalization Note is chainLaw P x, the Ionescu–Tulcea law of the chain on the path space . Meyn–Tweedie sum ; summing gives the same limit. Standard Borel is assumed in place of Meyn–Tweedie's standing countable-generation hypothesis; the statement holds for any invariant probability , which for a Harris recurrent chain is unique.
import Mathlib import Definitions.Def_RiskSensMDP_AverageCost_HarrisRecurrence open MeasureTheory ProbabilityTheory Filter Finset
namespace RiskSensMDP.AverageCost
/-- Law of large numbers for positive Harris chains (Meyn & Tweedie 2009, Theorem 17.0.1 (i)). -/
theorem harris_slln {E : Type*} [MeasurableSpace E] [StandardBorelSpace E]
(P : Kernel E E) [IsMarkovKernel P] (hP : IsPositiveHarrisRecurrent P)
(μ : Measure E) [IsProbabilityMeasure μ] (hμ : Kernel.Invariant P μ)
(g : E → ℝ) (hg : Measurable g) (hgi : Integrable g μ) (x : E) :
∀ᵐ ω ∂(chainLaw P x),
Tendsto (fun n : ℕ => (1 / (n : ℝ)) * ∑ k ∈ Finset.range n, g (ω k)) atTop
(nhds (∫ y, g y ∂μ)) := by sorry
end RiskSensMDP.AverageCost