Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2.1 — Strassen's ≤_i theorem

Proved
PalmQueueing.Ordering.strassen_st

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

couplingprobabilityqueueingstatisticsstochastic-ordering

Theorem 4.2.1 (Strassen's ≤i\le_i≤i​ theorem). For FFF and GGG in D(Rn)\mathcal{D}(\mathbb{R}^n)D(Rn), F≤iGF \le_i GF≤i​G if and only if there exist two Rn\mathbb{R}^nRn-valued random variables XXX and YYY defined on the same probability space with probability distribution FFF and GGG respectively, and such that X≤YX \le YX≤Y a.s.

The stochastic order holds exactly when the two distributions can be coupled monotonically. The book explains what the pointwise representations are for: they "provide a natural way for handling integral ordering in higher dimensions, at least whenever the independence assumptions of Property 4.2.3 are not satisfied ... particularly useful to establish comparison properties of embedded sequences in various queueing systems by simple induction arguments, which replace the usual analytical proofs, based on stability properties of the integral order with respect to convolutions or products of c.d.f."

In dimension 111 the coupling is explicit: take UUU uniform on [0,1][0,1][0,1] and set X=F−1(U)X = F^{-1}(U)X=F−1(U), Y=G−1(U)Y = G^{-1}(U)Y=G−1(U) with F−1(u)=inf⁡{x; F(x)>u}F^{-1}(u) = \inf\{x;\ F(x) > u\}F−1(u)=inf{x; F(x)>u}. In dimension nnn there is no such formula, which is why the theorem is Strassen's.

Both directions are asserted; the converse is immediate and the construction of the coupling is the theorem. No integrability hypothesis, unlike Theorem 4.2.2.

The book attributes it to Strassen and does not prove it: "The next two theorems on the pathwise representation of stochastic orders are proved in Strassen (1965)."

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Ordering_PartialOrders
import Definitions.Def_PalmQueueing_Ordering_IntegralOrders

/-!
# Theorem 4.2.1: Strassen's `≤_i` theorem (§4.2.3, p.277)
-/
Formal statement
namespace PalmQueueing.Ordering

open MeasureTheory

/-- **Theorem 4.2.1 (Strassen's `≤_i` theorem)** (p.277). For `F` and `G` in `𝒟(ℝⁿ)`, `F ≤_i G`
**if and only if** there exist two `ℝⁿ`-valued random variables `X` and `Y` defined on the same
probability space with probability distribution `F` and `G` respectively, and such that `X ≤ Y`
a.s.

The stochastic order holds exactly when the two distributions can be **coupled monotonically**.
This is the pathwise representation that makes the order usable in higher dimensions: "These
representations are particularly useful to establish comparison properties of embedded sequences
in various queueing systems by simple induction arguments, which replace the usual analytical
proofs, based on stability properties of the integral order with respect to convolutions or
products of c.d.f."

Both directions are asserted; the converse — that a monotone coupling gives the order — is
immediate, and the construction of the coupling is the theorem.

In dimension `1` the coupling is explicit and the book gives it: take `U` uniform on `[0,1]` and
set `X = F^{-1}(U)`, `Y = G^{-1}(U)` with `F^{-1}(u) = inf{x; F(x) > u}`. In dimension `n` no such
formula is available, which is why the theorem is Strassen's.

**No integrability hypothesis**, unlike Theorem 4.2.2: the stochastic order does not need first
moments. -/
theorem strassen_st {n : ℕ} (F G : Measure (Fin n → ℝ))
    (hF : IsDistribution F) (hG : IsDistribution G) :
    StLe F G ↔
      ∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω) (_ : IsProbabilityMeasure P)
        (X Y : Ω → Fin n → ℝ),
        Measurable X ∧ Measurable Y ∧
        Measure.map X P = F ∧ Measure.map Y P = G ∧
        ∀ᵐ ω ∂P, CoordLe (X ω) (Y ω) := by sorry

end PalmQueueing.Ordering
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 277, Theorem 4.2.1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

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