Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 1 — α\alphaα-mixing of the local summands Γt\Gamma_tΓt​: αΓ(h)≤γmax⁡{0, h−k−1}\alpha_\Gamma(h)\le\gamma^{\max\{0,\,h-k-1\}}αΓ​(h)≤γmax{0,h−k−1}

Proved
TPG.corollary_1_gamma_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​.

Fix a truncation size kkk and define the local summands

Γt=2 (2Zt−1)∑u=tmin⁡(t+k, T−1)Yu,t=0,…,T−1.\Gamma_t=2\,(2Z_t-1)\sum_{u=t}^{\min(t+k,\,T-1)}Y_u ,\qquad t=0,\dots,T-1 .Γt​=2(2Zt​−1)u=t∑min(t+k,T−1)​Yu​,t=0,…,T−1.

Corollary. Under Assumption 1 and a 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∈σ(Γ0,…,Γs)A\in\sigma(\Gamma_0,\dots,\Gamma_s)A∈σ(Γ0​,…,Γs​) and every B∈σ(Γs+h+1,…,ΓT−1)B\in\sigma(\Gamma_{s+h+1},\dots,\Gamma_{T-1})B∈σ(Γs+h+1​,…,ΓT−1​),

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

In the source's notation, with lag h′=h+1≥1h'=h+1\ge1h′=h+1≥1, this is αΓ(h′)≤γmax⁡{0, h′−k−1}\alpha_\Gamma(h')\le\gamma^{\max\{0,\,h'-k-1\}}αΓ​(h′)≤γmax{0,h′−k−1}: the bound is 111 for 1≤h′≤k+11\le h'\le k+11≤h′≤k+1 and γh′−k−1\gamma^{h'-k-1}γh′−k−1 for h′≥k+2h'\ge k+2h′≥k+2.

The summands Γt\Gamma_tΓt​ are the terms of the TPG estimator, τ^k=1T∑tΓt\widehat\tau_k=\frac1T\sum_t\Gamma_tτk​=T1​∑t​Γt​; the corollary transfers the mixing rate of the process to them, with a delay equal to the window length.

Formalization Note The supremum defining αΓ(h′)\alpha_\Gamma(h')αΓ​(h′) is unfolded into a statement for each split point and each pair of events; the exponent is a truncated subtraction of natural numbers.

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 corollary_1_gamma_alpha_mixing {S : Type} [Fintype S] [MeasurableSpace S] [MeasurableSingletonClass S]
    (E : Env S) (T k : ℕ) (θ γ 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[sigmaGamma S T k 0 s] A)
    (hB : MeasurableSet[sigmaGamma S T k (s + h + 1) T] B) :
    |(E.expLaw T θ).real (A ∩ B) - (E.expLaw T θ).real A * (E.expLaw T θ).real B|
      ≤ γ ^ (h - k) := 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, p. 29, Corollary 1.
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.
  • Natural numbers TTT and kkk, 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).

The real-valued functions GtG_tGt​. For each t∈{0,…,T−1}t\in\lbrace 0,\dots,T-1\rbracet∈{0,…,T−1} define Gt:ΩT→RG_t:\Omega_T\to\mathbb{R}Gt​:ΩT​→R by

Gt(ω)=c(Zt(ω))⋅∑u∈{0,…,T−1}:t≤u≤t+kYu(ω),G_t(\omega)=c\bigl(Z_t(\omega)\bigr)\cdot\sum_{u\in\lbrace 0,\dots,T-1\rbrace : t\le u\le t+k}Y_u(\omega),Gt​(ω)=c(Zt​(ω))⋅u∈{0,…,T−1}:t≤u≤t+k∑​Yu​(ω),

where c(z)=2⋅(2⋅1[z=true]−1)c(z)=2\cdot\bigl(2\cdot\mathbf{1}[z=\mathrm{true}]-1\bigr)c(z)=2⋅(2⋅1[z=true]−1), that is, c(true)=2c(\mathrm{true})=2c(true)=2 and c(false)=−2c(\mathrm{false})=-2c(false)=−2. The sum runs over the times uuu from ttt up to t+kt+kt+k that exist in the trajectory, i.e. over u=t,…,min⁡(t+k,T−1)u=t,\dots,\min(t+k,T-1)u=t,…,min(t+k,T−1). Thus GtG_tGt​ depends on ω\omegaω only through ZtZ_tZt​ and Yt,…,Ymin⁡(t+k,T−1)Y_t,\dots,Y_{\min(t+k,T-1)}Yt​,…,Ymin(t+k,T−1)​, and not on any state coordinate XuX_uXu​.

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 Gpast\mathcal{G}_{\mathrm{past}}Gpast​ on ΩT\Omega_TΩT​ generated by the real-valued functions GtG_tGt​ 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 {ω:Gt(ω)∈C}\lbrace\omega:G_t(\omega)\in C\rbrace{ω:Gt​(ω)∈C} with such a ttt and CCC a Borel subset of R\mathbb{R}R.

  4. BBB belongs to the σ\sigmaσ-algebra Gfuture\mathcal{G}_{\mathrm{future}}Gfuture​ on ΩT\Omega_TΩT​ generated in the same way by the functions GtG_tGt​ 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)∣≤γmax⁡(h−k,0).\bigl\lvert\mu_\theta(A\cap B)-\mu_\theta(A)\cdot\mu_\theta(B)\bigr\rvert\le\gamma^{\max(h-k,0)}.​μθ​(A∩B)−μθ​(A)⋅μθ​(B)​≤γmax(h−k,0).

The exponent is the natural-number (truncated) difference of hhh and kkk: it equals h−kh-kh−k when k≤hk\le hk≤h and equals 000 when k≥hk\ge hk≥h. The inequality is non-strict and there is no multiplicative constant in front of the power of γ\gammaγ.

Edge cases and literal details.

  • Whenever k≥hk\ge hk≥h the exponent is 000 and the right-hand side is γ0=1\gamma^{0}=1γ0=1. In particular this is the case for h=0h=0h=0 with any kkk.
  • Hypothesis 5 forces T≥2T\ge 2T≥2; s=0s=0s=0, h=0h=0h=0 and k=0k=0k=0 are all allowed, and kkk may exceed TTT. For k=0k=0k=0, Gt=c(Zt)⋅YtG_t=c(Z_t)\cdot Y_tGt​=c(Zt​)⋅Yt​.
  • The index set in hypothesis 6 is {0,…,s}\lbrace 0,\dots,s\rbrace{0,…,s}. 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.
  • The two σ\sigmaσ-algebras are generated by the scalar functions GtG_tGt​ only (each a signed sum ±2∑Yu\pm 2\sum Y_u±2∑Yu​), not by the individual coordinates XtX_tXt​, ZtZ_tZt​, YtY_tYt​.
  • The generators of Gpast\mathcal{G}_{\mathrm{past}}Gpast​ are functions of the coordinates ZtZ_tZt​ (0≤t≤s0\le t\le s0≤t≤s) and YuY_uYu​ (0≤u≤min⁡(s+k,T−1)0\le u\le\min(s+k,T-1)0≤u≤min(s+k,T−1)); the generators of Gfuture\mathcal{G}_{\mathrm{future}}Gfuture​ are functions of ZtZ_tZt​ and YuY_uYu​ with s+h+1≤t,u≤T−1s+h+1\le t,u\le T-1s+h+1≤t,u≤T−1. When k≥h+1k\ge h+1k≥h+1 these two ranges of YYY-times overlap (both contain time s+h+1s+h+1s+h+1); the statement is asserted in that case too, with right-hand side 111.
  • 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