Proof of Theorem 2, p. 1215 — "because of Theorem 1": EX*ₙ ≤ 2 sup_{t∈T*ₙ} E⁺X_t for i.i.d. Xᵢ ≥ 0
ProvedSamuelCahnProphet.IID.upper_boundiidp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalitythreshold-rule
Let and let be i.i.d. nonnegative random variables with common law , a probability measure on . Let be the class of threshold rules , with . Then
This is the upper half of Theorem 2, which the proof attributes to Theorem 1 (p. 1214). It is the i.i.d. case of the goal of the companion mission I of this series.
Formalization Note. The i.i.d. variables are the coordinates of under the product measure , the standard model of an i.i.d. sample; every quantity involved depends only on the joint law. "Nonnegative" is . Expectations are in , so the bound also covers .
Preamble
import Mathlib import Definitions.Def_SamuelCahnProphet_IID_Setting open MeasureTheory Filter Topology
Formal statement
namespace SamuelCahnProphet.IID
theorem upper_bound (n : ℕ) [NeZero n] (μ : Measure ℝ) [IsProbabilityMeasure μ]
(hμ : μ (Set.Iio 0) = 0) :
Emax μ n ≤ 2 * supEplus μ n := by sorry
end SamuelCahnProphet.IID
Source
Samuel-Cahn, Comparison of threshold stop rules and maximum for independent nonnegative random variables, Ann. Probab. 12 (1984), p. 1215, proof of Theorem 2, first sentence ("Because of Theorem 1"); Theorem 1, p. 1214
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.