Proof of Theorem 1, numerical bounds, pp. 7 and 10 — at θ = 0.646, τ = 0.313: (1−θ)/(1+θ) ≥ 0.215, τ ln(1/τ) ≥ 0.363, and the bounds of cases (ii), (iv), (v), (vi) are ≥ 0.215 for every m ≥ 1
ProvedSecretaryPred.LearnedDynkin.numerical_boundscompetitive-ratiolearning-augmented-algorithmsoptimal-stoppingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem
Fix the parameters of Theorem 1, and . Then:
- ;
- (the bound of cases (i) and (iii));
- for every integer , each of the following case bounds is at least :
These are the numerical facts that turn the six case bounds into the constant of Theorem 1. The margins are thin: the case (iv) bound at is and the case (vi) bound at is about .
Formalization Note The decimals are exact rationals in Lean (, ); is Real.log.
Differences from the source:
- reading: 'the competitive ratio is at least 0.215 for all m' in cases (iv), (v), (vi), and 'the competitive ratio for the case (ii) is at least its second term' → the closed-form bound of each of cases (ii), (iv), (v), (vi) is ≥ 0.215 for every m ≥ 1; reason: the paper's case competitive ratios are these closed-form lower bounds; the (ii) clause is stated directly instead of through the comparison with (iv)
Preamble
import Mathlib import Definitions.Def_SecretaryPred_LearnedDynkin_Setting
Formal statement
namespace SecretaryPred.LearnedDynkin
theorem numerical_bounds :
(0.215 : ℝ) ≤ (1 - 0.646) / (1 + 0.646) ∧
(0.363 : ℝ) ≤ 0.313 * Real.log (1 / 0.313) ∧
(∀ m : ℕ, 1 ≤ m →
(0.215 : ℝ) ≤ 1 / ((m : ℝ) + 1) + 0.313 * ∑ k ∈ Finset.Icc 1 m,
(m.choose k : ℝ) * (-1 : ℝ) ^ (k - 1) * (1 - 0.313 ^ k) / (k : ℝ)) ∧
(∀ m : ℕ, 1 ≤ m →
(0.215 : ℝ) ≤ 0.313 * ∑ k ∈ Finset.Icc 1 m,
(m.choose k : ℝ) * (-1 : ℝ) ^ (k - 1) * (1 - 0.313 ^ k) / (k : ℝ)) ∧
(∀ m : ℕ, 1 ≤ m →
(0.215 : ℝ) ≤ (1 - 0.313) ^ (m + 1) / ((m : ℝ) + 1)
- 0.313 * ∑ k ∈ Finset.Icc 1 m,
(m.choose k : ℝ) * (-1 : ℝ) ^ k * (1 - 0.313 ^ k) / (k : ℝ)
- (1 - 0.313) / (m : ℝ) * (1 - (1 - 0.313) ^ m)) ∧
(∀ m : ℕ, 1 ≤ m →
(0.215 : ℝ) ≤ 1 / ((m : ℝ) + 1) * ((1 - 0.646) / (1 + 0.646))
- 0.313 * ∑ k ∈ Finset.Icc 1 (m + 1),
((m + 1).choose k : ℝ) * (-1 : ℝ) ^ k * (1 - 0.313 ^ k) / (k : ℝ)
- (1 - 0.313) / ((m : ℝ) + 1) * (1 - (1 - 0.313) ^ (m + 1))) := by sorry
end SecretaryPred.LearnedDynkin
Source
Fujii, Yoshida, The Secretary Problem with Predictions, arXiv:2306.08340v1, p. 7 (case M = ∅: (1−0.646)/(1+0.646) ≥ 0.215) and p. 10 (the paragraph after case (vi))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.