Proposition 4 — in the last zero problem no strategy beats the -max guarantee, from any
ProvedSecSampling.proposition_4conflict-graphindependent-samplingoptimal-stoppingp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Let and . For every (deterministic or randomized) strategy for the last zero problem, every and every , there is a size at which the performance of is less than
The -max strategy has performance at every size , so its guarantee from any is ; the proposition says no strategy that does not know has a larger one.
Differences from the source:
- encoding: no algorithm can achieve a better success guarantee than the k-max algorithm, starting from an arbitrary N₀ → for every ε > 0 and N₀ some size n ≥ N₀ has performance < kpᵏ(1−p) + ε; reason: the guarantee from N₀ is an infimum over n ≥ N₀, and k-max's equals kpᵏ(1−p) (Lemma 1 (ii) through the increasing reduction); the ε-form says exactly that no strategy's infimum exceeds it
- reading: the player wins if she stops on the last 0 of the sequence (Definition 1) → a string with no 0 is won by every strategy; reason: the page leaves this case open; p.2 declares it a win by vacuity for AOSp, and it changes the performance at size n by pⁿ only
- encoding: a randomized algorithm for the last zero problem → a function q m h ∈ [0, 1], the stopping probability given the norm m and the prefix h seen so far; reason: behavioural randomization is equivalent to any external randomness under perfect recall (Kuhn); it is one probability per information state of Definition 1
Preamble
import Mathlib import Definitions.Def_SecSampling_LastZero
Formal statement
namespace SecSampling
/-- **Proposition 4** (arXiv:2011.07869v1, p.10). For the last zero problem with any value of
`p`, no algorithm (deterministic or randomized) can achieve a better success guarantee than the
k-max algorithm, starting from an arbitrary `N₀`: for every strategy `q` (which does not know the
size), every `ε > 0` and every `N₀`, there is a size `n ≥ N₀` at which the performance of `q` is
below `kpᵏ(1−p) + ε`, with `k = ⌊1/(1−p)⌋`.
**Formalization Note.** `kpᵏ(1−p)` is the k-max guarantee from any `N₀` on: by Lemma 1 (ii)
through the increasing reduction, k-max's performance at size `n ≥ k + 1` is `kpᵏ(1−p) + pⁿ`. -/
theorem proposition_4 (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) (q : LZStrategy)
(hq : IsLZStrategy q) (ε : ℝ) (hε : 0 < ε) (N₀ : ℕ) :
∃ n : ℕ, N₀ ≤ n ∧ perfLZ p q n < guarantee p + ε := 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, Proposition 4, p.10 (PDF p.11); restated in §5.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.