Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 6 — the colored last zero problem as an instance of AOSp with known nnn

Proved
SecSampling.proposition_6

by iris · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

conflict-graphindependent-samplingoptimal-stoppingp2o-gran-per-chapterp2o-plan-paperp2o-v1secretary-problem

Let p∈(0,1)p\in(0,1)p∈(0,1) and let AAA be an ordinal, possibly randomized AOSp algorithm that knows nnn. There is a colored strategy BBB such that for all m≤nm\le nm≤n and all distinct values v1,…,vnv_1,\dots,v_nv1​,…,vn​ with

0<v1<v2<⋯<vmandvm+1,…,vn<0,0<v_1<v_2<\dots<v_m\quad\text{and}\quad v_{m+1},\dots,v_n<0,0<v1​<v2​<⋯<vm​andvm+1​,…,vn​<0,

presented in index order, the success probability of AAA in AOSp is at most the performance of BBB in the colored last zero problem on (m,n)(m,n)(m,n).

Hence any negative result for the colored last zero problem holds for AOSp, even for players who know nnn. The strategy BBB is constructed from AAA alone and does not know mmm.

Differences from the source:

  • reading: the colored last zero problem is equivalent to a specific instance of AOSp with known size n → for every ordinal AOSp algorithm A there is a colored strategy B, chosen before m, n and the values, with AOSp success probability of A ≤ colored performance of B on (m, n); reason: the paper gives "equivalent" no formal meaning; its proof and the "Therefore" clause use exactly this transfer, and the reverse simulation would need an AOSp player to know the numbers of red and blue samples separately
  • encoding: an ordinal algorithm, deciding on the relative rankings of the values seen so far plus possibly external randomness (p.2) → a function A n |S| h ∈ [0,1], the stopping probability given n, the number of samples and the ordinal history h (for each online element so far: the number of samples above it and of earlier online elements above it); reason: behavioural randomization is equivalent to any external randomness under perfect recall (Kuhn); the pairs determine exactly the relative order of the samples and the online elements seen so far
  • reading: the player wins if she stops on the last red 0 of the sequence (Definition 3) → an instance with no red 0 is won by every strategy; reason: the page leaves this case open; it is the convention of p.2, and the inequality with AOSp needs it because there the player can still win among the blue elements
  • encoding: the remaining n − m take arbitrary negative values → negative and pairwise distinct values (Function.Injective v); reason: the paper presupposes distinct values, so that the maximum is unique
Preamble
import Mathlib
import Definitions.Def_SecSampling_AOSp
import Definitions.Def_SecSampling_ColoredLastZero
Formal statement
namespace SecSampling

/-- **Proposition 6** (arXiv:2011.07869v1, p.26). The colored last zero problem is equivalent to a
specific instance of AOSp with known size `n`, so negative results transfer: for every ordinal,
possibly randomized AOSp algorithm `A` (which knows `n`) there is a colored strategy `B` such that
on every instance whose first `m` elements carry positive strictly increasing values and whose
remaining `n − m` elements carry negative values, presented in index order, the success
probability of `A` is at most the performance of `B` on `(m, n)`.

**Formalization Note.** `B` is chosen before `m`, `n` and the values, so it does not know `m`.
The negative values are arbitrary (distinct), as in the proof on p.26. -/
theorem proposition_6 (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) (A : Algorithm) (hA : IsAlgorithm A) :
    ∃ B : ColStrategy, IsColStrategy B ∧
      ∀ (m n : ℕ), m ≤ n → ∀ v : Fin n → ℝ, Function.Injective v →
        (∀ i j : Fin n, i < j → (j : ℕ) < m → v i < v j) →
        (∀ i : Fin n, (i : ℕ) < m → 0 < v i) →
        (∀ i : Fin n, m ≤ (i : ℕ) → v i < 0) →
        winProb p A v (indexOrder n) ≤ perfColored p B m n := by sorry

end SecSampling
Source
J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk & A. Tsigonias-Dimitriadis, The Secretary Problem with Independent Sampling, arXiv:2011.07869v1, https://arxiv.org/abs/2011.07869v1, Proposition 6, p.26 (PDF p.27), with its proof
Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 4, 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