Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
SecretaryPred.LearnedDynkin.numerical_bounds

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-ratiolearning-augmented-algorithmsoptimal-stoppingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem

Fix the parameters of Theorem 1, θ=0.646\theta=0.646θ=0.646 and τ=0.313\tau=0.313τ=0.313. Then:

  1. 1−θ1+θ≥0.215\dfrac{1-\theta}{1+\theta}\ge 0.2151+θ1−θ​≥0.215;
  2. τln⁡1τ≥0.363\tau\ln\dfrac1\tau\ge 0.363τlnτ1​≥0.363 (the bound of cases (i) and (iii));
  3. for every integer m≥1m\ge 1m≥1, each of the following case bounds is at least 0.2150.2150.215:
(ii)1m+1+τ∑k=1m(mk)(−1)k−11−τkk,(iv)τ∑k=1m(mk)(−1)k−11−τkk,\text{(ii)}\quad \frac{1}{m+1}+\tau\sum_{k=1}^{m}\binom{m}{k}(-1)^{k-1}\frac{1-\tau^k}{k},\qquad \text{(iv)}\quad \tau\sum_{k=1}^{m}\binom{m}{k}(-1)^{k-1}\frac{1-\tau^k}{k},(ii)m+11​+τk=1∑m​(km​)(−1)k−1k1−τk​,(iv)τk=1∑m​(km​)(−1)k−1k1−τk​, (v)(1−τ)m+1m+1−τ∑k=1m(mk)(−1)k1−τkk−1−τm{1−(1−τ)m},\text{(v)}\quad \frac{(1-\tau)^{m+1}}{m+1}-\tau\sum_{k=1}^{m}\binom{m}{k}(-1)^{k}\frac{1-\tau^k}{k}-\frac{1-\tau}{m}\bigl\{1-(1-\tau)^m\bigr\},(v)m+1(1−τ)m+1​−τk=1∑m​(km​)(−1)kk1−τk​−m1−τ​{1−(1−τ)m}, (vi)1m+1⋅1−θ1+θ−τ∑k=1m+1(m+1k)(−1)k1−τkk−1−τm+1{1−(1−τ)m+1}.\text{(vi)}\quad \frac{1}{m+1}\cdot\frac{1-\theta}{1+\theta}-\tau\sum_{k=1}^{m+1}\binom{m+1}{k}(-1)^{k}\frac{1-\tau^k}{k}-\frac{1-\tau}{m+1}\bigl\{1-(1-\tau)^{m+1}\bigr\}.(vi)m+11​⋅1+θ1−θ​−τk=1∑m+1​(km+1​)(−1)kk1−τk​−m+11−τ​{1−(1−τ)m+1}.

These are the numerical facts that turn the six case bounds into the constant 0.2150.2150.215 of Theorem 1. The margins are thin: the case (iv) bound at m=1m=1m=1 is τ(1−τ)=0.215031\tau(1-\tau)=0.215031τ(1−τ)=0.215031 and the case (vi) bound at m=1m=1m=1 is about 0.2150490.2150490.215049.

Formalization Note The decimals are exact rationals in Lean (0.646=646/10000.646 = 646/10000.646=646/1000, 0.313=313/10000.313 = 313/10000.313=313/1000); ln⁡\lnln 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
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me