Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — the discrete-time comparison theorem: coupled random sequences with Xi≤YiX_i \le Y_iXi​≤Yi​ for all iii a.s.

Proved
StochIneqPO.Comparison.comparison_theorem

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

comparison-theoremcouplingionescu-tulceap2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-sequencesstochastic-order

Let E1,E2,…E_1, E_2, \dotsE1​,E2​,… be partially ordered Polish spaces and En=E1×⋯×EnE^{n} = E_1 \times \cdots \times E_nEn=E1​×⋯×En​ with the coordinatewise order. Let P1,Q1P_1, Q_1P1​,Q1​ be probability measures on E1E_1E1​, and for n=2,3,…n = 2, 3, \dotsn=2,3,… let pn,qnp_n, q_npn​,qn​ be stochastic kernels from En−1E^{n-1}En−1 to EnE_nEn​. Assume P1≺Q1P_1 \prec Q_1P1​≺Q1​ and

pn(xn−1,⋅)≺qn(yn−1,⋅)whenever (x1,…,xn−1)≤(y1,…,yn−1).(4)p_n(x^{n-1}, \cdot) \prec q_n(y^{n-1}, \cdot) \qquad \text{whenever } (x_1, \dots, x_{n-1}) \le (y_1, \dots, y_{n-1}). \tag{4}pn​(xn−1,⋅)≺qn​(yn−1,⋅)whenever (x1​,…,xn−1​)≤(y1​,…,yn−1​).(4)

Then there are random variables XiX_iXi​, YiY_iYi​ with values in EiE_iEi​, i=1,2,…i = 1, 2, \dotsi=1,2,…, on a common probability space, such that X1∼P1X_1 \sim P_1X1​∼P1​, Y1∼Q1Y_1 \sim Q_1Y1​∼Q1​, the conditional distribution of XnX_nXn​ given Xn−1=xn−1X^{n-1} = x^{n-1}Xn−1=xn−1 is pn(xn−1,⋅)p_n(x^{n-1}, \cdot)pn​(xn−1,⋅), that of YnY_nYn​ given Yn−1=yn−1Y^{n-1} = y^{n-1}Yn−1=yn−1 is qn(yn−1,⋅)q_n(y^{n-1}, \cdot)qn​(yn−1,⋅), and

P(Xi≤Yi, i=1,2,… )=1.(5)P(X_i \le Y_i,\ i = 1, 2, \dots) = 1. \tag{5}P(Xi​≤Yi​, i=1,2,…)=1.(5)

This extends O'Brien's comparison theorem (and Kalmykov's) to random sequences in partially ordered Polish spaces: two processes whose initial laws and transition kernels are ordered can be realized on one probability space so that one path dominates the other for all times simultaneously.

Formalization Note The initial and conditional distributions determine the joint law of (X1,X2,… )(X_1, X_2, \dots)(X1​,X2​,…), which is the Ionescu-Tulcea measure; the conclusion states that the law of the whole sequence (Xn)(X_n)(Xn​) is Kernel.trajMeasure P₁ p and that of (Yn)(Y_n)(Yn​) is trajMeasure Q₁ q (equivalent to the conditional-law formulation, which holds only up to null sets). Indices are 0-based: the paper's EiE_iEi​, XiX_iXi​ are E (i - 1), X (i - 1), and the paper's kernel pnp_npn​ (n≥2n \ge 2n≥2) is p (n - 2) : Kernel (Π i : Iic (n - 2), E i) (E (n - 1)). Hypothesis (4) is pointwise for all ordered pairs of histories; no stochastic monotonicity of the kernels is assumed. The conclusion (5) is one almost-sure event for all indices jointly. Every EiE_iEi​ is a partially ordered Polish space by the paper's standing assumption (Sec. 1), although the theorem says "Polish spaces".

Preamble
import Mathlib
import Definitions.Def_StochIneqPO_Comparison_StochLE
Formal statement
namespace StochIneqPO.Comparison

open MeasureTheory ProbabilityTheory Finset

theorem comparison_theorem {E : ℕ → Type*} [∀ n, TopologicalSpace (E n)]
    [∀ n, PolishSpace (E n)] [∀ n, MeasurableSpace (E n)] [∀ n, BorelSpace (E n)]
    [∀ n, PartialOrder (E n)] [∀ n, OrderClosedTopology (E n)]
    (P₁ Q₁ : Measure (E 0)) [IsProbabilityMeasure P₁] [IsProbabilityMeasure Q₁]
    (p q : (n : ℕ) → Kernel (Π i : Iic n, E i) (E (n + 1)))
    [∀ n, IsMarkovKernel (p n)] [∀ n, IsMarkovKernel (q n)]
    (hPQ : StochLE P₁ Q₁)
    (hpq : ∀ n, ∀ x y : Π i : Iic n, E i, x ≤ y → StochLE (p n x) (q n y)) :
    ∃ (Ω : Type) (_ : MeasurableSpace Ω) (μ : Measure Ω), IsProbabilityMeasure μ ∧
      ∃ (X Y : (n : ℕ) → Ω → E n), (∀ n, Measurable (X n)) ∧ (∀ n, Measurable (Y n)) ∧
        μ.map (fun ω n => X n ω) = Kernel.trajMeasure P₁ p ∧
        μ.map (fun ω n => Y n ω) = Kernel.trajMeasure Q₁ q ∧
        ∀ᵐ ω ∂μ, ∀ n, X n ω ≤ Y n ω := by sorry

end StochIneqPO.Comparison
Source
Kamae, Krengel, O'Brien, Stochastic Inequalities on Partially Ordered Spaces, Ann. Probab. 5 (1977), Theorem 2, eqs. (4)–(5), p. 903 (PDF p. 5)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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