Proof of Theorem 17, pp. 17–19 — the un-clipped dual recursion equals the formula of Theorem 17 without the max
ProvedSecretaryAdvice.SamplesDual.unclipped_closed_formclosed-formlp-dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Consider the secretary problem with secretaries and samples, and let be the backward recursion of the dual LP with the samples coefficients of §5 and with the clipping removed: and . Then for every round and signal ,
and for
This is what the paper's induction proves ("For the proof we can ignore the ").
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
Formal statement
namespace SecretaryAdvice.SamplesDual
/-- Proof of Theorem 17, pp. 17–19, with `max {0, ·}` ignored: the un-clipped backward recursion
`v(i,s)` equals `a(n,s)` at `i = n` and the expression inside the max of Theorem 17 for `i < n`. -/
theorem unclipped_closed_form (n k i : ℕ) (hi : 1 ≤ i) (hin : i ≤ n) (s : Fin (k + 1)) :
samplesUnclipped n k i s = unclippedFormula n k i s := by sorry
end SecretaryAdvice.SamplesDual
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, pp. 17–19, proof of Theorem 17 (with the max ignored)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.