Theorem 1, p. 1214 — a median threshold earns half the expected maximum
ProvedSamuelCahnProphet.Median.theorem_1independencemedianoptimal-stoppingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitythreshold-rule
Let be independent nonnegative random variables, , let , and let be a median of . Write . Then both conditional conclusions hold:
Thus one of the two median threshold rules guarantees at least half the expected maximum, with the positive stopped reward explicitly retained.
Formalization Note Nonnegativity is almost sure, independence is mutual, and expectations take values in , so no integrability condition is imposed. Formalization Note Indices are zero based in Lean, so the paper's event or becomes or . Expectations are extended nonnegative integrals, and the final observation is always taken if no earlier one crosses the threshold.
Preamble
import Mathlib import Definitions.Def_SamuelCahnProphet_Median_Setting
Formal statement
namespace SamuelCahnProphet.Median
open MeasureTheory ProbabilityTheory
theorem theorem_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{n : ℕ} [NeZero n] (X : Fin n → Ω → ℝ) (hXm : ∀ i, Measurable (X i))
(hXnn : ∀ i, ∀ᵐ ω ∂P, 0 ≤ X i ω) (hind : iIndepFun X P) (m : ℝ)
(hmed : IsMedian P (maxX X) m) :
(ENNReal.ofReal m ≤ beta P X m →
(∫⁻ ω, ENNReal.ofReal (maxX X ω) ∂P) ≤ 2 * EplusS P X m ∧
2 * EplusS P X m ≤ 2 * expStop P X (sRule X m)) ∧
(beta P X m ≤ ENNReal.ofReal m →
(∫⁻ ω, ENNReal.ofReal (maxX X ω) ∂P) ≤ 2 * EplusT P X m ∧
2 * EplusT P X m ≤ 2 * expStop P X (tRule 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, Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.