Lemma 5 — exponential decay of estimation errors
ProvedKeskinZeevi.IncumbentSufficient.estimation_error_exponential_decayConsider the incumbent price model with light-tailed i.i.d. demand shocks. There is a constant , depending only on the model and the law of the shocks, such that for every pricing policy , every slope , all and all ,
Once the accumulated information is large, the least squares slope estimate is accurate with exponentially high probability, whatever the policy did to accumulate that information.
Formalization Note. is chosen before the policy, the slope, , and , 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 , so is the paper's estimate.
import Mathlib import Definitions.Def_RobustBooking_Shared_Noise import Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares open RobustBooking.Shared open MeasureTheory ProbabilityTheory
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Fix:
- a model with slope interval ;
- a measurable space with a probability measure ;
- noise functions ;
- a real number .
Hypothesis. Assume 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 ) cannot be stated from this code.
Conclusion. There exists a real with the following property. For every policy for , every , all reals and , and every natural number :
The ingredients are:
- , where is the price deviation that generates under slope and noise ;
- , set to when ;
- .
The inequalities are strict for and non-strict for . The right-hand side is read as an extended nonnegative real.
Dependence of . The constant is chosen before , , , and . It may depend only on , , and .
Degenerate cases.
- : since , the event excludes every where the estimate defaults to .
- Non-measurable event: of the event is its outer measure.
- Empty : no probability measure exists on it, so the statement is vacuous.
- Unsatisfiable noise hypothesis: if is unsatisfiable for some (for example, a negative ), the statement is vacuous for that . Whether this happens cannot be determined from the code shown.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.