Theorem 1, p. 1459 — nonadaptive thresholds attain (1 − 1/e) E[max_i X_i]
ProvedCorreaThreshold.Nonadaptive.theorem_1Let be independent nonnegative random variables, with . There exist fixed thresholds such that, writing ,
Under uniformly random arrival, the left side is the expected prize of taking the first observation above its assigned threshold. The theorem gives the paper's guarantee for nonadaptive stopping.
Formalization Note Indices are 0-based. Nonnegativity is assumed almost surely, a distributionally equivalent version of the paper's nonnegative random variables. The thresholds are chosen before seeing the sample, may equal , and use strict acceptance. Both expectations are extended nonnegative integrals, so heavy-tailed variables remain in scope. The statement covers atoms and makes no continuity assumption.
import Mathlib import Definitions.Def_CorreaThreshold_Nonadaptive_Setting
namespace CorreaThreshold.Nonadaptive
open MeasureTheory ProbabilityTheory
/-- Theorem 1: deterministic nonadaptive thresholds attain `1 - 1/e` of the prophet's reward. -/
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) :
∃ τ : Fin n → ENNReal,
ENNReal.ofReal (1 - Real.exp (-1)) *
(∫⁻ ω, ENNReal.ofReal (SamuelCahnProphet.Median.maxX X ω) ∂P) ≤
(∫⁻ ω, ENNReal.ofReal (ratio τ X ω) ∂P) := by sorry
end CorreaThreshold.Nonadaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.