Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One step of the trajectory kernel is an explicit pushforward of PPP

Proved
MarkovChainCLT.partialTraj_succ_self_apply_eq_map

by LukeBernese · Aug 15, 2026 · Mathlib c5ea003 (Lean v4.30.0)

ionescu-tulceamarkov-chainpath-spaceprobability

Let PPP be a Markov transition kernel on X\mathsf{X}X and let κn\kappa_nκn​ be the associated time-homogeneous one-step family used by the Ionescu–Tulcea construction, κn(ω,⋅)=P(ωn,⋅)\kappa_n(\omega,\cdot) = P(\omega_n,\cdot)κn​(ω,⋅)=P(ωn​,⋅). For every mmm and every partial trajectory v=(v0,…,vm)v = (v_0,\dots,v_m)v=(v0​,…,vm​),

partialTrajκ(m,m+1)(v)  =  P(vm,⋅)∘(w↦(v,w))−1,\mathrm{partialTraj}_{\kappa}(m, m+1)(v) \;=\; P(v_m, \cdot) \circ \Bigl(w \mapsto (v, w)\Bigr)^{-1},partialTrajκ​(m,m+1)(v)=P(vm​,⋅)∘(w↦(v,w))−1,

i.e. extending a trajectory by one time step is the pushforward of P(vm,⋅)P(v_m,\cdot)P(vm​,⋅) along the map that appends www as the new last coordinate, glueing the block Iic m\mathrm{Iic}\,mIicm with the singleton block Ioc m (m+1)\mathrm{Ioc}\,m\,(m+1)Iocm(m+1).

Why this is worth isolating. In Mathlib the one-step extension partialTraj κ m (m+1) is defined as

(id×k(κm)∗piSingletonm)∗ IicProdIocm,m+1,\bigl(\mathrm{id} \times_{\mathrm{k}} (\kappa_m)_*\mathrm{piSingleton}_m\bigr)_*\,\mathrm{IicProdIoc}_{m,m+1},(id×k​(κm​)∗​piSingletonm​)∗​IicProdIocm,m+1​,

a composite of a product kernel, a kernel pushforward, and a gluing map between dependent function types indexed by Finset.Iic and Finset.Ioc. That form is well suited to the abstract development, but it is unusable for hands-on computation: every concrete manipulation has to unfold the product kernel, discharge the measurability of the gluing map, and fight the dependent indexing.

This lemma performs that unfolding once and delivers the elementary description that any concrete argument actually wants: a single pushforward of PPP along an explicit map. Two things become immediate from it:

  • the one-step law depends on vvv only through its last coordinate vmv_mvm​ — this is precisely the Markov property, which is invisible in the definitional form;
  • the transition kernel is the same PPP for every mmm — time-homogeneity, which the general Kernel.traj API deliberately does not know, since it is built for possibly time-inhomogeneous families.

Both facts are exactly what is needed to prove that shifting a trajectory by one time step is the same as taking one step of PPP and then running the chain, and hence to establish stationarity of the chain started from an invariant measure, the Markov property on path space, and the mixing-coefficient estimates that depend on it.

Proof. Unfold partialTraj_succ_self, evaluate the product kernel at vvv (the first factor is Kernel.id, so it contributes the Dirac mass δv\delta_vδv​), and use Measure.dirac_prod to rewrite δv⊗ν\delta_v \otimes \nuδv​⊗ν as the pushforward of ν\nuν along w↦(v,w)w \mapsto (v,w)w↦(v,w). Composing the three pushforwards with Measure.map_map and observing κm(v)=P(vm,⋅)\kappa_m(v) = P(v_m,\cdot)κm​(v)=P(vm​,⋅) by definition gives the claim definitionally.

Preamble
import Definitions.Def_MarkovChainPathMeasure

open Filter Finset Function MeasurableEquiv MeasurableSpace MeasureTheory Preorder ProbabilityTheory
open scoped ENNReal NNReal Topology
Formal statement
theorem MarkovChainCLT.partialTraj_succ_self_apply_eq_map {S : Type*} [MeasurableSpace S]
    (P : Kernel S S) [IsMarkovKernel P] (m : ℕ) (v : Π _i : Finset.Iic m, S) :
    Kernel.partialTraj (X := fun _ : ℕ => S) (BanditAlgorithm.markovChainStep P) m (m + 1) v
      = (P (v ⟨m, Finset.mem_Iic.2 le_rfl⟩)).map
          (fun w => IicProdIoc (X := fun _ : ℕ => S) m (m + 1)
            (v, MeasurableEquiv.piSingleton (X := fun _ : ℕ => S) m w)) := by sorry
Source
C. T. Ionescu Tulcea, "Mesures dans les espaces produits", Atti Accad. Naz. Lincei Rend. 7 (1949) 208-211; J. Neveu, Mathematical Foundations of the Calculus of Probability, Holden-Day 1965, Ch. V; S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, 2nd ed., Cambridge 2009, Ch. 3.

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