Proof of Proposition 5.1, p. 42 — some chain i has Σ_j p_j^i ≤ k/ω
ProvedPosetSecretary.LowerBound.exists_chain_selProb_sum_leonline-selectionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pigeonholeposetsecretary-problem
Let and , and let be a selection rule with capacity on , the disjoint union of chains of elements. Write for the probability that selects the element . Then some chain satisfies
The least-selected chain is the one the lower-bound construction loads with the score.
Formalization Note The page indexes the elements of a chain by rank ("the th best"); the sum over all elements of a chain does not depend on that indexing.
Preamble
import Mathlib import Definitions.Def_AppliedComb_Posets_width import Definitions.Def_PosetSecretary_LowerBound_Setting
Formal statement
namespace PosetSecretary.LowerBound
theorem exists_chain_selProb_sum_le (ω k : ℕ) (hω : 1 ≤ ω)
(μ : Finset (ChainsPoset ω k) → ℝ) (hμ : IsSelectionRule k μ) :
∃ i : Fin ω, ∑ j : Fin k, selProb μ ⟨i, j⟩ ≤ (k : ℝ) / ω := by sorry
end PosetSecretary.LowerBound
Source
Salem & Gupta, Secretary Problems with Biased Evaluations Using Partial Ordinal Information, SSRN 3444283 (version of 2022-04-17), proof of Proposition 5.1, Appendix F, p. 42, second paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.