Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — the process (Xt,Zt,Yt)(X_t,Z_t,Y_t)(Xt​,Zt​,Yt​) is α\alphaα-mixing with α(h)≤γh−1\alpha(h)\le\gamma^{h-1}α(h)≤γh−1

Proved
TPG.lemma_2_alpha_mixing

by Wenqian Xing · Oct 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

causal-inferencemarkov-chainnonstationaritypolicy-gradienttreatment-effect

Setting. SSS is a finite state space and the action Zt∈{0,1}Z_t\in\{0,1\}Zt​∈{0,1} is control or treatment. Time is t=0,1,…,T−1t=0,1,\dots,T-1t=0,1,…,T−1, which is the source's time t+1t+1t+1. Under action zzz at time ttt the state moves according to a transition matrix PztP_z^tPzt​, i.e. P(Xt+1=x′∣Xt=x,Zt=z)=Pzt(x,x′)\mathbb P(X_{t+1}=x'\mid X_t=x,Z_t=z)=P_z^t(x,x')P(Xt+1​=x′∣Xt​=x,Zt​=z)=Pzt​(x,x′); the matrices may depend on ttt arbitrarily. The initial state X0X_0X0​ has distribution ρ\rhoρ, and the reward YtY_tYt​ has distribution R(⋅∣Xt,Zt)R(\cdot\mid X_t,Z_t)R(⋅∣Xt​,Zt​) on R\mathbb RR, with R([−M,M]∣x,z)=1R([-M,M]\mid x,z)=1R([−M,M]∣x,z)=1 for all x,zx,zx,z and conditional independence from everything else given (Xt,Zt)(X_t,Z_t)(Xt​,Zt​). Under the policy πθ\pi_\thetaπθ​ every action is treatment with probability θ\thetaθ, independently of everything else; Eθ\mathbb E_\thetaEθ​, Pθ\mathbb P_\thetaPθ​ and Var⁡θ\operatorname{Var}_\thetaVarθ​ refer to the law of the trajectory (Xt,Zt,Yt)t<T(X_t,Z_t,Y_t)_{t<T}(Xt​,Zt​,Yt​)t<T​ under πθ\pi_\thetaπθ​.

Assumption 1 (mixing time) with constant γ∈(0,1)\gamma\in(0,1)γ∈(0,1): for every time t<Tt<Tt<T, every action zzz and every pair of probability vectors f,f′f,f'f,f′ on SSS, ∥f′Pzt−fPzt∥TV≤γ ∥f′−f∥TV\|f'P_z^t-fP_z^t\|_{\mathrm{TV}}\le\gamma\,\|f'-f\|_{\mathrm{TV}}∥f′Pzt​−fPzt​∥TV​≤γ∥f′−f∥TV​, where ∥f−f′∥TV=12∥f−f′∥1\|f-f'\|_{\mathrm{TV}}=\tfrac12\|f-f'\|_1∥f−f′∥TV​=21​∥f−f′∥1​. The kernel deviation is δ=sup⁡t<Tsup⁡x∈S∥P1t(x,⋅)−P0t(x,⋅)∥TV\delta=\sup_{t<T}\sup_{x\in S}\|P_1^t(x,\cdot)-P_0^t(x,\cdot)\|_{\mathrm{TV}}δ=supt<T​supx∈S​∥P1t​(x,⋅)−P0t​(x,⋅)∥TV​.

For a≤ba\le ba≤b let Fab=σ((Xt,Zt,Yt):a≤t≤b)\mathcal F_a^b=\sigma\bigl((X_t,Z_t,Y_t):a\le t\le b\bigr)Fab​=σ((Xt​,Zt​,Yt​):a≤t≤b) be the σ\sigmaσ-algebra generated by the states, actions and rewards at times aaa through bbb.

Lemma. Under Assumption 1, the process (Xt,Zt,Yt)t<T(X_t,Z_t,Y_t)_{t<T}(Xt​,Zt​,Yt​)t<T​ is α\alphaα-mixing under every Bernoulli randomization policy πθ\pi_\thetaπθ​, 0<θ<10<\theta<10<θ<1: for all integers s,h≥0s,h\ge0s,h≥0 with s+h+1≤T−1s+h+1\le T-1s+h+1≤T−1, every A∈F0sA\in\mathcal F_0^{s}A∈F0s​ and every B∈Fs+h+1T−1B\in\mathcal F_{s+h+1}^{T-1}B∈Fs+h+1T−1​,

∣Pθ(A∩B)−Pθ(A) Pθ(B)∣≤γh.\bigl|\mathbb P_\theta(A\cap B)-\mathbb P_\theta(A)\,\mathbb P_\theta(B)\bigr|\le\gamma^{h} .​Pθ​(A∩B)−Pθ​(A)Pθ​(B)​≤γh.

In the source's notation, with lag h′=h+1≥1h'=h+1\ge1h′=h+1≥1 and split point s′=s+1s'=s+1s′=s+1, this is α(h′)≤γh′−1\alpha(h')\le\gamma^{h'-1}α(h′)≤γh′−1 for the coefficient α(h′)=sup⁡1≤s′≤T−h′sup⁡A∈F1s′, B∈Fs′+h′T∣P(A∩B)−P(A)P(B)∣\alpha(h')=\sup_{1\le s'\le T-h'}\sup_{A\in\mathcal F_1^{s'},\,B\in\mathcal F_{s'+h'}^{T}}|\mathbb P(A\cap B)-\mathbb P(A)\mathbb P(B)|α(h′)=sup1≤s′≤T−h′​supA∈F1s′​,B∈Fs′+h′T​​∣P(A∩B)−P(A)P(B)∣.

The lemma quantifies how fast the experimental trajectory forgets its past, and is the input for the variance bound and for the consistency of the variance estimator.

Formalization Note The supremum defining α(h′)\alpha(h')α(h′) is unfolded into a statement for each split point and each pair of events. The reward bound is kept as a standing hypothesis of the model.

Preamble
import Mathlib
import Definitions.Def_TPG_Model
import Definitions.Def_TPG_Estimators
import Definitions.Def_TPG_Inference

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
Formal statement
namespace TPG
theorem lemma_2_alpha_mixing {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
    (E : Env S) (T : ℕ) (θ γ M : ℝ)
    (hθ0 : 0 < θ) (hθ1 : θ < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
    (hmix : E.Mixing T γ) (hM : E.RewardBound M)
    (s h : ℕ) (hsh : s + h + 1 < T)
    (A B : Set (Traj S T))
    (hA : MeasurableSet[sigmaWindow T 0 s] A)
    (hB : MeasurableSet[sigmaWindow T (s + h + 1) T] B) :
    |(E.expLaw T θ).real (A ∩ B) - (E.expLaw T θ).real A * (E.expLaw T θ).real B|
      ≤ γ ^ h := by sorry
end TPG
Source
Johari, Peng, Xing, Estimation of Treatment Effects Under Nonstationarity via the Truncated Policy Gradient Estimator, revised manuscript of October 2026 (revision of arXiv:2506.05308v3, https://arxiv.org/abs/2506.05308); numbering follows the revised manuscript. Appendix A.4, pp. 28–29, Lemma 2 and its proof.
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Throughout, B={true,false}\mathbb{B}=\lbrace\mathrm{true},\mathrm{false}\rbraceB={true,false} denotes the two-element set of truth values.

Objects quantified over. The statement is asserted for all of the following.

  • A finite set SSS, equipped with a σ\sigmaσ-algebra in which every one-point set {x}\lbrace x\rbrace{x} is measurable. (As SSS is finite, every subset of SSS is then measurable.)
  • An environment EEE on SSS, which is a bundle of the following data together with the listed conditions:
    • for every natural number t∈Nt\in\mathbb{N}t∈N (all of N\mathbb{N}N, not only t<Tt\lt Tt<T) and every z∈Bz\in\mathbb{B}z∈B, a real matrix PtzP_t^{z}Ptz​ with rows and columns indexed by SSS, such that every entry satisfies Ptz(x,x′)≥0P_t^{z}(x,x')\ge 0Ptz​(x,x′)≥0 and every row satisfies ∑x′∈SPtz(x,x′)=1\sum_{x'\in S}P_t^{z}(x,x')=1∑x′∈S​Ptz​(x,x′)=1;
    • a function ρ:S→R\rho:S\to\mathbb{R}ρ:S→R with ρ(x)≥0\rho(x)\ge 0ρ(x)≥0 for all x∈Sx\in Sx∈S and ∑x∈Sρ(x)=1\sum_{x\in S}\rho(x)=1∑x∈S​ρ(x)=1 (so SSS cannot be empty);
    • for every x∈Sx\in Sx∈S and z∈Bz\in\mathbb{B}z∈B, a probability measure Rx,zR_{x,z}Rx,z​ on R\mathbb{R}R with its Borel σ\sigmaσ-algebra.
  • A natural number TTT, real numbers θ\thetaθ, γ\gammaγ, MMM, natural numbers sss, hhh (natural numbers include 000), and two sets AAA, BBB of trajectories, as described next.

The trajectory space. Let ΩT\Omega_TΩT​ be the set of all functions ω\omegaω from {0,1,…,T−1}\lbrace 0,1,\dots,T-1\rbrace{0,1,…,T−1} to S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R. For t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} write

ωt=(Xt(ω),Zt(ω),Yt(ω))∈S×B×R.\omega_t=\bigl(X_t(\omega),Z_t(\omega),Y_t(\omega)\bigr)\in S\times\mathbb{B}\times\mathbb{R}.ωt​=(Xt​(ω),Zt​(ω),Yt​(ω))∈S×B×R.

ΩT\Omega_TΩT​ carries the product σ\sigmaσ-algebra, where each factor S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R carries the product of the given σ\sigmaσ-algebra on SSS, the σ\sigmaσ-algebra of all subsets of B\mathbb{B}B, and the Borel σ\sigmaσ-algebra of R\mathbb{R}R. The sets AAA and BBB are subsets of ΩT\Omega_TΩT​.

The measure μθ\mu_\thetaμθ​ on ΩT\Omega_TΩT​. For a state path x=(x0,…,xT−1)∈STx=(x_0,\dots,x_{T-1})\in S^{T}x=(x0​,…,xT−1​)∈ST and a label path z=(z0,…,zT−1)∈BTz=(z_0,\dots,z_{T-1})\in\mathbb{B}^{T}z=(z0​,…,zT−1​)∈BT, define the real number wθ(x,z)w_\theta(x,z)wθ​(x,z) as the product of three factors:

  1. the product over t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} of the quantity that equals ρ(xt)\rho(x_t)ρ(xt​) if t=0t=0t=0 and equals 111 otherwise;
  2. the product over all ordered pairs (u,t)(u,t)(u,t) of indices in {0,…,T−1}\lbrace 0,\dots,T-1\rbrace{0,…,T−1} of the quantity that equals Puzu(xu,xt)P_u^{z_u}(x_u,x_t)Puzu​​(xu​,xt​) if u+1=tu+1=tu+1=t and equals 111 otherwise;
  3. the product over t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} of the quantity that equals θ\thetaθ if zt=truez_t=\mathrm{true}zt​=true and equals 1−θ1-\theta1−θ if zt=falsez_t=\mathrm{false}zt​=false.

For T≥1T\ge 1T≥1 this is

wθ(x,z)=ρ(x0)⋅∏u=0T−2Puzu(xu,xu+1)⋅∏t=0T−1qθ(zt),qθ(true)=θ,qθ(false)=1−θ.w_\theta(x,z)=\rho(x_0)\cdot\prod_{u=0}^{T-2}P_u^{z_u}(x_u,x_{u+1})\cdot\prod_{t=0}^{T-1}q_\theta(z_t),\qquad q_\theta(\mathrm{true})=\theta,\quad q_\theta(\mathrm{false})=1-\theta .wθ​(x,z)=ρ(x0​)⋅u=0∏T−2​Puzu​​(xu​,xu+1​)⋅t=0∏T−1​qθ​(zt​),qθ​(true)=θ,qθ​(false)=1−θ.

So the step from time uuu to time u+1u+1u+1 uses the matrix with time index uuu and the label zuz_uzu​ at time uuu, and the same number θ\thetaθ is used at every time ttt. The measure is the finite sum

μθ=∑(x,z)∈ST×BTmax⁡(wθ(x,z),0)⋅⨂t=0T−1(δxt⊗δzt⊗Rxt,zt),\mu_\theta=\sum_{(x,z)\in S^{T}\times\mathbb{B}^{T}}\max\bigl(w_\theta(x,z),0\bigr)\cdot\bigotimes_{t=0}^{T-1}\Bigl(\delta_{x_t}\otimes\delta_{z_t}\otimes R_{x_t,z_t}\Bigr),μθ​=(x,z)∈ST×BT∑​max(wθ​(x,z),0)⋅t=0⨂T−1​(δxt​​⊗δzt​​⊗Rxt​,zt​​),

where δ\deltaδ denotes a point mass, the inner ⊗\otimes⊗ is the product measure on S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R, and the outer ⨂\bigotimes⨂ is the product measure over the TTT time indices. In words: μθ\mu_\thetaμθ​ is a mixture over the finitely many pairs (x,z)(x,z)(x,z), with weight max⁡(wθ(x,z),0)\max(w_\theta(x,z),0)max(wθ​(x,z),0), of the law under which Xt=xtX_t=x_tXt​=xt​ and Zt=ztZ_t=z_tZt​=zt​ for every ttt and the real coordinates Y0,…,YT−1Y_0,\dots,Y_{T-1}Y0​,…,YT−1​ are independent with YtY_tYt​ distributed according to Rxt,ztR_{x_t,z_t}Rxt​,zt​​. Below, μθ(C)\mu_\theta(C)μθ​(C) denotes the measure of a set CCC read as a real number (value in [0,∞][0,\infty][0,∞] converted to R\mathbb{R}R, with ∞\infty∞ sent to 000).

Hypotheses.

  1. 0<θ0\lt\theta0<θ and θ<1\theta\lt 1θ<1.

  2. 0<γ0\lt\gamma0<γ and γ<1\gamma\lt 1γ<1.

  3. (One-step contraction, for each label separately.) For every natural number ttt with t<Tt\lt Tt<T, every z∈Bz\in\mathbb{B}z∈B, and every pair of functions f,f′:S→Rf,f':S\to\mathbb{R}f,f′:S→R that are probability vectors (all values ≥0\ge 0≥0 and values summing to 111),

12∑x′∈S∣∑x∈Sf′(x)Ptz(x,x′)−∑x∈Sf(x)Ptz(x,x′)∣≤γ⋅12∑x∈S∣f′(x)−f(x)∣.\frac12\sum_{x'\in S}\Bigl\lvert\sum_{x\in S}f'(x)P_t^{z}(x,x')-\sum_{x\in S}f(x)P_t^{z}(x,x')\Bigr\rvert\le\gamma\cdot\frac12\sum_{x\in S}\bigl\lvert f'(x)-f(x)\bigr\rvert .21​x′∈S∑​​x∈S∑​f′(x)Ptz​(x,x′)−x∈S∑​f(x)Ptz​(x,x′)​≤γ⋅21​x∈S∑​​f′(x)−f(x)​.
  1. (Bounded support of the real coordinate.) For every x∈Sx\in Sx∈S and z∈Bz\in\mathbb{B}z∈B, Rx,z([−M,M])=1R_{x,z}\bigl([-M,M]\bigr)=1Rx,z​([−M,M])=1, where [−M,M][-M,M][−M,M] is the closed interval of reals yyy with −M≤y≤M-M\le y\le M−M≤y≤M.

  2. s+h+1<Ts+h+1\lt Ts+h+1<T.

  3. AAA belongs to the σ\sigmaσ-algebra Fpast\mathcal{F}_{\mathrm{past}}Fpast​ on ΩT\Omega_TΩT​ generated by the coordinate maps ω↦ωt=(Xt,Zt,Yt)(ω)\omega\mapsto\omega_t=(X_t,Z_t,Y_t)(\omega)ω↦ωt​=(Xt​,Zt​,Yt​)(ω) for those t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} with 0≤t≤s0\le t\le s0≤t≤s; that is, the smallest σ\sigmaσ-algebra containing every set {ω:ωt∈C}\lbrace\omega:\omega_t\in C\rbrace{ω:ωt​∈C} with such a ttt and CCC a measurable subset of S×B×RS\times\mathbb{B}\times\mathbb{R}S×B×R.

  4. BBB belongs to the σ\sigmaσ-algebra Ffuture\mathcal{F}_{\mathrm{future}}Ffuture​ on ΩT\Omega_TΩT​ generated in the same way by the coordinate maps ω↦ωt\omega\mapsto\omega_tω↦ωt​ for those t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} with s+h+1≤t≤Ts+h+1\le t\le Ts+h+1≤t≤T.

Conclusion.

∣μθ(A∩B)−μθ(A)⋅μθ(B)∣≤γh.\bigl\lvert\mu_\theta(A\cap B)-\mu_\theta(A)\cdot\mu_\theta(B)\bigr\rvert\le\gamma^{h}.​μθ​(A∩B)−μθ​(A)⋅μθ​(B)​≤γh.

The inequality is non-strict, the exponent hhh is the natural number from the hypotheses, and there is no multiplicative constant in front of γh\gamma^{h}γh.

Edge cases and literal details.

  • Hypothesis 5 forces T≥2T\ge 2T≥2; s=0s=0s=0 and h=0h=0h=0 are both allowed.
  • The index set in hypothesis 6 is {0,…,s}\lbrace 0,\dots,s\rbrace{0,…,s} (all of these are below TTT). In hypothesis 7 the upper bound is written as t≤Tt\le Tt≤T, but trajectories only have indices t≤T−1t\le T-1t≤T−1, so that bound never excludes anything and the index set is {s+h+1,…,T−1}\lbrace s+h+1,\dots,T-1\rbrace{s+h+1,…,T−1}, which is non-empty by hypothesis 5. Both σ\sigmaσ-algebras are generated by the full triples (Xt,Zt,Yt)(X_t,Z_t,Y_t)(Xt​,Zt​,Yt​) at the listed times. The hhh indices s+1,…,s+hs+1,\dots,s+hs+1,…,s+h lie in neither index set.
  • For h=0h=0h=0 the two index sets are {0,…,s}\lbrace 0,\dots,s\rbrace{0,…,s} and {s+1,…,T−1}\lbrace s+1,\dots,T-1\rbrace{s+1,…,T−1} and the right-hand side is γ0=1\gamma^{0}=1γ0=1.
  • The number MMM occurs only in hypothesis 4 and not in the conclusion. No sign condition on MMM is written; if M<0M\lt 0M<0 the interval [−M,M][-M,M][−M,M] is empty and hypothesis 4 cannot hold.
  • Hypothesis 3 is imposed on the matrices PtzP_t^{z}Ptz​ for t=0,…,T−1t=0,\dots,T-1t=0,…,T−1 and for each of the two labels separately (not on a θ\thetaθ-weighted average of the two matrices). The measure μθ\mu_\thetaμθ​ involves only PuzP_u^{z}Puz​ for u=0,…,T−2u=0,\dots,T-2u=0,…,T−2; the matrix with index T−1T-1T−1 is constrained by hypothesis 3 but does not enter μθ\mu_\thetaμθ​, and the matrices with index ≥T\ge T≥T enter neither.
  • The clipping max⁡(⋅,0)\max(\cdot,0)max(⋅,0) is part of the definition of μθ\mu_\thetaμθ​. Under hypothesis 1 and the non-negativity of ρ\rhoρ and of the matrix entries, every wθ(x,z)w_\theta(x,z)wθ​(x,z) is already ≥0\ge 0≥0, so the clipping changes nothing here.
  • That μθ\mu_\thetaμθ​ is a probability measure is neither a hypothesis nor a conclusion of the statement; it follows from the construction (each product measure has total mass 111 and, by the row-sum and normalisation conditions, the weights wθ(x,z)w_\theta(x,z)wθ​(x,z) sum to 111).
Human review
  • Endorsed by tianyipeng · Oct 12, 2026

  • Endorsed by Wenqian Xing · Oct 12, 2026

    Confirmed by the mission captain (proposal self-audit).

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