Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma OA.1, OA p. 9 — Cantelli's inequality: P(X ≤ µ − a) ≤ σ²/(σ² + a²) for a ≥ 0

Proved
DistFreePricing.Maximin.lemma_OA_1

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

cantelli-inequalitychebyshevconcentrationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Cantelli's inequality (one-sided Chebyshev, left tail). Let XXX be a square-integrable random variable on a probability space with mean μ=E[X]\mu=\mathbb E[X]μ=E[X] and variance σ2\sigma^2σ2, σ≥0\sigma\ge0σ≥0. Then for every a≥0a\ge 0a≥0 (with σ2+a2>0\sigma^2+a^2>0σ2+a2>0, so that the bound is defined)

P(X<μ−a)≤P(X≤μ−a)≤σ2σ2+a2.\mathbb P(X<\mu-a)\le\mathbb P(X\le\mu-a)\le\frac{\sigma^2}{\sigma^2+a^2}.P(X<μ−a)≤P(X≤μ−a)≤σ2+a2σ2​.

If σ>0\sigma>0σ>0 then, equivalently, with a=kσa=k\sigmaa=kσ, for every k≥0k\ge 0k≥0

P(X<μ−kσ)≤P(X≤μ−kσ)≤11+k2,\mathbb P(X<\mu-k\sigma)\le\mathbb P(X\le\mu-k\sigma)\le\frac{1}{1+k^2},P(X<μ−kσ)≤P(X≤μ−kσ)≤1+k21​,

and the same kkk-form holds for a valuation VVV with law F∈FF\in\mathscr FF∈F (nonnegative support, mean μ\muμ, second moment μ2+σ2\mu^2+\sigma^2μ2+σ2): F((−∞,μ−kσ))≤F((−∞,μ−kσ])≤1/(1+k2)F((-\infty,\mu-k\sigma))\le F((-\infty,\mu-k\sigma])\le 1/(1+k^2)F((−∞,μ−kσ))≤F((−∞,μ−kσ])≤1/(1+k2).

This is the only probabilistic input of the paper's distribution-free bounds: it controls the mass below a price μ−kσ\mu-k\sigmaμ−kσ, hence the fraction of customers lost at that price.

Formalization Note Probabilities are measureReal; the variance is ProbabilityTheory.variance. The kkk-form uses the paper's standing σ>0\sigma>0σ>0 (pp. 8–9).

Differences from the source:

  • encoding: a random variable X that has mean μ and standard deviation σ → X ∈ L²(P) on a probability space, ∫ X dP = μ, variance X P = σ², σ ≥ 0; reason: having a standard deviation means a finite second moment; same instances
  • encoding: for all a ≥ 0 → for all a ≥ 0 with 0 < σ² + a²; reason: at σ = a = 0 the bound σ²/(σ² + a²) is 0/0; this excludes only that undefined case
  • reading: "Equivalently, … ≤ 1/(1+k²) for any k ≥ 0" → the k-form under 0 < σ; reason: the paper's standing σ > 0 (pp. 8–9); the substitution a = kσ needs it, and at σ = 0 the k-form is false (X = μ a.s., P(X ≤ μ) = 1 > 1/(1+k²) for k > 0)
  • reading: the k-form is written for the valuation V → stated both for X and for every law F ∈ 𝓕 (Iio/Iic masses of F); reason: the paper uses the k-form for the valuation law in Theorem 1; both readings are given
Preamble
import Mathlib
import Definitions.Def_DistFreePricing_Maximin_Setting
Formal statement
namespace DistFreePricing.Maximin

open MeasureTheory

/-- Lemma OA.1 (Cantelli's inequality, OA p. 9), for a square-integrable random variable with
mean `μ` and standard deviation `σ ≥ 0`: the `a`-form for every `a ≥ 0` at which the bound
`σ²/(σ² + a²)` is defined, and, under the paper's standing `σ > 0`, the equivalent `k`-form, also
for a valuation law `F ∈ 𝓕`. -/
theorem lemma_OA_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (X : Ω → ℝ) (hX : MemLp X 2 P) (μ σ : ℝ) (hμ : ∫ ω, X ω ∂P = μ) (hσ : 0 ≤ σ)
    (hvar : ProbabilityTheory.variance X P = σ ^ 2) :
    (∀ a : ℝ, 0 ≤ a → 0 < σ ^ 2 + a ^ 2 →
      P.real {ω | X ω < μ - a} ≤ P.real {ω | X ω ≤ μ - a} ∧
        P.real {ω | X ω ≤ μ - a} ≤ σ ^ 2 / (σ ^ 2 + a ^ 2)) ∧
    (0 < σ → ∀ k : ℝ, 0 ≤ k →
      P.real {ω | X ω < μ - k * σ} ≤ P.real {ω | X ω ≤ μ - k * σ} ∧
        P.real {ω | X ω ≤ μ - k * σ} ≤ 1 / (1 + k ^ 2)) ∧
    (0 < σ → ∀ F ∈ valClass μ σ, ∀ k : ℝ, 0 ≤ k →
      F.real (Set.Iio (μ - k * σ)) ≤ F.real (Set.Iic (μ - k * σ)) ∧
        F.real (Set.Iic (μ - k * σ)) ≤ 1 / (1 + k ^ 2)) := by sorry

end DistFreePricing.Maximin
Source
Chen, Hu, Perakis, Distribution-Free Pricing, accepted manuscript (MSOM, doi:10.1287/msom.2021.1055), Lemma OA.1, OA p. 9
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

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