(1.3), p. 1214 — expected maximum bounded by threshold excess
ProvedSamuelCahnProphet.Median.eq_1_3optimal-stoppingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitythreshold-rule
For any real and a nonempty finite family of measurable observations on a probability space, let and . Then
Here the expectations are extended nonnegative expectations of positive parts; when , the display is exactly the paper's (1.3). The bound supplies the upper estimate on the prophet's expected reward.
Formalization Note The statement allows arbitrary real ; is the extended nonnegative representation of the paper's , which is nonnegative when is a median of nonnegative observations. Neither independence nor observation nonnegativity is needed for this inequality.
Preamble
import Mathlib import Definitions.Def_SamuelCahnProphet_Median_Setting
Formal statement
namespace SamuelCahnProphet.Median
open MeasureTheory ProbabilityTheory
theorem eq_1_3 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{n : ℕ} [NeZero n] (X : Fin n → Ω → ℝ) (hXm : ∀ i, Measurable (X i)) (m : ℝ) :
(∫⁻ ω, ENNReal.ofReal (maxX X ω) ∂P) ≤
ENNReal.ofReal m + ∫⁻ ω, ENNReal.ofReal (maxX X ω - m) ∂P ∧
ENNReal.ofReal m + (∫⁻ ω, ENNReal.ofReal (maxX X ω - m) ∂P) ≤
ENNReal.ofReal m + beta P X m := by sorry
end SamuelCahnProphet.Median
Source
Samuel-Cahn, Comparison of threshold stop rules and maximum for independent nonnegative random variables, Ann. Probab. 12 (1984), p. 1214, (1.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.