Lemma 17 — the fill-in strategy has optimal average performance in every window
ProvedSecSampling.lemma_17conflict-graphindependent-samplingoptimal-stoppingp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Let and consider a window . The fill-in strategy for this window is a valid algorithm in the conflict graph, and every valid (randomized) algorithm has average performance in the window at most that of the fill-in strategy:
Combined with Lemma 19, this bounds the window average of every strategy by that of -max plus .
Differences from the source:
- reading: the fill-in strategy has optimal average performance → fill-in is valid, and its window average is at least that of every valid randomized selection; reason: p.25: "extending this lemma suffices to extend the negative results to randomized algorithms"; optimality is among valid algorithms, and fill-in is one
- encoding: a monotone path is a possibly infinite path (p.15) → validity is required on finite monotone paths; reason: the terms are nonnegative, so a sum over an infinite path is bounded by 1 iff all its finite partial sums are
Preamble
import Mathlib import Definitions.Def_SecSampling_FractionalSelection
Formal statement
namespace SecSampling
/-- **Lemma 17** (arXiv:2011.07869v1, p.22). The fill-in strategy has optimal average performance
for any window `[n, n + t]`: it is a valid algorithm in the conflict graph, and every valid
(randomized) algorithm has average performance in the window at most that of the fill-in
strategy. -/
theorem lemma_17 (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) (n t : ℕ) :
IsValidSel (fillIn p n t) ∧
∀ qs : List Bool → ℝ, IsValidSel qs → windowAvg p qs n t ≤ windowAvg p (fillIn p n t) n t := by sorry
end SecSampling
Source
J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk & A. Tsigonias-Dimitriadis, The Secretary Problem with Independent Sampling, arXiv:2011.07869v1, https://arxiv.org/abs/2011.07869v1, Lemma 17, p.22 (PDF p.23); extension to randomized algorithms, p.25
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.