Proof of Theorem 17, p. 17 — under the induction hypothesis, v(i,s) = a(n,s) − (1/(k+1))∏1/(k+t+1)·∏_{t<i}(s+t)·Σ_{s′≥s}T(i,s′)
ProvedSecretaryAdvice.SamplesDual.t_reductionclosed-formlp-dualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Consider the secretary problem with secretaries and samples, and let be the un-clipped backward recursion of the dual LP with the samples coefficients , of §5. Let and assume the inductive hypothesis of the proof of Theorem 17: for every round with and every signal , equals the un-clipped closed form ( if , and the expression inside the maximum of Theorem 17 if ). Then for every signal ,
where .
This step reduces the inductive step of Theorem 17 to an identity about the sum .
Preamble
import Mathlib import Definitions.Def_SecretaryAdvice_SamplesDual_ClosedForm open Finset
Formal statement
namespace SecretaryAdvice.SamplesDual
/-- Proof of Theorem 17, p. 17: if the un-clipped recursion agrees with the claimed closed form
at every round `i' > i` and every signal, then at round `i`
`v(i,s) = 1/(k+1)·∏_{t=1}^{n−1} (s+t)/(k+t+1)
− 1/(k+1)·∏_{t=1}^{n−1} 1/(k+t+1) · ∏_{t=1}^{i−1} (s+t) · Σ_{s'=s}^{k} T(i,s')`. -/
theorem t_reduction (n k i : ℕ) (hi : 1 ≤ i) (hin : i < n)
(ih : ∀ i' : ℕ, i < i' → i' ≤ n → ∀ s' : Fin (k + 1),
samplesUnclipped n k i' s' = unclippedFormula n k i' s')
(s : Fin (k + 1)) :
samplesUnclipped n k i s =
1 / ((k : ℝ) + 1) * (∏ t ∈ Icc 1 (n - 1), (((s : ℕ) : ℝ) + t) / ((k : ℝ) + t + 1)) -
1 / ((k : ℝ) + 1) * (∏ t ∈ Icc 1 (n - 1), 1 / ((k : ℝ) + t + 1)) *
(∏ t ∈ Icc 1 (i - 1), (((s : ℕ) : ℝ) + t)) *
∑ s' ∈ Icc (s : ℕ) k, T n k i s' := by sorry
end SecretaryAdvice.SamplesDual
Source
Dütting et al., Secretaries with Advice, arXiv:2011.06726v1, p. 17, proof of Theorem 17, inductive step (first display and the definition of T(i, s′))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.