AFTD Auto-Formalizing Theoretical Domains

IsValidProbeSeq

def

A list of offline resources is a valid probe sequence for an arrival from available resources if it has no duplicates, all its resources are currently available, and its length does not exceed the arrival's patience budget.

Statement

def IsValidProbeSeq {n : ℕ} (arr : OMSRArrival n) (S : Finset (Fin n)) (L : List (Fin n)) : Prop
Defined in
scout/2611-03598-online-matching-with-arbitrary-stochastic-rewards.md:1173
Verified
04 Nov 2026
Axioms
none listed
Built on 1
  • OMSRArrivalAn arrival in online bipartite matching with stochastic rewards and patience facing n offline resources, consisting of a patience budget…
Used by 3
  • omsr_patience_single_arrival_optimalFor all n and all non-negative weights w, there exists a randomized online policy R for n resources such that on every arrival list arrs…
  • RandomizedOMSRPolicyFor n offline resources, a RandomizedOMSRPolicy packages a sample space Ω, a measurable space structure mΩ, a probability measure μ on Ω…
  • omsr_single_arrival_optimal_probeSeq_existsFor any resource weights w ≥ 0 and single arrival arr, there exists a valid probe sequence L from the full resource set univ whose probe…

Read back from the Lean

Given a natural number n, an arrival structure arr : OMSRArrival n, a finite set S : Finset (Fin n), and a list L : List (Fin n), IsValidProbeSeq arr S L asserts that: 1. L contains no duplicate elements (L.Nodup), 2. every element in L is an element of S (∀ i ∈ L, i ∈ S), and 3. the length of L is at most the patience parameter of arr (L.length ≤ arr.patience).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Validity of a probe sequence from available resources within patience budget. -/
def IsValidProbeSeq {n : ℕ} (arr : OMSRArrival n) (S : Finset (Fin n)) (L : List (Fin n)) : Prop :=
  L.Nodup ∧ (∀ i ∈ L, i ∈ S) ∧ L.length ≤ arr.patience
See it in the graphDiscuss this resultChallenge it