Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5 — exponential decay of estimation errors

Proved
KeskinZeevi.IncumbentSufficient.estimation_error_exponential_decay

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

concentrationdynamic-pricingleast-squaresp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the incumbent price model with light-tailed i.i.d. demand shocks. There is a constant ρ>0\rho > 0ρ>0, depending only on the model and the law of the shocks, such that for every pricing policy π\piπ, every slope β∈B\beta \in \mathfrak Bβ∈B, all δ,m>0\delta, m > 0δ,m>0 and all t≥2t \ge 2t≥2,

Pβπ{∣β^t−β∣>δ, J^t≥m}≤2exp⁡(−ρ (δ∧δ2) m).\mathbb P^\pi_\beta\big\{ |\hat\beta_t - \beta| > \delta,\ \hat J_t \ge m \big\} \le 2 \exp\big(-\rho\, (\delta \wedge \delta^2)\, m\big).Pβπ​{∣β^​t​−β∣>δ, J^t​≥m}≤2exp(−ρ(δ∧δ2)m).

Once the accumulated information J^t\hat J_tJ^t​ is large, the least squares slope estimate is accurate with exponentially high probability, whatever the policy did to accumulate that information.

Formalization Note. ρ\rhoρ is chosen before the policy, the slope, δ\deltaδ, mmm and ttt, as on the page ("there exists … ρ such that, under any pricing policy π"). The probability is the measure of the set of noise realizations on which both events hold, as an ENNReal bounded by ENNReal.ofReal. On that set J^t≥m>0\hat J_t \ge m > 0J^t​≥m>0, so β^t\hat\beta_tβ^​t​ is the paper's estimate.

Preamble
import Mathlib
import Definitions.Def_RobustBooking_Shared_Noise
import Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares
open RobustBooking.Shared

open MeasureTheory ProbabilityTheory
Formal statement
namespace KeskinZeevi.IncumbentSufficient

/-- Keskin–Zeevi 2014, p. 1150, Lemma 5 (28): there is a constant `ρ > 0`, depending only on the
model and the noise law, such that for every policy `π`, every `β ∈ 𝔅`, all `δ, m > 0` and all
`t ≥ 2`, `P(|β̂_t - β| > δ, Ĵ_t ≥ m) ≤ 2 exp(-ρ (δ ∧ δ²) m)`. -/
theorem estimation_error_exponential_decay (M : Model) {Ω : Type*} [MeasurableSpace Ω]
    (P : Measure Ω) [IsProbabilityMeasure P] (ε : ℕ → Ω → ℝ) (σ : ℝ)
    (hε : LightTailedNoise P ε σ) :
    ∃ ρ : ℝ, 0 < ρ ∧
      ∀ (π : Policy M) (β : ℝ), β ∈ M.B →
      ∀ δ m : ℝ, 0 < δ → 0 < m → ∀ t : ℕ, 2 ≤ t →
        P {ω | δ < |betaHat π β ε t ω - β| ∧ m ≤ Jhat π β ε t ω} ≤
          ENNReal.ofReal (2 * Real.exp (-(ρ * min δ (δ ^ 2) * m))) := by sorry

end KeskinZeevi.IncumbentSufficient
Source
Keskin and Zeevi, Dynamic Pricing with an Unknown Demand Model, Operations Research 62(5), 2014, p. 1150, Lemma 5, Eq. (28)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Fix:

  • a model MMM with slope interval B=[bmin⁡,bmax⁡]\mathfrak B = [b_{\min}, b_{\max}]B=[bmin​,bmax​];
  • a measurable space Ω\OmegaΩ with a probability measure PPP;
  • noise functions εs:Ω→R\varepsilon_s : \Omega \to \mathbb Rεs​:Ω→R;
  • a real number σ\sigmaσ.

Hypothesis. Assume LightTailedNoise(P,ε,σ)\mathrm{LightTailedNoise}(P, \varepsilon, \sigma)LightTailedNoise(P,ε,σ) holds. This predicate is defined in an external file whose content is not shown here, so its exact requirements (independence, sub-Gaussian or other tail bounds, zero mean, measurability, any sign condition on σ\sigmaσ) cannot be stated from this code.

Conclusion. There exists a real ρ>0\rho > 0ρ>0 with the following property. For every policy π\piπ for MMM, every β∈B\beta \in \mathfrak Bβ∈B, all reals δ>0\delta > 0δ>0 and m>0m > 0m>0, and every natural number t≥2t \ge 2t≥2:

P({ω:δ<∣β^t(ω)−β∣ and m≤J^t(ω)})≤2exp⁡(−ρ⋅min⁡(δ,δ2)⋅m).P\Bigl(\bigl\{\omega : \delta < |\hat\beta_t(\omega) - \beta| \text{ and } m \le \hat J_t(\omega)\bigr\}\Bigr) \le 2\exp\bigl(-\rho \cdot \min(\delta, \delta^2)\cdot m\bigr).P({ω:δ<∣β^​t​(ω)−β∣ and m≤J^t​(ω)})≤2exp(−ρ⋅min(δ,δ2)⋅m).

The ingredients are:

  • J^t=∑s=1txs2\hat J_t = \sum_{s=1}^t x_s^2J^t​=∑s=1t​xs2​, where xsx_sxs​ is the price deviation that π\piπ generates under slope β\betaβ and noise ε\varepsilonε;
  • β^t=∑s=1t(Ds−D^)xs/J^t\hat\beta_t = \sum_{s=1}^t (D_s - \hat D) x_s / \hat J_tβ^​t​=∑s=1t​(Ds​−D^)xs​/J^t​, set to 000 when J^t=0\hat J_t = 0J^t​=0;
  • Ds=D^+βxs+εsD_s = \hat D + \beta x_s + \varepsilon_sDs​=D^+βxs​+εs​.

The inequalities are strict for δ\deltaδ and non-strict for mmm. The right-hand side is read as an extended nonnegative real.

Dependence of ρ\rhoρ. The constant ρ\rhoρ is chosen before π\piπ, β\betaβ, δ\deltaδ, mmm and ttt. It may depend only on MMM, PPP, ε\varepsilonε and σ\sigmaσ.

Degenerate cases.

  • J^t=0\hat J_t = 0J^t​=0: since m>0m > 0m>0, the event m≤J^tm \le \hat J_tm≤J^t​ excludes every ω\omegaω where the estimate defaults to 000.
  • Non-measurable event: PPP of the event is its outer measure.
  • Empty Ω\OmegaΩ: no probability measure exists on it, so the statement is vacuous.
  • Unsatisfiable noise hypothesis: if LightTailedNoise(P,ε,σ)\mathrm{LightTailedNoise}(P, \varepsilon, \sigma)LightTailedNoise(P,ε,σ) is unsatisfiable for some σ\sigmaσ (for example, a negative σ\sigmaσ), the statement is vacuous for that σ\sigmaσ. Whether this happens cannot be determined from the code shown.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

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