Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2.2 — Strassen's ≤_cx theorem

Proved
PalmQueueing.Ordering.strassen_cx

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

couplingmartingaleprobabilityqueueingstatisticsstochastic-ordering

Theorem 4.2.2 (Strassen's ≤cx\le_{cx}≤cx​ theorem). Let FFF and GGG be two integrable distributions in D(Rn)\mathcal{D}(\mathbb{R}^n)D(Rn); F≤cxGF \le_{cx} GF≤cx​G (resp. F≤icxGF \le_{icx} GF≤icx​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 distributions FFF and GGG respectively, and such that E[Y∣X]=XE[Y \mid X] = XE[Y∣X]=X (resp. E[Y∣X]≥XE[Y \mid X] \ge XE[Y∣X]≥X) a.s.

The convex order holds exactly when the larger distribution is a martingale dilation of the smaller: GGG is obtained from FFF by spreading each point out without moving its conditional mean. This is the classical Strassen representation, and it is what makes the convex order tractable — comparison results for queues become induction arguments on a coupling rather than analytic manipulations of convolutions of c.d.f.'s.

Both clauses are stated, as the book states them together: ≤cx\le_{cx}≤cx​ with E[Y∣X]=XE[Y \mid X] = XE[Y∣X]=X and ≤icx\le_{icx}≤icx​ with E[Y∣X]≥XE[Y \mid X] \ge XE[Y∣X]≥X.

Both directions are asserted. The hard one is the construction of the coupling; a one-directional statement would be the easy half, since Jensen's inequality gives F≤cxGF \le_{cx} GF≤cx​G from any such pair immediately.

E[Y∣X]E[Y \mid X]E[Y∣X] is a conditional expectation, not an equality of expectations: the content is that the identity holds a.s. given XXX.

Integrability is a hypothesis here and not in Theorem 4.2.1. The convex order needs first moments; the stochastic order does not. The two are not harmonised.

The book attributes both theorems to Strassen (1965) and proves neither. Example 4.2.3 on the same page shows the construction at work: for the comparison of exponential and Erlang distributions, symmetry makes E[Yi∣X]E[Y_i \mid X]E[Yi​∣X] a function Ψ(X)\Psi(X)Ψ(X) independent of iii, and Ψ(X)=E[1n∑iYi∣X]=E[X/n∣X]=X/n\Psi(X) = E[\frac{1}{n}\sum_i Y_i \mid X] = E[X/n \mid X] = X/nΨ(X)=E[n1​∑i​Yi​∣X]=E[X/n∣X]=X/n a.s.

Preamble
import Mathlib
import Definitions.Def_PalmQueueing_Ordering_PartialOrders
import Definitions.Def_PalmQueueing_Ordering_IntegralOrders

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

open MeasureTheory

/-- **Theorem 4.2.2 (Strassen's `≤_cx` theorem)** (p.278). Let `F` and `G` be two integrable
distributions in `𝒟(ℝⁿ)`; `F ≤_cx G` (resp. `F ≤_icx G`) **if and only if** there exist two
`ℝⁿ`-valued random variables `X` and `Y` defined on the same probability space with distributions
`F` and `G` respectively, and such that `E[Y | X] = X` (resp. `E[Y | X] ≥ X`) a.s.

The convex order holds exactly when the larger distribution is a **martingale dilation** of the
smaller: `G` is obtained from `F` by spreading each point out without moving its conditional mean.
That is the classical Strassen representation, and it is what makes the convex order tractable —
comparison results for queues become induction arguments on a coupling, rather than analytic
manipulations of convolutions of c.d.f.'s.

Both clauses are in the statement, as the book states them together: the `≤_cx` case with
`E[Y | X] = X` and the `≤_icx` case with `E[Y | X] ≥ X`.

**Both directions are asserted.** The hard one is the construction of the coupling; a
one-directional statement would be the easy half, since Jensen's inequality gives `F ≤_cx G` from
any such pair immediately.

`E[Y | X]` is a **conditional expectation**, not an equality of expectations: the whole content is
that the identity holds pointwise a.s. given `X`.

**Integrability is a hypothesis here and not in Theorem 4.2.1.** The convex order needs first
moments; the stochastic order does not. The two theorems are not harmonised.

The book attributes both to Strassen and does not prove them: "The next two theorems on the
pathwise representation of stochastic orders are proved in Strassen (1965)." -/
theorem strassen_cx {n : ℕ} (F G : Measure (Fin n → ℝ))
    (hF : IsDistribution F) (hG : IsDistribution G)
    (hFi : IsIntegrableDist F) (hGi : IsIntegrableDist G) :
    (CxLe 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 ∧
        condExp (MeasurableSpace.comap X inferInstance) P Y =ᵐ[P] X) ∧
    (IcxLe 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 ω)
          (condExp (MeasurableSpace.comap X inferInstance) P Y ω)) := by sorry

end PalmQueueing.Ordering
Source
Baccelli & Bremaud, Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, 2nd ed., Springer 2003, p. 278, Theorem 4.2.2
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