Proof of Lemma 1, p. 10 — optimizing p: the bound is maximized at p = p(k), with value 1/α(k)
ProvedOrdinalMSP.Forbidden.optimal_pconstantsoptimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Let be an integer and let
be the lower bound on obtained for sampling probability . With for and for :
- is an admissible sampling probability;
- ;
- maximizes over : for every .
This is the last step of the proof of the Key Lemma: "by optimizing the value of as a function of ", the guaranteed selection probability is , attained at .
Formalization Note is passed as a function g together with its defining equation, which branches on first. and are pK k and alphaK k of the Setting definition (Real.exp, Real.rpow). The page writes "the probability of is "; the formal content is that the lower bound attains the value at and that no other does better.
Preamble
import Mathlib import Definitions.Def_OrdinalMSP_Forbidden_Setting
Formal statement
namespace OrdinalMSP.Forbidden
theorem optimal_p (k : ℕ) (hk : 1 ≤ k) (g : ℝ → ℝ)
(hg : ∀ p, g p = if k = 1 then -p * Real.log p else (p - p ^ k) / ((k : ℝ) - 1)) :
pK k ∈ Set.Ioc 0 1 ∧ g (pK k) = 1 / alphaK k ∧ ∀ p ∈ Set.Ioc (0 : ℝ) 1, g p ≤ g (pK k) := by sorry
end OrdinalMSP.Forbidden
Source
Soto, Turkieltaub & Verdugo, Strong Algorithms for the Ordinal Matroid Secretary Problem, arXiv:1802.01997v1, proof of Lemma 1, p. 10, last sentence ("By optimizing the value of p as a function of k, …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.