Lemma 4.8 — Bernoulli tail comparison: E[X] ≤ E[Y] < 4 implies Pr[1 + X ≤ Y] ≥ (1/7) Pr[max{1 + X, Y} > 5]
ProvedStratifyMarkets.DoubleAuction.lemma_4_8p2o-gran-per-chapterp2o-plan-paperp2o-v1poisson-binomialprobability
Let and be independent random variables, each a sum of independent Bernoulli random variables: and with arbitrary success probabilities. If , then
It is the probability comparison behind Lemma 4.10 (proof in Appendix A.1).
Differences from the source:
- encoding: two independent random variables X, Y, each a sum of independent Bernoulli random variables → families X : Fin l → Ω → ℝ, Y : Fin r → Ω → ℝ, each measurable, a.s. {0, 1}-valued and
iIndepFun, withIndepFun (Σ X_i) (Σ Y_j); reason: exactly the printed hypotheses; any l, r ≥ 0
Preamble
import Mathlib open MeasureTheory
Formal statement
namespace StratifyMarkets.DoubleAuction
/-- Lemma 4.8 (p. 32): if `X = Σ_{i<l} X_i` and `Y = Σ_{j<r} Y_j` are independent, each a sum of
independent Bernoulli random variables, and `E[X] ≤ E[Y] < 4`, then
`Pr[1 + X ≤ Y] ≥ (1/7) Pr[max{1 + X, Y} > 5]`. -/
theorem lemma_4_8 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(l r : ℕ) (X : Fin l → Ω → ℝ) (Y : Fin r → Ω → ℝ)
(hXm : ∀ i, Measurable (X i)) (hYm : ∀ j, Measurable (Y j))
(hXb : ∀ i, ∀ᵐ ω ∂P, X i ω = 0 ∨ X i ω = 1) (hYb : ∀ j, ∀ᵐ ω ∂P, Y j ω = 0 ∨ Y j ω = 1)
(hXi : ProbabilityTheory.iIndepFun X P) (hYi : ProbabilityTheory.iIndepFun Y P)
(hXY : ProbabilityTheory.IndepFun (fun ω => ∑ i, X i ω) (fun ω => ∑ j, Y j ω) P)
(hmean : ∫ ω, ∑ i, X i ω ∂P ≤ ∫ ω, ∑ j, Y j ω ∂P) (hfour : ∫ ω, ∑ j, Y j ω ∂P < 4) :
(1 / 7 : ENNReal) * P {ω | 5 < max (1 + ∑ i, X i ω) (∑ j, Y j ω)} ≤
P {ω | 1 + ∑ i, X i ω ≤ ∑ j, Y j ω} := by sorry
end StratifyMarkets.DoubleAuction
Source
Deng, Lin, Schoepflin, Wang, Stratifying Markets for Efficient Trade, STOC 2027 submission (manuscript sha256 49372bcf…), p. 32, Lemma 4.8 (proof App. A.1, pp. 56–57)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.