Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Time-homogeneity: the shift commutes with one-step extension of a trajectory

Proved
MarkovChainCLT.partialTraj_map_shift_succ

by LukeBernese · Aug 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

ionescu-tulceamarkov-chainpath-spaceprobabilitystationarity

Let PPP be a Markov kernel on X\mathsf{X}X and write σ\sigmaσ for the shift on initial segments, the map Iic(m+1)→Iic(m)\mathrm{Iic}(m{+}1) \to \mathrm{Iic}(m)Iic(m+1)→Iic(m) given by (σv)i=vi+1(\sigma v)_i = v_{i+1}(σv)i​=vi+1​, which drops the first coordinate of a partial trajectory. Then for every nnn and every u=(u0,…,un+1)u = (u_0,\dots,u_{n+1})u=(u0​,…,un+1​),

σ∗[partialTraj(n+1, n+2)(u)]  =  partialTraj(n, n+1)(σu).\sigma_*\bigl[\mathrm{partialTraj}(n{+}1,\,n{+}2)(u)\bigr] \;=\; \mathrm{partialTraj}(n,\,n{+}1)\bigl(\sigma u\bigr).σ∗​[partialTraj(n+1,n+2)(u)]=partialTraj(n,n+1)(σu).

In words: extending a trajectory by one step and then dropping its first coordinate is the same as dropping the first coordinate and then extending. The shift commutes with one-step extension.

Why it is the crux. This is the exact formal content of time-homogeneity, and it is where the two structural facts about the constant one-step family are actually consumed:

  • Markov property. The one-step extension of uuu uses the kernel P(un+1,⋅)P(u_{n+1},\cdot)P(un+1​,⋅), while the one-step extension of σu\sigma uσu uses P((σu)n,⋅)P\bigl((\sigma u)_n,\cdot\bigr)P((σu)n​,⋅). These are the same kernel because (σu)n=un+1(\sigma u)_n = u_{n+1}(σu)n​=un+1​ — the shift preserves the last coordinate, which is the only thing the transition law depends on.
  • Time-homogeneity. The kernel used at time n+1n+1n+1 and the kernel used at time nnn are both PPP. For a general, possibly time-inhomogeneous family κn\kappa_nκn​ the statement is simply false: one would be comparing κn+1\kappa_{n+1}κn+1​ with κn\kappa_nκn​.

Once the two transition kernels are identified, what remains is a purely combinatorial identity between the two gluing maps: appending a new coordinate at position n+2n+2n+2 and then shifting, versus shifting and then appending at position n+1n+1n+1. Both produce the function on Iic(n+1)\mathrm{Iic}(n{+}1)Iic(n+1) equal to ui+1u_{i+1}ui+1​ for i≤ni \le ni≤n and to the new coordinate at i=n+1i = n+1i=n+1.

Where it leads. Iterating this identity along the partialTraj recursion partialTraj(0, n{+}1) = partialTraj(n, n{+}1) \circ partialTraj(0, n) propagates the shift through all finite-dimensional marginals of the trajectory law. Combined with the fact that a path measure is determined by those marginals, it yields the global statement that shifting a trajectory by one time step is the same as taking one step of PPP and then running the chain — the identity underlying stationarity of a chain started from an invariant measure, the Markov property on path space, and every mixing-coefficient estimate that rests on it.

Proof. Rewrite both sides with the explicit pushforward description of a one-step extension, so each becomes a pushforward of a single measure P(un+1,⋅)P(u_{n+1},\cdot)P(un+1​,⋅) along an explicit gluing map. Composing the pushforwards reduces the claim to the pointwise identity between the two maps, which is settled by splitting on whether the index iii satisfies i≤ni \le ni≤n: in the first case both sides read off ui+1u_{i+1}ui+1​, in the second both return the newly drawn coordinate (using that for a constant family the singleton-block identification is the constant map).

Preamble
import Definitions.Def_MarkovChainPathMeasure

open Filter Finset Function MeasurableEquiv MeasurableSpace MeasureTheory Preorder ProbabilityTheory
open scoped ENNReal NNReal Topology
Formal statement
theorem MarkovChainCLT.partialTraj_map_shift_succ {S : Type*} [MeasurableSpace S]
    (P : Kernel S S) [IsMarkovKernel P] (n : ℕ) (u : Π _j : Finset.Iic (n + 1), S) :
    (Kernel.partialTraj (X := fun _ : ℕ => S) (BanditAlgorithm.markovChainStep P)
        (n + 1) (n + 1 + 1) u).map
        (fun v i => v ⟨i.1 + 1, Finset.mem_Iic.2 (Nat.succ_le_succ (Finset.mem_Iic.mp i.2))⟩)
      = Kernel.partialTraj (X := fun _ : ℕ => S) (BanditAlgorithm.markovChainStep P) n (n + 1)
          (fun i => u ⟨i.1 + 1, Finset.mem_Iic.2 (Nat.succ_le_succ (Finset.mem_Iic.mp i.2))⟩) := 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