Lemma 7 — an NBUE page count is dominated by the exponential in the increasing convex order
ProvedProductFraming.Nest.lemma_7exponential-distributionnbuep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-orders
Let have law satisfying Assumption A3 (NBUE), and let be an exponential random variable with mean . Then for every function that is increasing and convex on and integrable under the law of ,
This comparison with the exponential distribution is what produces the constant in the analysis of NEST.
Formalization Note The law of is Mathlib's expMeasure, whose parameter is the rate . Integrability of under that law is added: Lean's Bochner integral is for a non-integrable function, while on the page makes the claim trivial in that case. Increasing and convex are required on , where both laws live; increasing means nondecreasing.
Preamble
import Mathlib import Definitions.Def_ProductFraming_Nest_Model
Formal statement
namespace ProductFraming.Nest
open Finset MeasureTheory ProbabilityTheory
/-- Lemma 7 (Gallego, Li, Truong, Wang 2020, p. 36): if `X` is NBUE and `Z` is exponential with
`E[Z] = E[X]`, then `E[g(X)] ≤ E[g(Z)]` for every increasing convex `g`. Mathlib's
`expMeasure` takes the rate, so the law of `Z` is `expMeasure (E[X])⁻¹`. The integrability of
`g` under the law of `Z` is added (otherwise the Bochner integral is `0`). -/
theorem lemma_7 (m : ℕ) (hm : 1 ≤ m) (lam : ℕ → ℝ) (hlam : IsPageLaw m lam) (hA3 : IsNBUE m lam)
(g : ℝ → ℝ) (hg_mono : MonotoneOn g (Set.Ici 0)) (hg_conv : ConvexOn ℝ (Set.Ici 0) g)
(hg_int : Integrable g (expMeasure (mean m lam)⁻¹)) :
∑ x ∈ Icc 1 m, lam x * g (x : ℝ) ≤ ∫ z, g z ∂(expMeasure (mean m lam)⁻¹) := by sorry
end ProductFraming.Nest
Source
Gallego, Li, Truong, Wang, Approximation Algorithms for Product Framing and Pricing, Operations Research (2020), DOI 10.1287/opre.2019.1875, authors' accepted manuscript, A.2, p. 36, Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.