Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Strong law of large numbers for positive Harris chains (Meyn–Tweedie Thm 17.0.1), from every initial state

Open
RiskSensMDP.AverageCost.harris_slln

by tianyipeng · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

ergodic-theoremharris-recurrencelaw-of-large-numbersmarkov-chain

Let EEE be a standard Borel space and let PPP be a Markov kernel on EEE. Suppose the chain is positive Harris recurrent: it is Harris recurrent with respect to some nonzero σ\sigmaσ-finite measure φ\varphiφ and admits an invariant probability measure μ\muμ (μP=μ\mu P=\muμP=μ). Let g:E→Rg:E\to\mathbb Rg:E→R be measurable with ∫∣g∣ dμ<∞\int|g|\,d\mu<\infty∫∣g∣dμ<∞. Then for every starting state x∈Ex\in Ex∈E, the Markov chain (Xn)n≥0(X_n)_{n\ge0}(Xn​)n≥0​ with kernel PPP and X0=xX_0=xX0​=x satisfies

lim⁡n→∞1n∑k=0n−1g(Xk)=∫Eg dμPx-almost surely.\lim_{n\to\infty}\frac1n\sum_{k=0}^{n-1} g(X_k)=\int_E g\,d\mu\qquad P_x\text{-almost surely.}n→∞lim​n1​k=0∑n−1​g(Xk​)=∫E​gdμPx​-almost surely.

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 Cn/nC^n/nCn/n of a positive Harris recurrent stationary policy converges almost surely to ∫c(x,f(x)) μf(dx)\int c(x,f(x))\,\mu_f(dx)∫c(x,f(x))μf​(dx).

Formalization Note PxP_xPx​ is chainLaw P x, the Ionescu–Tulcea law of the chain on the path space ENE^{\mathbb N}EN. Meyn–Tweedie sum g(Φ1),…,g(Φn)g(\Phi_1),\dots,g(\Phi_n)g(Φ1​),…,g(Φn​); summing g(X0),…,g(Xn−1)g(X_0),\dots,g(X_{n-1})g(X0​),…,g(Xn−1​) 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 μ\muμ, which for a Harris recurrent chain is unique.

Preamble
import Mathlib
import Definitions.Def_RiskSensMDP_AverageCost_HarrisRecurrence

open MeasureTheory ProbabilityTheory Filter Finset
Formal statement
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
Source
Meyn & Tweedie, Markov Chains and Stochastic Stability, 2nd ed. (2009), Theorem 17.0.1 (i); cited in Bäuerle & Rieder, More Risk-Sensitive Markov Decision Processes (KIT 1000039663; Math. Oper. Res. 39(1), 2014), p. 17, proof of Theorem 5.1

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me