Proof sketch of Theorem 2.1, PDF p. 2 — the easy computation: (1 − 5/√(k/2))(1 − 1/(2√k))/2 + (1/2 − √(1/k)) > 1 − 5/√k
ProvedMultiChoiceSecretary.Alg.combine_estimatesinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
For every real ,
The two terms on the right are the estimates, in units of , of the modified value selected among the first arrivals (by the induction hypothesis) and after them. This is the "easy computation" that closes the induction step of Theorem 2.1.
Formalization Note. Stated for every real , which contains every integer .
Preamble
import Mathlib import Definitions.Def_MultiChoiceSecretary_Alg_Setting
Formal statement
namespace MultiChoiceSecretary.Alg
theorem combine_estimates (k : ℝ) (hk : 0 < k) :
1 - 5 / Real.sqrt k <
(1 - 5 / Real.sqrt (k / 2)) * (1 - 1 / (2 * Real.sqrt k)) * (1 / 2) +
(1 / 2 - Real.sqrt (1 / k)) := by sorry
end MultiChoiceSecretary.Alg
Source
Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, SODA 2005, PDF p. 2 (right column), proof sketch of Theorem 2.1, "Combining the estimates from the preceding two paragraphs, an easy computation verifies …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.