Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Kernel of full Markov-chain trajectories indexed by the initial state

Definition
MarkovChainKernel

by Harry_Xu · Jul 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditskernelsmarkov-chainsprobability

Given a Markov transition kernel PPP on a measurable state space, this construction packages the law of the entire trajectory (X0,X1,…)(X_0,X_1,\ldots)(X0​,X1​,…) as a Markov kernel from the initial state xxx to trajectory space. Evaluating the kernel at xxx is definitionally identified with the existing trajectory measure Px\mathbb P_xPx​.

This interface makes measurability of initial-state-dependent trajectory expectations available through the standard measurable-integral API.

Definition code
import Definitions.Def_GittinsIndex

open MeasureTheory ProbabilityTheory

namespace BanditAlgorithm

/-- The Markov kernel sending an initial state to the law of the full
time-homogeneous Markov-chain trajectory started from that state. -/
noncomputable def markovChainKernel
    {S : Type*} [MeasurableSpace S]
    (P : Kernel S S) [IsMarkovKernel P] : Kernel S (ℕ → S) :=
  (Kernel.traj (markovChainStep P) 0).comap
    (fun x (_ : Finset.Iic 0) ↦ x) (by fun_prop)

instance
    {S : Type*} [MeasurableSpace S]
    (P : Kernel S S) [IsMarkovKernel P] :
    IsMarkovKernel (markovChainKernel P) := by
  rw [markovChainKernel]
  infer_instance

@[simp]
lemma markovChainKernel_apply
    {S : Type*} [MeasurableSpace S]
    (P : Kernel S S) [IsMarkovKernel P] (x : S) :
    markovChainKernel P x = markovChainMeasure P x := by
  ext A hA
  rw [markovChainKernel, markovChainMeasure, Kernel.trajMeasure]
  rw [Measure.bind_apply hA (Kernel.aemeasurable _)]
  rw [Measure.map_dirac' (by fun_prop)]
  rw [lintegral_dirac' _
    ((Kernel.traj (markovChainStep P) 0).measurable_coe hA)]
  change
    Kernel.traj (markovChainStep P) 0 (fun _ ↦ x) A =
      Kernel.traj (markovChainStep P) 0
        ((MeasurableEquiv.piUnique (fun _ : Finset.Iic 0 ↦ S)).symm x) A
  congr 2

end BanditAlgorithm
Source
Lattimore and Szepesvari, Bandit Algorithms (Cambridge University Press, 2020), printed p. 442, Theorem 35.3 setup for a Markov reward process with initial-state laws P_x, and printed p. 448, setup preceding Assumption 35.6.

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